$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio

Basic Information

• Paper ID: 2507.12847
• Title: $O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
• Authors: Tasuku Soma (The Institute of Statistical Mathematics & RIKEN AIP), Mingquan Ye (National Institute of Informatics & University of California, Santa Cruz), Yuichi Yoshida (National Institute of Informatics)
• Classification: cs.DS (Data Structures and Algorithms)
• Publication Date: November 5, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2507.12847

Abstract

This paper presents the first $O(\log n)$-approximation algorithm for the bipartiteness ratio of undirected graphs, where $n$ is the number of vertices. The approach extends the cut-matching game framework from the sparsest cut problem to the bipartiteness ratio problem, requiring only $\text{polylog } n$ single-commodity undirected maximum flow computations. Combined with the fastest undirected maximum flow algorithms, this achieves near-linear time complexity. The research introduces the concept of well-linkedness for auxiliary semi-symmetric graphs and proves a new characterization of bipartiteness ratio in terms of well-linkedness. As an application, an $\tilde{O}(mn)$-time algorithm for minimum uncut is proposed. Additionally, directed bipartiteness ratio is defined, and an $O(\log n)$-approximation algorithm is provided via directed Leighton-Rao style embeddings.

Research Background and Motivation

Problem Definition

The bipartiteness ratio problem was introduced by Trevisan Tre12. For an undirected graph $G=(V,E,w)$, it is defined as: $\beta(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \frac{\sum_{e=(i,j)\in E} w(e)\cdot|x_i+x_j|}{\sum_{i\in V} \deg(i)\cdot|x_i|}$

This ratio characterizes the deviation of a graph from bipartiteness: $\beta(G)=0$ if and only if $G$ is bipartite.

Research Significance

1. Theoretical Importance: The bipartiteness ratio is a core concept in the dual Cheeger inequality, closely related to the largest eigenvalue $\lambda_n$ of the normalized Laplacian matrix: $\frac{2-\lambda_n}{2} \leq \beta(G) \leq \sqrt{2(2-\lambda_n)}$
2. Application Value:
   • Spectral algorithm design: Trevisan utilized this inequality to design a purely spectral algorithm for maximum cut
   • Network analysis: Applications in signed graph clustering, community detection, and related areas XOG20; AL20; NP22
   • Combinatorial optimization: Close connections to classical problems like maximum cut and minimum uncut

Limitations of Existing Methods

1. Lack of Approximation Algorithms: Despite mature approximation algorithms for Cheeger inequality and sparsest cut (e.g., $O(\sqrt{\log n})$-approximation), no polynomial-time approximation algorithm existed for bipartiteness ratio
2. Insufficiency of Spectral Methods: Existing spectral methods (based on eigenvectors) only provide theoretical bounds and cannot directly solve the optimization problem
3. Differences from Sparsest Cut: Although bipartiteness ratio is formally similar to sparsest cut, its constraint structure (three-partition) makes direct application of existing techniques challenging

Research Motivation

To fill the gap in approximation algorithms for bipartiteness ratio and provide new algorithmic tools for spectral graph theory and combinatorial optimization.

Core Contributions

1. First Approximation Algorithm: Proposes the first $O(\log n)$-approximation algorithm for $b$-bipartiteness ratio with time complexity $\tilde{O}(\min\{b(V),n^2\}+m)$
2. Theoretical Innovations:
   • Introduces the concept of well-linkedness for auxiliary semi-symmetric graphs
   • Proves an equivalence characterization of bipartiteness ratio in terms of well-linkedness of auxiliary graph $G'$ (Theorem 3.5)
   • Extends the cut-matching game framework from sparsest cut to bipartiteness ratio
3. Minimum Uncut Application: Designs an $\tilde{O}(mn)$-time algorithm that, for graphs with minimum uncut ratio $\eta$, finds a cut with uncut ratio $O(\log n\log(1/\eta))\cdot\eta$
4. Directed Extension:
   • Defines directed bipartiteness ratio and its submodular function characterization
   • Achieves $O(\log n)$-approximation via directed $\ell_1$ embedding
   • Provides directed minimum uncut algorithm

Detailed Methodology

Task Definition

$b$-bipartiteness ratio: Given an undirected graph $G=(V,E,w)$ and positive vertex weights $b:V\to\mathbb{Z}_{++}$, define: $\beta_b(G) := \min_{x\in\{0,\pm1\}^V\setminus\{0\}} \beta_b(x), \quad \beta_b(x) := \frac{\sum_{(i,j)\in E} w(i,j)\cdot|x_i+x_j|}{\sum_{i\in V} b(i)\cdot|x_i|}$

Input: Graph $G$, edge weights $w$, vertex weights $b$, parameter $r>0$
Output: Vector $x\in\{0,\pm1\}^V$ such that $\beta_b(x)\leq O(\log n)\cdot\beta_b(G)$

Core Technical Framework

1. Auxiliary Graph Construction

Construct a semi-symmetric bipartite graph $G'=(V^+\cup V^-,E')$:

• $V^+,V^-$ are two disjoint copies of $V$
• For each edge $(i,j)\in E$, add edges $(i^+,j^-)$ and $(i^-,j^+)$ to $E'$
• Inherit edge weights and vertex weights

Key Property (Lemma 3.2): For any $x\in\{0,\pm1\}^V$ corresponding to a three-partition $(L,R,Z)$, let $S=L^+\cup R^-$, then: $\beta_b(x) = \frac{w(E'(S,\bar{S}))}{b(S)}$

Therefore: $\beta_b(G) = \min_{S=L^+\cup R^-, \text{ disjoint }L,R\subseteq V} \frac{w(E'(S,\bar{S}))}{b(S)}$

2. Well-Linkedness Characterization

Definition (Symmetric source-sink pair): $(A,B)$ is called symmetric if there exist disjoint $L,R\subseteq V$ such that: $A = L^+\cup R^-, \quad B = L^-\cup R^+$

Definition 3.3 (Well-linkedness): A symmetric pair $(A,B)$ is called $r$-well-linked if the auxiliary network $\mathcal{N}_{A,B,r}$ admits a saturating flow from $s^+$ to $s^-$, where:

• Edge capacities: capacity from $s^+$ to each vertex $u$ in $A$ is $b(u)$; similarly for $B$ to $s^-$
• Capacity of edge $e$ in $E'$ is $w(e)/r$

$G'$ is called $r$-well-linked if all symmetric pairs are $r$-well-linked.

Theorem 3.5 (Core Characterization): $\beta_b(G)\geq r$ if and only if $G'$ is $r$-well-linked.

Proof Sketch:

• (⇒) If $\beta_b(G)\geq r$, then for any symmetric pair $(A,B)$, the minimum $s^+$-$s^-$ cut value $\geq b(A)$; by max-flow min-cut theorem, a saturating flow exists
• (⇐) If some symmetric pair $(A,B)$ is not $r$-well-linked, then the minimum cut corresponds to a consistent set $S$ satisfying $w(E'(S,\bar{S}))/b(S)<r$

3. Cut-Matching Game

Game Framework (Algorithm 1):

• Maintain: MMWU density matrix $X_t$, empty multigraph $H$
• Each round:
  1. Cut player: Compute (approximate) Gram decomposition $\{v_i\}$ of $D_b^{-1/2}X_tD_b^{-1/2}$
  2. Sample Gaussian vector $g\sim\mathcal{N}(0,I_n)$, compute $\tilde{v}_i=\langle g,v_i\rangle$
  3. Let $L'=\{i:\tilde{v}_i>0\}$, $R'=\{i:\tilde{v}_i<0\}$, take the larger as $L$, set $(A,B)$ as the corresponding symmetric pair
  4. Check: If $(A,B)$ is not $r$-well-linked, return the minimum cut corresponding to $x$
  5. Matching player: Otherwise find saturating flow, decompose into path multiset $\mathcal{P}_t$, demand graph is $M_t$
  6. Update $F_t = D_b^{-1/2}(D_{M_t}+A_{M_t})D_b^{-1/2}$, perform MMWU update
• Termination: After $T=O(\log^2 n)$ rounds, return $H=M_1\oplus\cdots\oplus M_T$

Key Analysis:

1. Width: $F_t\preceq 4I$ (by lemma proof)
2. Gain: $\langle F_t,X_t\rangle = \sum_{(i,j)\in M_t}\|v_i+v_j\|^2 \geq \Omega(1/\log n)$ (via Gaussian projection)
3. MMWU Bound (Lemma 3.7): $\lambda_{\min}\left(\sum_{t=1}^T F_t\right) \geq (1-\rho\delta)\sum_{t=1}^T\langle F_t,X_t\rangle - \frac{\ln n}{\delta}$
   Taking $\delta=O(1)$, $T=O(\log^2 n)$, we get $\lambda_{\min}\geq\Omega(\log n)$
4. Certificate: Lemma 3.9 proves $\beta_b(H)=\Omega(\log n)$; since $H$ can be $O(T)$-congestion embedded into $G$, we get $\beta_b(G)=\Omega(r/\log n)$

Technical Innovations

1. Exploitation of Semi-Symmetry: Through the semi-symmetric structure of auxiliary graph $G'$, the three-partition problem is transformed into a flow problem with symmetric source-sink pairs, which is the key problem reformulation
2. Consistent Cut Lemma (Lemma 3.4): Using semi-symmetry and Lemma 2.5, proves that a consistent minimum cut can always be found, simplifying the analysis
3. Gaussian Projection Technique:
   • Project high-dimensional Gram decomposition to one dimension, preserving approximation of $\|v_i+v_j\|$ (Equation 3.6)
   • Lemma 3.8 uses Laurent-Massart bound to ensure $\sum b(i)|\tilde{v}_i|^2\geq 1/2$ holds with constant probability
4. Fast Gram Decomposition (Lemma 3.11): Through JL dimensionality reduction and truncated Taylor expansion, reduces $O(n^3)$ exact decomposition to $\tilde{O}(\min\{b(V),n^2\})$

Experimental Setup

Theoretical Algorithm, No Experimental Section

This is a pure theoretical algorithm paper with main contributions in:

1. Theoretical guarantee: $O(\log n)$ approximation ratio
2. Time complexity analysis: $\tilde{O}(m)$ for original bipartiteness ratio
3. Theoretical comparison with existing methods (Table 1)

Experimental Results

Summary of Theoretical Results

Main Theorem (Theorem 3.12):

• Approximation Ratio: $O(\log n)$
• Time Complexity:
  • $O(\log^3 n\cdot\max\{\log^2 n,\log b(V)\}\cdot\min\{b(V),n^2\})$ arithmetic operations
  • $O(\log^2 n)$ single-commodity maximum flow computations
• Success Probability: $\geq 1-1/\text{poly}(n)$

Minimum Uncut Application (Theorem 4.1):

• Input: Graph with minimum uncut ratio $\eta$
• Output: Cut with uncut ratio $\leq O(\log n\log(1/\eta))\cdot\eta$
• Time: $\tilde{O}(mn)$

Comparative Analysis (Table 1):

Advantages:

• Compared to spectral methods Tre12, KLLO+13: Independent of eigenvalues, better approximation ratio
• Compared to SDP methods GVY93, ACMM05: Although approximation ratio is slightly weaker, time reduces from $\tilde{O}(m^\omega)$ to $\tilde{O}(mn)$ ($\omega\approx 2.37$)

Directed Graph Extension

Directed Bipartiteness Ratio (Equation 1.3): $\beta_b(x) = \frac{\sum_{(i,j)\in E}\psi_{ij}(x)}{\sum_i b(i)|x_i|}, \quad \psi_{ij}(x)=\begin{cases}|x_i+x_j| & x_i\geq x_j\\ |x_i|+|x_j| & \text{otherwise}\end{cases}$

Theorem 1.3: Polynomial-time $O(\log n)$-approximation algorithm via:

1. Constructing auxiliary semi-symmetric gadget graph $G'$
2. Solving directed semi-metric relaxation (LP)
3. Directed $\ell_1$ weak embedding CMM06 achieving $O(\log|V'|)=O(\log n)$ approximation

Theorem 1.4: $O(\log n\log(1/\eta))\cdot\eta$-approximation for directed minimum uncut

Related Work

Spectral Graph Theory

1. Cheeger Inequality AM85; Alo86: Relates second smallest eigenvalue $\lambda_2$ to conductance $\phi(G)$: $\frac{\lambda_2}{2}\leq\phi(G)\leq\sqrt{2\lambda_2}$
2. Dual Cheeger Inequality Tre12; BJ13: Relationship between bipartiteness ratio studied in this work and largest eigenvalue $\lambda_n$
3. Higher-Order Spectral Methods KLLO+13; GS11: Utilize multiple eigenvalues for improved approximation

Sparsest Cut Algorithms

1. Combinatorial Methods:
   • Cut-matching game KRV06: $O(\log^2 n)$
   • Improvement OSVV08: $O(\log n)$
   • Optimal AK16: $O(\sqrt{\log n})$ via MMWU
2. SDP Method ARV09: $O(\sqrt{\log n})$ via metric embedding
3. Directed Graphs Lou10; LTW24: $O(\log n)$-approximation for directed sparsest cut

Maximum Cut/Minimum Uncut

1. Approximation Algorithms:
   • GW algorithm GW94: $0.878$-approximation (SDP)
   • Spectral methods Tre12; KLLO+13: Dependent on eigenvalues
   • SDP hierarchy GS11; ACMM05: Stronger but slower
2. This Work's Contribution: First application of cut-matching game to bipartiteness ratio, achieving near-linear time

Conclusions and Discussion

Main Conclusions

1. First polynomial-time $O(\log n)$-approximation algorithm for bipartiteness ratio
2. Introduces well-linkedness for auxiliary semi-symmetric graphs, establishing new flow-cut characterization
3. Achieves near-linear time $\tilde{O}(m)$, significantly better than SDP methods
4. Successfully extends to directed graphs, providing unified framework

Limitations

1. Approximation Ratio: $O(\log n)$ weaker than SDP's $O(\sqrt{\log n})$ ARV09; ACMM05
2. Minimum Uncut: Additional $\log(1/\eta)$ factor; compared to ACMM05's $O(\sqrt{\log n})\cdot\eta$, there is a gap
3. Directed Graph Time: Directed version still requires polynomial time (not near-linear), dependent on LP solving
4. Practical Performance: Pure theoretical results without experimental validation

Future Directions

1. Improved Approximation Ratio: Can we achieve $O(\sqrt{\log n})$ while maintaining near-linear time?
2. Directed Graph Acceleration: Can directed bipartiteness ratio approximation also be reduced to $\tilde{O}(m)$ time?
3. Lower Bounds: Is $O(\log n)$ an inherent barrier for flow-based methods?
4. Practical Applications: Empirical studies in network analysis and community detection

In-Depth Evaluation

Strengths

1. Theoretical Breakthrough:
   • Resolves a long-standing open problem (no approximation algorithm since 2012)
   • First to establish equivalence characterization of bipartiteness ratio and well-linkedness (Theorem 3.5)
   • Elegantly unifies undirected and directed cases
2. Technical Innovation:
   • Semi-Symmetry Exploitation: Auxiliary graph construction cleverly transforms three-partition into symmetric flow problem
   • MMWU Analysis: Creatively applies AK16 framework to new problem; Gaussian projection technique handles Gram decomposition
   • Fast Implementation: Lemma 3.11's approximate Gram decomposition avoids $O(n^3)$ bottleneck
3. Algorithm Efficiency:
   • Time complexity $\tilde{O}(m)$ is near-optimal (requires reading the graph)
   • Only requires single-commodity flow, can leverage latest near-linear time algorithms CKLP+22
   • Orders of magnitude improvement over SDP methods ($\tilde{O}(m^\omega)$)
4. Theoretical Completeness:
   • Rigorous probabilistic analysis (Lemma 3.8 uses Laurent-Massart bound)
   • Detailed time complexity decomposition
   • Directed extension demonstrates framework generality

Weaknesses

1. Approximation Ratio Gap:
   • $O(\log n)$ vs. $O(\sqrt{\log n})$ ARV09: Acceptable but not optimal
   • No discussion of whether improvement is possible (e.g., via stronger SDP relaxation)
2. Missing Experiments:
   • No performance evaluation on real graphs
   • No constant factor comparison (big-O hides potentially large constants)
   • Lacks empirical comparison with spectral methods
3. Directed Graph Incompleteness:
   • Directed version time complexity not explicitly stated (Theorem 1.3 only says "polynomial time")
   • Requires LP solving, potentially slower than undirected case
   • No discussion of whether $\tilde{O}(m)$ is achievable
4. Technical Details:
   • Lemma 3.11 proof deferred to appendix; main text lacks intuition
   • Gaussian projection requires $O(\log n)$ resampling (Lemma 3.8), may impact practical performance
   • MMWU step size $\delta$ selection lacks guidance
5. Application Limitations:
   • Minimum uncut's additional $\log(1/\eta)$ factor may be significant when $\eta$ is very small
   • No discussion of practical significance of weighted version ($b$ arbitrary)

Impact

1. Theoretical Contribution:
   • Provides new algorithmic perspective for spectral graph theory
   • Well-linkedness concept for semi-symmetric graphs may have independent value
   • Demonstrates broader applicability of cut-matching game
2. Technical Impact:
   • MMWU + Gaussian projection paradigm may apply to other ratio problems
   • Fast Gram decomposition technique (Lemma 3.11) is reusable
3. Practical Value:
   • Near-linear time enables large-scale graph processing
   • May promote applications of bipartiteness ratio in network analysis
   • Directed version provides tool for directed graph community detection
4. Open Problems:
   • Motivates research on improved approximation ratios
   • Directed graph acceleration has clear value

Applicable Scenarios

1. Large-Scale Graph Analysis:
   • Quasi-bipartiteness detection in social networks
   • Structure analysis of user-item graphs in recommendation systems
2. Spectral Clustering:
   • Clustering method based on largest eigenvalue
   • Community detection in signed graphs XOG20; NP22
3. Combinatorial Optimization:
   • Preprocessing for maximum cut (via recursive bisection)
   • Heuristics for graph partitioning problems
4. Theoretical Research:
   • Benchmark for graph parameter approximation
   • New perspective on flow-cut duality

Not Applicable: Scenarios requiring $O(\sqrt{\log n})$ optimal approximation (should use SDP methods)

Selected References

1. Tre12 L. Trevisan. "Max cut and the smallest eigenvalue". SIAM J. Comput. 41.6 (2012): Defines bipartiteness ratio, proves dual Cheeger inequality
2. KRV06 R. Khandekar, S. Rao, U. Vazirani. "Graph partitioning using single commodity flows". STOC 2006: Proposes cut-matching game
3. AK16 S. Arora, S. Kale. "A combinatorial, primal-dual approach to semidefinite programs". J. ACM 63.2 (2016): MMWU framework, main technical foundation of this work
4. ACMM05 A. Agarwal et al. "$O(\sqrt{\log n})$ approximation algorithms for min uncut...". STOC 2005: SDP method for minimum uncut, main comparison point
5. CKLP+22 L. Chen et al. "Maximum flow and minimum-cost flow in almost-linear time". FOCS 2022: Near-linear time maximum flow, enables efficiency of this work's algorithm

Overall Assessment: This is a high-quality theoretical algorithm paper that resolves a long-standing open problem with significant technical innovations (semi-symmetric graph characterization, MMWU extension) and achieves near-linear time complexity. Main limitations are the suboptimal approximation ratio and lack of experimental validation. Makes important contributions to theoretical computer science and may initiate practical research on bipartiteness ratio. Recommended for publication at top-tier venues (FOCS/SODA level).