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 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.
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received December 6, 1999
Rights and permissions
About this article
Cite this article
Alon, N., Fischer, E., Krivelevich, M. et al. Efficient Testing of Large Graphs. Combinatorica 20, 451–476 (2000). https://doi.org/10.1007/s004930070001
Issue Date:
DOI: https://doi.org/10.1007/s004930070001