A sublinear bipartiteness tester for bounded degree graphs

We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far from being bipartite. Graphs are represented by i ncidence lists of bounded length d, anti the testing: algorithm can perform queries of the form: "who is the ith neighbor of vertex v". The tester sho uld determine with high probability whether the graph is bipartite or E-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 co mplexity and running time poly((log N)/epsilon) . root N where N is the num ber of graph vertices. It was shown before that; Omega(root N) queries are necessary (for constant epsilon), and hence the performance of our algorith m is tight (in its dependence on N), up to polylogarithmic factors. In our analysis we use techniques that were previously applied to prove fas t convergence of random walks on expander graphs. Here we use the contrapos itive statement by which slow convergence implies small cuts in the graph, and further show that these cuts have certain additional properties. This i mplication is applied in showing that for any graph, the graph vertices can be divided into disjoint subsets such that: (1) the total number of edges between the different subsets is small; and (2) each subset itself exhibits a, certain mixing property that is useful in our analysis.