zbMATH — the first resource for mathematics

Efficient testing of large graphs. (English) Zbl 1052.68096
An $$\epsilon$$-test for a graph property $$P$$ is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph $$G$$ of order $$n$$ are adjacent or not, distinguishes with probability at least $$2\over3$$ between the case of $$G$$ satisfying $$P$$ and the case $$G$$ has to be modified by adding or removing more than $$\varepsilon n^2$$ edges to make it satisfy $$P$$. The property $$P$$ is called testable if for every $$\varepsilon>0$$ there exists an $$\varepsilon$$-test for $$P$$ whose total number of queries is bounded only by a function of $$\varepsilon$$.
It was previously shown by O. Goldreich, S. Goldwasser and D. Ron [Proceedings of the 37th annual symposium on Foundations of computer science, 339–348 (1996)] that graph properties describable by the existence of a partition of certain type, like $$k$$-colorability, are testable. The authors study the testability of first order graph properties. The main result states that graph properties describable by a first order expression containing at most one quantifier or a quantifier alternation of type “$$\exists\forall$$” are testable. The result is obtained by proving a variant of Szemerédi regularity lemma and using it to show the testability of a certain generalized coloring problem. The authors also describe a first order property of type “$$\forall\exists$$”, based on the graph isomorphism problem, which is not testable.

MSC:
 68R10 Graph theory (including graph drawing) in computer science 05C85 Graph algorithms (graph-theoretic aspects) 05C35 Extremal problems in graph theory
Full Text: