O(log n)-Approximation Algorithms for Bipartiteness Ratio
2025/07/17 by Tasuku Soma, Soma, Tasuku, Mingquan Ye +3
Computer Science · Decision Sciences · #Advanced Graph Theory Research #Optimization and Search Problems #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2507.12847
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 \mathoppolylog 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 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/η)) ⋅ η 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.
Citations
- The dual Cheeger-Buser inequality for graphons
- Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
- New Structures and Algorithms for Length-Constrained Expander Decompositions
- A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths
- Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game
- A Cut-Matching Game for Constant-Hop Expanders
- A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems
- Sublinear-Time Clustering Oracle for Signed Graphs
- Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
- Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
- Deterministic Decremental SSSP and Approximate Min-Cost Flow in\n Almost-Linear Time
- Deterministic Decremental Reachability, SCC, and Shortest Paths via\n Directed Expanders and Congestion Balancing
- Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
- The Expander Hierarchy and its Applications to Dynamic Graph Algorithms
- A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
- Expander Decomposition and Pruning: Faster, Stronger, and Simpler
- Solving Linear Programs in the Current Matrix Multiplication Time
- Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
- A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
- Routing in Undirected Graphs with Constant Congestion
- Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
- Cut-Matching Games on Directed Graphs
- Breaking the Multicommodity Flow Barrier for sqrt(log(n))-Approximations to Sparsest Cut
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Related