# A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

arXiv: https://arxiv.org/abs/1910.08025 · HTML: https://mlsanity.com/paper/1910.08025/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2019.

## Built on by (most cited first, 3 of 3)

- [ℓ2-norm Flow Diffusion in Near-Linear Time](https://mlsanity.com/paper/2105.14629/) (2021)
- [Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser](https://mlsanity.com/paper/2305.06541/) (2023)
- [Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues](https://mlsanity.com/paper/2306.09128/) (2023)

## Abstract (arXiv)

We consider the classical Minimum Balanced Cut problem: given a graph G, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first em deterministic, almost-linear time approximation algorithm for this problem. Specifically, our algorithm, given an n-vertex m-edge graph G and any parameter 1≤ r≤ O(log n), computes a (log m)r2-approximation for Minimum Balanced Cut on G, in time Oleft ( m1+O(1/r)+o(1)· (log m)O(r2)right ). In particular, we obtain a (log m)1/ε-approximation in time m^1+O(1/√ε) for any constant ε, and a (log m)f(m)-approximation in time m1+o(1), for any slowly growing function m. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of G that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an n-vertex graph is no(1), thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in n factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.