Efficient testing of large graphs (Q5932749)

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 \textit{O. Goldreich, S. Goldwasser} and \textit{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.