Revision #1 Authors: Oded Goldreich, Luca Trevisan

Accepted on: 26th May 2001 00:00

Downloads: 2048

Keywords:

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.

TR01-010 Authors: Oded Goldreich, Luca Trevisan

Publication: 25th January 2001 17:04

Downloads: 1819

Keywords:

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.