Every Monotone Graph Property is TestableNoga Alon∗Tel Aviv University Tel Aviv, Isarel

[email protected] Shapira†Tel Aviv University Tel Aviv,

[email protected] graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract family of all monotone graph properties was also extensively studied. Our main result in this paper is that any monotone graph prop- erty can be tested with one-sided error, and with querycomplexity depending only on †. This result unifies several previous results in the area of property testing, and also implies the testability of well-studied graph properties that were previously not known to be testable. At the heart of the proof is an application of a variant of Szemer´ edi’s Regu- larity Lemma. The main ideas behind this application may be useful in characterizing all testable graph properties, and in generally studying graph property testing. As a byproduct of our techniques we also obtain addi- tional results in graph theory and property testing, which are of independent interest.One of these results is that the query complexity of testing testable graph properties with one-sided error may be arbitrarily large. Another re-sult, which significantly extends previous results in extremal graph-theory, is that for any monotone graph property P, any graph that is †-far from satisfying P, contains a sub- graph of size depending on † only, which does not satisfy P. Finally, we prove the following compactness statement: If agraph G is †-far from satisfying a (possibly infinite) set of graph properties P, then it is at least δP(†)-far from satis- fying one of the properties.∗Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. †This work forms part of the author’s Ph.D. thesis. Research supported in part by a Charles Clore Foundation Fellowship and an IBM Ph.D. Fellowship.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. STOC’05, May 22-24, 2005, Hunt Valley, Maryland, USA. Copyright 2005 ACM 1-58113-960-8/05/0005 .$5.00.Categories and Subject DescriptorsG.2.2 [Discrete Mathematics]: Graph Theory—Graph al- gorithms; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems— Computations on discrete structuresGeneral TermsAlgorithms, TheoryKeywordsProperty Testing, Monotone Properties, Regularity Lemma1.INTRODUCTION1.1Definitions and BackgroundAll graphs considered here are finite, undirected, and have neither loops nor parallel edges.Let P be a property of graphs, namely, a family of graphs closed under isomor- phism.All graph properties discussed in this paper are assumed to be decidable, that is, we disregard properties for which it is not possible to tell whether a given graphsatisfies them. A graph G with n vertices is said to be †- far from satisfying P if one must add or delete at least †n2 edges in order to turn G into a graph satisfying P. A tester for P is a randomized algorithm which, given the quantity n and the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or not, distinguishes with high probability (say, 2/3), between the case of G satisfying P and the case of G being †-far from satisfying P. One of the striking results in the area of property-testing is that many natural graph properties have a tester, whose total number of queries is bounded only by a function of †, which is independent of the size of the input graph. A property having such a tester is called testable. Note, that if the number of queries performed by the tester is bounded by a function of † only, then so is its running time. A tester is said to have one-sided error if wheneverG satisfies P, the algorithm declares that this is the case with probability 1. Throughout the paper, we assume thata tester first samples a set of vertices, queries all edges on the set, and then accepts or rejects by considering the graph spanned by the set. As observed in [3] and formally proved in [20], this can be assumed with no loss of generality, as this assumption at most squares the query complexity (and we will not care about such factors in this paper).The general notion of property testing was first formulated by Rubinfeld and Sudan [29], who were motivated mainly byits connection to the study of program checking. The study of the notion of testability for combinatorial structures, and mainly for labelled graphs, was introduced in the seminal paper of Goldreich, Goldwasser and Ron [19], who showed that several natural graph properties are testable. In the wake of [19], many other graph properties were shown to be testable, while others were shown to be non-testable. See [15], [18] and [28] for additional results and references on graph property-testing as well as on testing properties of other combinatorial structures.1.2Related Work The most interesting results in property-testing are those that show that large families of problems are testable. The main result of [19] states that a certain abstract graph parti- tion problem, which includes as a special case k-colorability, having a large cut and having a large clique, is testable. The authors of [20] gave a characterization of the partition prob- lems discussed in [19] that are testable with one-sided error. In [3], a logical characterization of a family of testable graph properties was obtained. According to this characterization,every first order graph-property of type ∃∀ is testable, whilethere are first-order graph properties of type ∀∃ that are not testable. These results were extended in [14]. There are also several general testability and non-testability results in other areas besides testing graph properties. In [4] it is proved that every regular language is testable. This re- sult was extended to any read-once branching program in [24]. On the other hand, it was proved in [16], that there are read-twice branching programs that are not-testable. The main result of [6] states that any constraint satisfac- tion problem is testable. With this abundance of general testability results, a natu- ral question is what makes a combinatorial property testable. As graphs are the most well studied combinatorial structures in the theory of computation, it is natural to consider the problem of characterizing the testable graph properties, as the most important open problem in the area of propertytesting. Regretfully, though, finding such a characterization seems to be a very challenging endeavor, which is still open.1.3The Main New Result Our main goal in this paper is to show that all the graph properties that belong to a large, natural and well studied family of graph properties are testable. In fact, we even show that these properties are testable with one-sided error. A graph-property P is said to be monotone if it is closed under removal of edges and vertices. In other words, if a graph G does not satisfy P, then any graph that contains G as a (not necessarily induced) subgraph does not satisfy P as well. Various monotone graph properties were extensively studied in graph theory. As examples of monotone properties one can consider the property of having a homomorphism to afixed graph H (which includes as a special case the propertyof being k-colorable, see Definition 2.2), and the property of not containing a (not necessarily induced) copy of somefixed graph H. Another monotone property is being (k,H)-Ramsey: For a (possibly infinite) family of graphs H, a graph is said to be (k,H)-Ramsey if one can color its edges using k colors, such that no color class contains a copy of a graph H ∈ H. This property is the main focus of Ramsey-Theory, see [21] and its references.As another example, one can consider the property of being (k,H,f)-Multicolorable; Fora (possibly infinite) family of graphs H and a function f from H to the positive integers, a graph is said to be (k,H,f)- Multicolorable if one can color its edges using k colors, such that every copy of a graph H ∈ H receives at least f(H) colors. See [13], [11] and their references for a discussion of some special cases. The abstract family of monotone graph properties has also been extensively studied in graph theory. See [17], [10], [9] and their references. Our main result is the following:Theorem 1. (The Main Result) Any monotone graph property is testable with one-sided error.We stress that we actually prove a slightly weaker state- ment than the one given above, as the monotone property has to satisfy some technical conditions (which cannot be avoided).However, as the cases where the actual result is weaker than what is stated in Theorem 1 deal with ex- tremely unnatural properties, and even in these cases the actual result is roughly the same, we postpone the precise statement to Section 4 (see Theorem 6). Another impor-tant note is that in [20], Goldreich and Trevisan define a monotone graph property to be one that is closed under removal of edges, and not necessarily under removal of ver- tices.They show that there are such properties that are not testable even with two sided error. In fact, their resultis stronger as the property they define belongs to NP and has query complexity Ω(n2). This means that Theorem 1 cannot be extended, in a strong sense, to properties that are only closed under removal of edges. As we have mentioned above, having a homomorphismto a fixed graph H, k-colorability and the property of notcontaining a copy of a fixed graph H, are monotone prop- erties, and are thus testable with one-sided error by Theo- rem 1. These properties were known to be testable before, and as Theorem 1 applies to general monotone properties, the bounds it supplies for these properties are inferior com- pared to the ones proved by the ad-hoc arguments (see [5], [19], [20] and [7]). In Theorem 4 we prove that this is un- avoidable.The main importance of Theorem 1 thus lies in its generality. However, as described in the beginning of this subsection, there are additional natural and well-studied monotone graph properties that prior to this work were not known to be testable, and we may thus use Theorem 1 to conclude that these properties are testable with one-sided error. We also believe that Theorem 1 and its proof may be an important step towards a combinatorial characterization of the graph properties that are testable with one-sided er- ror. Another important aspect of Theorem 1 is that it can be used to prove general results on graph property testing. Two examples are Theorems 4 and 5, which we describe in the next subsection. Another result is discussed in Section 4. We believe that Theorem 1 will be useful for proving other consequences as well.See Section 7 for more details and possible natural lines of research suggested by the results of this paper.1.4Techniques and Additional ResultsThe first technical ingredient in the proof of Theorem 1 is the proof of an (almost) equivalent formulation of it. For a(possibly infinite) family of graphs F we say that a graph is F-free if it contains no member from F as a (not necessar- ily induced) subgraph. Clearly, being F-free is a monotoneproperty. It is well known (see e.g. [2]) that for any finite family of graphs F, the property of being F-free is testable. This follows from a standard application of Szemer´ edi’s Reg- ularity Lemma. As we discuss in Section 2, this lemma isinadequate for obtaining a similar result for infinite families of graphs. The main technical step in the proof of Theo- rem 1 is the following theorem, which is the main technical contribution of this paper.Theorem 2. For every (possibly infinite) family of graphs F, there are functions NF(†) and QF(†) with the following properties: If G is a graph on n ≥ NF(†) vertices which is †-far from being F-free, then a random subset of QF(†) vertices of G spans a member of F with probability at least 2/3.Note that Theorem 2 immediately implies that for every family of graphs F, the property of being F-free is testable. In order to prove Theorem 2 we apply a strong version of the regularity lemma, proved by Alon, Fischer, Krivelevich and Szegedy [3].We believe that our application of this lemma may be useful for attacking other problems. As a byproduct of our argument we obtain the following graph theoretic result.Theorem 3. For every monotone graph property P, there is a function WP(†) with the following property: If G is †- far from satisfying P, then G contains a subgraph of size at most WP(†), which does not satisfy P.The above theorem significantly extends a result of R¨ odl and Duke [26], conjectured by Erd˝ os, which asserts that the above statement holds for the k-colorability property. Theo- rem 3 applies to any monotone property, and in particular to all the properties discussed in the beginning of the previous subsection. As will become evident from the proof of Theorem 1 (which is based on Theorem 2), the upper bounds for testing a monotone property depend on the property being tested. In other words, what we prove is that for every property P, there is a function QP(†) such that P can be tested with query complexity QP(†). A natural question one may ask,is if the dependency on the specific property being tested can be removed. We rule out this possibility by proving the following.Theorem 4. For any function Q : (0,1) 7→ N, there isa monotone graph property P, such that for infinitely many values of †, P cannot be tested with one-sided error using less than Q(†) queries.We note that proving the above for finitely many values of † is rather easy. This, however, will not imply that there are monotone properties that cannot be tested using query complexity, say, 2O(1/†). Prior to this work, the best lower bound proved for testing a testable graph property with one- sided error was obtained in [1], where it is shown that for every non-bipartite graph H, the query complexity of testing whether a graph does not contain a copy of H is at least (1/†)Ω(log 1/†). The fact that for every H this property is testable with one-sided error, follows from [2] and [3], and also as a special case from Theorem 1. As by Theorem 1 every monotone graph property is testable with one-sided error, Theorem 4 establishes that the one-sided error querycomplexity of testing testable graph properties, even those that are tes