ISSN:
1439-6912
Keywords:
AMS Subject Classification (1991) Classes: 68R10, 05C85, 05C35.
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004930070001
Permalink
