Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR00-083 | 23rd September 2002 00:00


Revision #1
Authors: Eldar Fischer
Accepted on: 23rd September 2002 00:00
Downloads: 1362



TR00-083 | 18th September 2000 00:00

Testing graphs for colorability properties

Authors: Eldar Fischer
Publication: 26th September 2000 15:14
Downloads: 1461


Let $P$ be a property of graphs. An $\epsilon$-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 $\epsilon{n\choose2}$ edges to make it
satisfy $P$. The property $P$ is called testable, if for every
$\epsilon$ there exists an $\epsilon$-test for $P$ whose total number
of queries is independent of the size of the input graph. Goldreich,
Goldwasser and Ron (FOCS 1996) showed that certain graph properties,
like $k$-colorability, admit an $\epsilon$-test. In [Alon, Fischer,
Krivelevich and Szegedy, FOCS 1999] a first step towards a logical
characterization of the testable graph properties was made by proving
that properties describable by a very general type of coloring problem
are testable.

It is proven here that other classes of graph properties, describable by
various generalizations of the coloring notion used in the above article are
testable. It is also observed that these testability results, as well as
the previous results about existence of non-testable properties, can
be extended to certain combinatorial structures related to graphs, such as

ISSN 1433-8092 | Imprint