Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-010 | 26th May 2001 00:00

Three Theorems regarding Testing Graph Properties. Revision of: TR01-010

RSS-Feed




Revision #1
Authors: Oded Goldreich, Luca Trevisan
Accepted on: 26th May 2001 00:00
Downloads: 3546
Keywords: 


Abstract:


Property testing is a relaxation of decision problems
in which it is required to distinguish yes-instances
(i.e., objects having a predetermined property) from instances
that are far from any yes-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation.
More specifically, these theorems relate to the project of
characterizing graph properties according to the complexity of
testing them (in the adjacency matrix representation).

The first theorem is that there exist monotone graph
properties in NP for which testing is very hard
(i.e., requires to examine a constant fraction of the entries in the matrix).
Our second theorem is that every graph property that can be tested
making a number of queries
that is independent of the size of the graph,
can be so tested by uniformly selecting a set of vertices
and accepting iff the induced subgraph has some fixed graph property
(which is not necessarily the same as the one being tested).
Our third theorem refers to the framework
of graph partition problems,
and is a characterization of the subclass of properties that
can be tested using a one-sided error tester making a number of
queries that is independent of the size of the graph.


Paper:

TR01-010 | 25th January 2001 00:00

Three Theorems regarding Testing Graph Properties.





TR01-010
Authors: Oded Goldreich, Luca Trevisan
Publication: 25th January 2001 17:04
Downloads: 3261
Keywords: 


Abstract:


Property testing is a relaxation of decision problems
in which it is required to distinguish {\sc yes}-instances
(i.e., objects having a predetermined property) from instances
that are far from any {\sc yes}-instance.
We presents three theorems regarding testing graph
properties in the adjacency matrix representation.
More specifically, these theorems relate to the project of
characterizing graph properties according to the complexity of
testing them (in the adjacency matrix representation).

The first theorem is that there exist {\em monotone}\/ graph
properties in $\NP$ for which testing is very hard
(i.e., requires to examine a constant fraction of the entries in the matrix).
Our second theorem is that every graph property that can be tested
using a {\em one-sided error}\/ tester making a number of queries
that is independent of the size of the graph,
can be so tested by uniformly selecting a set of vertices
and accepting iff the induced subgraph has some fixed graph property
(which is not necessarily the same as the one being tested).
Our third theorem refers to the framework
of {\em graph partition problems},
and is a characterization of the subclass of properties that
can be tested using a one-sided error tester making a number of
queries that is independent of the size of the graph.



ISSN 1433-8092 | Imprint