Name
Abstract | ||
|---|---|---|
Let P be a property of graphs. An \math-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 \math edges to make it satisfy P. The property P is called testable, if for every \math there exists an \math-test for P whose total number of queries is independent of the size of the input graph. Goldreich, Goldwasser and Ron [Property testing and its connection to learning and approximation, Proceedings of the 37th Annual IEEE FOCS (1996), 339--348] showed that certain graph properties admit an \math-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 \math 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 \math-unavoidable in G if all graphs that differ from G in no more than \math|G|2 places contain an induced copy of H. A graph H is called \math-abundant in G if G contains at least \math|G |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/s004930070001 | FOCS '99 Proceedings of the 40th Annual Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
graph H,certain graph property,input graph,input graph G,order graph property,testable graph property,math edge,properties describable,property P,property testing,Efficient Testing,Large Graphs | Graph theory,Discrete mathematics,Randomized algorithm,Combinatorics,Property testing,Existential quantification,Graph property,Vertex (geometry),Mathematics,Lemma (mathematics),Alternation (linguistics) | Journal |
Volume | Issue | ISSN |
20 | 4 | 1439-6912 |
ISBN | Citations | PageRank |
0-7695-0409-4 | 2 | 0.37 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Noga Alon | 1 | 10468 | 1688.16 |
| eldar fischer | 2 | 815 | 63.82 |
| michael krivelevich | 3 | 1688 | 179.90 |
| Mario Szegedy | 4 | 3358 | 325.80 |