Efficient Testing of Large Graphs

Let P be a property of graphs. An /spl epsiv/-test for P is a randomized algorithm which, given 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, between the case of G satisfying P and the case that it has to be modified by adding and removing more than /spl epsiv/n/sup 2/ edges to make it satisfy P. The property P is called testable, if for every /spl epsiv/ there exists an /spl epsiv/-test for P whose total number of queries is independent of the size of the input graph. O. Goldreich et al. (1996) showed that certain graph properties admit an /spl epsiv/-test. In this paper we make a first step towards a logical characterization of all testable graph properties, and show that properties describable by a very general type of coloring problem are testable. We use this theorem to prove that first order graph properties not containing a quantifier alternation of type "/spl forall//spl exist/" are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called /spl epsiv/-unavoidable in G if all graphs that differ from G in no more than /spl epsiv/|G|/sup 2/ places contain an induced copy of H. A graph H is called /spl delta/-abundant in G if G contains at least /spl delta/|G|/sup |H|/ induced copies of H. If H is /spl epsiv/-unavoidable in G then it is also /spl delta/(/spl epsiv/, |H|)-abundant.

Authors

• Noga Alon
• Eldar Fischer
• Michael Krivelevich
• Mario Szegedy

Keywords

• Mathematics
• Logic testing
• Radio access networks
• Read only memory
• Geometry
• Vertices
• Graph Properties
• Input Graph
• Cardinality
• Loss Of Generality
• Isomorphism
• Typical Properties
• Probability 1
• Random Graph
• Monotonicity Property
• Induced Subgraph
• Equipartition
• Graph Isomorphism
• Family Of Graphs
• Universal Quantifier