A better tester for bipartiteness?

Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of O(1/ε) vertices is bipartite with high probability. We conjecture that the induced subgraph is Ω~(ε)-far from bipartite with high probability. Gonen and Ron (RANDOM 2007) proved this conjecture in the case when the degrees of all vertices are at most O(εn). We give a more general proof that works for any d-regular (or almost d-regular) graph for arbitrary degree d. Assuming this conjecture, we prove that bipartiteness is testable with one-sided error in time O(1/ε^c), where c is a constant strictly smaller than two, improving upon the tester of Alon and Krivelevich. As it is known that non-adaptive testers for bipartiteness require Ω(1/ε^2) queries (Bogdanov and Trevisan, CCC 2004), our result shows, assuming the conjecture, that adaptivity helps in testing bipartiteness.

No reviews yet.

No comments yet.