Three Theorems regarding Testing Graph Properties
Webpage for a paper by Oded Goldreich and Luca Trevisan
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.
Material available on-line
- The
first posted version, 2001.
- Comments
regarding the first posted version, 2002.
- The final version, 2002.
[PDF versions]
- Errata to the final/journal version
(re the 2nd Theorem), 2005.
[PDF versions]
- Another errata, this one minor and referring to the 1st theorem.
Due to switching between proofs, we forgot to adapt some constants
in the proof. Specifically, the threshold for light weigth strings
should be modified from relative Hamming weight of $1/3$ to, say,
relative Hamming weight of $0.49$. This allows to prove Claim 3.1
as stated, where the problem is upper bounding the number of graphs
that are $0.1$-close to some final graph. This modification allows
to upperbound the number of final graphs by
$$2^{2t+o(t)}\cdot(N!)\cdot2^{0.51 {N\choose 2}}
= 2^{(0.02 + o(1) + 0.51)\cdot {N\choose 2}}$$
(rather than $2^{0.7 {N\choose 2}}$ as in Eq. (1)).,
Each such graph is $0.1$-close to at most $2^{0.469 {N\choose 2}}$ graphs,
and so the total number of graphs that are $0.1$-close to some final graph
is at most $2^{(0.999+o(1))\cdot {N\choose 2}} =o(2^{{N\choose 2}})$.
[Sept 2008]
See also list of papers on property testing.
Back to
either Oded Goldreich's homepage.
or general list of papers.