2019/10/17 by Yu Gao, Gao, Yu, Jason Li +9
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1910.07950
openalex publication_date 2019/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study deterministic algorithms for computing graph cuts, with focus on two fundamental problems: balanced sparse cut and k-vertex connectivity for small k (k=O(\polylog n)). Both problems can be solved in near-linear time with randomized algorithms, but their previous deterministic counterparts take at least quadratic time. In this paper, we break this bound for both problems. Interestingly, achieving this for one problem crucially relies on doing so for the other. In particular, via a divide-and-conquer argument, a variant of the cut-matching game by [Khandekar et al.`07], and the local vertex connectivity algorithm of [Nanongkai et al. STOC'19], we give a subquadratic time algorithm for k-vertex connectivity using a subquadratic time algorithm for computing balanced sparse cuts on sparse graphs. To achieve the latter, we improve the previously best mn bound for approximating balanced sparse cut for the whole range of m. This starts from (1) breaking the n3 barrier on dense graphs to nω+ o(1) (where ω< 2.372) using the the PageRank matrix, but without explicitly sweeping to find sparse cuts; to (2) getting the O(m1.58) bound by combining the J-trees by [Madry FOCS `10] with the nω+ o(1) bound above, and finally; to (3) getting the m1.5 + o(1) bound by recursively invoking the second bound in conjunction with expander-based graph sparsification. Interestingly, our final m1.5 + o(1) bound lands at a natural stopping point in the sense that polynomially breaking it would lead to a breakthrough for the dynamic connectivity problem.