Efficient testing of large graphs

Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy

Research output: Contribution to journalArticlepeer-review

219 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)451-476
Number of pages26
JournalCombinatorica
Volume20
Issue number4
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Efficient testing of large graphs'. Together they form a unique fingerprint.

Cite this