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 ɛ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 [1]. Interestingly, it turns out that if PH has a polynomial query complexity, then there is a two-sided ɛ-tester for PH that