Efficient testing of large graphs

Noga Alon, Michael Krivelevich, Eldar Fischer, Mario Szegedy

Research output: Contribution to journalConference articlepeer-review

41 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 graph properties admit an ε-test. In this paper we make a first step towards a 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 qq are always testable, while we show that some properties containing this alternation are not. Our results are proven using a combinatorial lemma, a special case of which, that may be of independent interest, is the following. A graph H is called qq-unavoidable in G if all graphs that differ from G in no more than qq|G|2 places contain an induced copy of H. A graph H is called δ-abundant in G if G contains at least δ|G||H| induced copies of H. If H is qq-unavoidable in G then it is also δ(qq, |H|)-abundant.

Original languageEnglish (US)
Pages (from-to)656-666
Number of pages11
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE 40th Annual Conference on Foundations of Computer Science - New York, NY, USA
Duration: Oct 17 1999Oct 19 1999

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

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

Cite this