Cut-Matching Games for Bipartiteness Ratio of Undirected Graphs

We propose an O (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 poly 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 O (mn) -time algorithm that given a graph whose maximum cut deletes a 1-η fraction of edges, finds a cut that deletes a 1 - O (n (1/η) ) η fraction of edges, where m is the number of edges.