zbMATH — the first resource for mathematics

A sublinear bipartiteness tester for bounded degree graphs. (English) Zbl 0932.68053
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 and the testing algorithm can perform queries of the form “who is the \(i\)th neighbour of vertex \(v\)”. The tester should determine with high probability whether the graph is bipartite or \(\varepsilon\)-far from bipartite for any given distance parameter \(\varepsilon\). Distance between graphs is defined to be the fraction of entries on which the graphs differ in their incidence-lists representation.” Their algorithm uses random walk technique and its performance is tight (in a sense explained in the paper).

68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI