A Sublinear Bipartite Tester for Bounded-Degree Graphs

Webpage for a paper by Oded Goldreich and Dana Ron


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.