Testing subgraphs in directed graphs

Noga Alon, Asaf Shapira

Research output: Contribution to journalArticle

68 Scopus citations

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 εn2 edges have to be deleted from it to make it H-free. We show that in this case G contains at least f(ε,H)nh copies of H. This is proved by establishing a directed version of Szemerédi'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. As is common with applications of the undirected regularity lemma, here too the function 1/f(ε,H) is an extremely fast growing function in ε. We therefore further prove a precise characterization of all the digraphs H, for which f(ε,H) has a polynomial dependency on ε. This implies a characterization of all the digraphs H, for which the property of being H-free has a one-sided error property tester whose query complexity is polynomial in 1/ε. We further show that the same characterization also applies to two-sided error property testers as well. A special case of this result settles an open problem raised by the first author in (Alon, Proceedings of the 42nd IEEE FOCS, IEEE, New York, 2001, pp. 434-441). Interestingly, it turns out that if PH has a polynomial query complexity, then there is a two-sided ε-tester for PH that samples only O(1/ε) vertices, whereas any one-sided tester for PH makes at least (1/ε)d/2 queries, where d is the average degree of H. We also show that the complexity of deciding if for a given directed graph H, P H has a polynomial query complexity, is NP-complete, marking an interesting distinction from the case of undirected graphs. For some special cases of directed graphs H, we describe very efficient one-sided error property-testers for testing PH. As a consequence we conclude that when H is an undirected bipartite graph, we can give a one-sided error property tester with query complexity O((1/ε)h/2), improving the previously known upper bound of O((1/ε)h2). The proofs combine combinatorial, graph theoretic and probabilistic arguments with results from additive number theory.

Original languageEnglish (US)
Pages (from-to)354-382
Number of pages29
JournalJournal of Computer and System Sciences
Volume69
Issue number3 SPEC. ISS.
DOIs
StatePublished - Nov 2004
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Core
  • Directed graphs
  • Property testing
  • Regularity

Fingerprint Dive into the research topics of 'Testing subgraphs in directed graphs'. Together they form a unique fingerprint.

Cite this