Efficient testing of large graphs

Let P be a property of graphs. An epsilon -test for P is a, randomized algo rithm which, given the ability to make queries whether a desired pair of ve rtices of an input graph G with n vertices are adjacent or not, distinguish es, 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 epsilonn(2) edg es to make it satisfy P. The property P is called testable, if for every ep silon there exists an epsilon -test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [ 8] showed that certain individual graph properties, like k-colorability, ad mit an epsilon -test. In this paper we make a first step towards a complete logical characterization of all testable graph properties, and show that p roperties describable by a very general type of coloring problem are testab le. We use this theorem to prove that first order graph properties not cont aining a quantifier alternation of type "For All There Exists" are always t estable, 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 epsilon -unavoidable in G if all graphs that differ from G in no mo re than epsilon /G/(2) places contain an induced copy of H. A graph H is ca lled delta -abundant in G if G contains at least delta /G/(/H/) induced cop ies of H. If H is epsilon -unavoidable in G then G is also delta(epsilon, / H/)-abundant.