TY - JOUR

T1 - Efficient testing of large graphs

AU - Alon, Noga

AU - Fischer, Eldar

AU - Krivelevich, Michael

AU - Szegedy, Mario

N1 - Funding Information:
† Research supported by a USA Israeli BSF grant, by a grant from th e Israel Science Foundation and by th e Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2000

Y1 - 2000

N2 - Let P be a property of graphs. An ∈-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 ∈n2 edges to make it satisfy P. The property P is called testable, if for every ∈ there exists an ∈-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, admit an ∈-test. In this paper we make a first step towards a complete 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 "∀∃" are always testable, while we show that some properties containing this alternation are not.

AB - Let P be a property of graphs. An ∈-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 ∈n2 edges to make it satisfy P. The property P is called testable, if for every ∈ there exists an ∈-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, admit an ∈-test. In this paper we make a first step towards a complete 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 "∀∃" are always testable, while we show that some properties containing this alternation are not.

UR - http://www.scopus.com/inward/record.url?scp=0034360832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034360832&partnerID=8YFLogxK

U2 - 10.1007/s004930070001

DO - 10.1007/s004930070001

M3 - Article

AN - SCOPUS:0034360832

VL - 20

SP - 451

EP - 476

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 4

ER -