{"ID":2893381,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.12847","arxiv_id":"2507.12847","title":"$O(\\log n)$-Approximation Algorithms for Bipartiteness Ratio","abstract":"We propose an $O(\\log n)$-approximation algorithm for the bipartiteness ratio of 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, and requires only $\\mathop{\\mathrm{polylog}} n$ many single-commodity undirected maximum flow computations. Therefore, with the current fastest undirected max-flow algorithms, it runs in almost linear time. Along the way, we introduce the concept of well-linkedness for skew-symmetric graphs and prove a novel characterization of bipartiteness ratio in terms of well-linkedness in an auxiliary skew-symmetric graph, which may be of independent interest. As an application, we devise an $\\tilde{O}(mn)$-time algorithm for the minimum uncut problem: given a graph whose optimal cut leaves an $η$ fraction of edges uncut, we find a cut that leaves only an $O(\\log n \\log(1/η)) \\cdot η$ fraction of edges uncut, where $m$ is the number of edges. Finally, we propose a directed analogue of the bipartiteness ratio, and we give a polynomial-time algorithm that achieves an $O(\\log n)$ approximation for this measure via a directed Leighton--Rao-style embedding. We also propose an algorithm for the minimum directed uncut problem with a guarantee similar to that for the minimum uncut problem.","short_abstract":"We propose an $O(\\log n)$-approximation algorithm for the bipartiteness ratio of 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, and requires...","url_abs":"https://arxiv.org/abs/2507.12847","url_pdf":"https://arxiv.org/pdf/2507.12847v2","authors":"[\"Tasuku Soma\",\"Mingquan Ye\",\"Yuichi Yoshida\"]","published":"2025-07-17T07:14:45Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}