A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
Authors:
- 1 November 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1158-1167
Abstract
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 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(logn), computes a (logm) r2 -approximation for Minimum Balanced Cut in G, in time O(m 1+O(1/r)+o(1) ·(logm) O(r2 )). In particular, we obtain a (logm) 1/ε -approximation in time m 1+O(√{ε}) for any constant , and a (logm) f(m) -approximation in time m 1+o(1) , for any slowly growing function f(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 n o(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.Keywords
All Related Versions
Funding Information
- European Research Council (ERC)
- Swedish Research Council (2015-04659)
- NSF (CCF-1616584,CCF-1718533,CCF-1907820)
This publication has 53 references indexed in Scilit:
- $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ TimeSIAM Journal on Computing, 2010
- Graph partitioning using single commodity flowsJournal of the ACM, 2009
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Faster approximation schemes for fractional multicommodity flow problemsACM Transactions on Algorithms, 2008
- Using PageRank to Locally Partition a GraphInternet Mathematics, 2007
- Randomized fully dynamic graph algorithms with polylogarithmic time per operationJournal of the ACM, 1999
- Beyond the flow decomposition barrierJournal of the ACM, 1998
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981