Testing subgraphs in directed graphs

ABSTRACT

Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ε n² edges have to be deleted from it to make it H-free. We show that in this case G contains at least f(ε,H) n^h copies of H. This is proved by establishing a directed version of Szemeredi's regularity lemma, and implies that for every H there is a one-sided error property tester whose query complexity is bounded by a function of ε only for testing the property PH of being H-free.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon, Testing Subgraphs in Large Graphs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.434, October 14-17, 2001
	2	N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
	3	Noga Alon , W. Fernandez de la Vega , Ravi Kannan , Marek Karpinski, Random sampling and approximation of MAX-CSP problems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509945]
	4	N. Alon , S. Dar , M. Parnas , D. Ron, Testing of clustering, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.240, November 12-14, 2000
	5	N. Alon, E. Fischer, M. Krivelevich and M. Szegedy, Efficient testing of large graphs, Proc. 40th Annual Symp. on Foundations of Computer Science (FOCS), New York, NY, IEEE (1999), 656--666. Also: Combinatorica 20 (2000), 451--476.
	6	Noga Alon , Michael Krivelevich , Ilan Newman , Mario Szegedy, Regular Languages are Testable with a Constant Number of Queries, SIAM Journal on Computing, v.30 n.6, p.1842-1862, 2001 [doi>10.1137/S0097539700366528]
	7	Noga Alon , Michael Krivelevich, Testing k-colorability, SIAM Journal on Discrete Mathematics, v.15 n.2, p.211-227, 2002 [doi>10.1137/S0895480199358655]
	8	N. Alon, M. Krivelevich and B. Sudakov, Turan numbers of bipartite graphs and related Ramsey-type questions, submitted.
	9	Noga Alon , Asaf Shapira, Testing satisfiability, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.645-654, January 06-08, 2002, San Francisco, California
	10	J. Bang-Jensen , P. Hell, The effect of two cycles on the complexity of colouring by directed graphs, Discrete Applied Mathematics, v.26 n.1, p.1-23, Jan. 1990 [doi>10.1016/0166-218X(90)90017-7]
	11	F. A. Behrend, On sets of integers which contain no three terms in arithmetic progression, Proc.\ National Academy of Sciences USA 32 (1946), 331--332.
	12	Andrej Bogdanov , Kenji Obata , Luca Trevisan, A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.93-102, November 16-19, 2002
	13	B. Bollobas, P. Erdos, M. Simonovits and E. Szemeredi, Extremal graphs without large forbidden subgraphs, Annals of Discrete Mathematics 3 (1978), 29--41.
	14	Artur Czumaj , Christian Sohler, Testing Hypergraph Coloring, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.493-505, July 08-12, 2001
	15	Artur Czumaj , Christian Sohler , Martin Ziegler, Property Testing in Computational Geometry, Proceedings of the 8th Annual European Symposium on Algorithms, p.155-166, September 05-08, 2000
	16	Reinhard Diestel, Graph Theory, Second Edition, Springer-Verlag, New York, 2000.
	17	P. Erdos, P. On extremal problems of graphs and generalized graphs. Israel J. Math. 2 1964 183--190.
	18	P. Erdos and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), 181--192.
	19	E. Fischer, The art of uninformed decisions: A primer to property testing, The Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science 75 (2001), 97--126.
	20	A. Frieze and R. Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), 175--220.
	21	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
	22	O. Goldreich , L. Trevisan, Three Theorems Regarding Testing Graph Properties, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.460, October 14-17, 2001
	23	W. T. Gowers, Lower bounds of tower type for Szemeredi's Uniformity Lemma, Geometric and Functional Analysis 7 (1997), 322--337.
	24	Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
	25	P. Hell, J. Nesetril, and X. Zhu, Duality of graph homomorphisms, in: Combinatorics, Paul Erd\Hos is Eighty, (D. Miklos et. al, eds.), Bolyai Society Mathematical Studies, Vol.2, 1996, pp. 271--282.
	26	J. Komlos and M. Simonovits, Szemeredi's regularity lemma and its applications in graph theory, in: Combinatorics, Paul Erdos is Eighty, (D. Miklos et. al, eds.), Bolyai Society Mathematical Studies, Vol.2, 1996, pp. 295--352.
	27	V. Rodl and R. Duke, On graphs with small subgraphs of large chromatic number, Graphs and Combinatorics 1 (1985), 91--96.
	28	D. Ron, Property testing, in: P. M. Pardalos, S. Rajasekaran, J. Reif and J. D. P. Rolim, editors, Handbook of Randomized Computing, Vol. II, Kluwer Academic Publishers, 2001, 597--649.
	29	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
	30	E. Szemeredi, Regular partitions of graphs, In: Proc. Colloque Inter. CNRS (J. C. Bermond, J. C. Fournier, M. Las~Vergnas and D. Sotteau, eds.), 1978, 399--401.
	31	A. C. Yao, Probabilistic computation, towards a unified measure of complexity. Proc. of the 18th IEEE FOCS (1977), 222--227.