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

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

√ ǫ) for any constant ǫ, and a (log m) f (m) -approximation in time m 1+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 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.

These results were obtained independently by Chuzhoy, and the group consisting of Gao, Li, Nanongkai, Peng, and Saranurak. Chronologically, Gao et al. obtained their result in July 2019, while Chuzhoy's result was obtained in September 2019, but there was no communication between the groups until early October 2019.