A sublinear bipartiteness tester for bounded degree graphs
Oded Goldreich, Dana Ron · 1998
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by incidence lists of bounded length d, and the testing algorithm can perform queries of the form: "who is the ith neighbor of vertex v". The tester should determine with high probability whether the graph is bipartite or ffl-far from bipartite for any given distance parameter ffl. Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidencelists representation. Our testing algorithm has query complexity and running time poly((log N )=ffl) \\Delta p N where N is the number of graph vertices. In previous work [GR96] we showed that\\Omega\\Gamma p N ) queries are necessary (for constant ffl), and hence the performance of our algorithm is tight (in its dependence on N ), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fast convergence of ra...