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.

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