Testing subgraphs in directed graphs

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 2 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 P H of being H-free.

Authors

• Noga Alon
• Asaf Shapira

Keywords

• directed graphs
• property testing
• regularity lemma