A Sublinear Bipartite Tester for Bounded-Degree Graphs
Webpage for a paper by Oded Goldreich and Dana Ron
Abstract
We present a sublinear-time algorithm for testing whether a
bounded-degree graph is bipartite or far from being bipartite.
The algorithm is given oracle access to the incidence list of
the graph, and should determine with high probability whether
the graph is bipartite or $\epsilon$-far from bipartite
for any given distance parameter $\epsilon$. Distance between
graphs is defined to be the fraction of entries on which the graphs
differ in their incidence-lists representation.
Our testing algorithm has query complexity and running time
$\poly((\log N)/\epsilon)\cdot\sqrt{N}$ where $N$ is the number of
graph vertices. The query complexity almost matches a previously
known lower bound.
A major part of our analysis is showing that any graph can be
partitioned into subsets such that each subset exhibits a certain
rapid-mixing property, and the total number of edges between the
subsets is small.
Material available on-line
A version dating to
1997.
Back to
either Oded Goldreich's homepage.
or general list of papers.