Cut-Matching Games for Bipartiteness Ratio of Undirected Graphs

We propose an O(log n)-approximation algorithm for the bipartiteness ratio for undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where n is the number of vertices. Our approach extends the cut-matching game framework for sparsest cut to the bipartiteness ratio. Our algorithm requires only polylog n many single-commodity undirected maximum flow computations. Therefore, with the current fastest undirected max-flow algorithms, it runs in nearly linear time. Along the way, we introduce the concept of well-linkedness for skew-symmetric graphs and prove a novel characterization of bipartitness ratio in terms of well-linkedness in an auxiliary skew-symmetric graph, which may be of independent interest. As an application, we devise an Õ(mn)-time algorithm that given a graph whose maximum cut deletes a $1-η$ fraction of edges, finds a cut that deletes a 1 - O(log n log(1/η)) · η fraction of edges, where m is the number of edges.