## 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^{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 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 the following precise characterization of all the digraphs H, for which f(ε, H) has a polynomial dependency on ε: a homomorphism φ: V(H) → V(K), from a digraph H to K, is a function that satisfies (u, v) ∈ E(H) ⇒ (φ(u), φ(v)) ∈ E(K). The core of a digraph H is the smallest subgraph K of H, for which there is a homomorphism from H to K. We show that for a connected H, f(ε, H) has a polynomial dependency on 1/ε, if and only if the core of H is either an oriented tree or a directed cycle of length 2. This implies that there is a one sided error property tester for testing H-freeness, whose query complexity is polynomial in 1/ε if and only if H is of the above two types. We further show that the same characterization applies for two-sided error property testers as well. A special case of this result settles an open problem raised by the first author in [1]. 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 P_{H} makes at least (1/ε)^{Ω(d)} queries, where d is the average degree of H. We 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 P_{H}. 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 language | English (US) |
---|---|

Pages (from-to) | 700-709 |

Number of pages | 10 |

Journal | Conference Proceedings of the Annual ACM Symposium on Theory of Computing |

DOIs | |

State | Published - 2003 |

Externally published | Yes |

Event | 35th Annual ACM Symposium on Theory of Computing - San Diego, CA, United States Duration: Jun 9 2003 → Jun 11 2003 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Directed Graphs
- Property Testing
- Regularity Lemma