ECCC-Report TR00-083https://eccc.weizmann.ac.il/report/2000/083Comments and Revisions published for TR00-083en-usMon, 23 Sep 2002 00:00:00 +0300
Revision 1
| |
Eldar Fischer
https://eccc.weizmann.ac.il/report/2000/083#revision1Mon, 23 Sep 2002 00:00:00 +0300https://eccc.weizmann.ac.il/report/2000/083#revision1
Paper TR00-083
| Testing graphs for colorability properties |
Eldar Fischer
https://eccc.weizmann.ac.il/report/2000/083Let $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
tournaments.
Tue, 26 Sep 2000 15:14:23 +0300https://eccc.weizmann.ac.il/report/2000/083