[May 16, 2010]
Andrej Bogdanov
A better tester for bipartiteness?
Abstract:
Alon and Krivelevich showed that if a graph is $\epsilon$-far from bipartite,
then a subgraph induced by a random subset of about $1/\epsilon$ vertices is
likely to contain an odd length cycle. We conjecture that this subgraph is
likely to be far from bipartite. We prove the conjecture is true for regular
graphs of any degree.
Assuming this conjecture, we give an algorithm that tests bipartiteness in time
$O((1/\epsilon)^{2-c})$, where $c > 0$ is some universal constant. Our
algorithm is inherently adaptive, as it is known that non-adaptive algorithms
for testing bipartiteness require at least $(1/\epsilon)^2$ queries.
Based on joint work with Li Fan.