A sublinear bipartiteness tester for bounded degree graphs

Authors:
  • OGOded Goldreich
    Oded Goldreich
  • DRDana Ron
    Dana Ron

Abstract
We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartite or far frombeing bipartite. Graphs are represented by incidence lists of bounded length d, and the testing algorithmcan perform queries of the form: "who is the ith neighbor of vertex v". The tester should determine withhigh 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...