2023/08/09 by Nalam, Chaitanya, Saranurak, Thatchaphol, Yingchareonthawornchai, Sorrachai · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2308.04695
An n-vertex m-edge graph is k-vertex connected if it cannot be disconnected by deleting less than k vertices. After more than half a century of intensive research, the result by [Li et al. STOC'21] finally gave a randomized algorithm for checking k-connectivity in near-optimal \widehatO(m) time. (We use \widehatO(⋅) to hide an no(1) factor.) Deterministic algorithms, unfortunately, have remained much slower even if we assume a linear-time max-flow algorithm: they either require at least Ω(mn) time [Even'75; Henzinger Rao and Gabow, FOCS'96; Gabow, FOCS'00] or assume that k=o(√(log n)) [Saranurak and Yingchareonthawornchai, FOCS'22]. We show a deterministic algorithm for checking k-vertex connectivity in time proportional to making \widehatO(k2) max-flow calls, and, hence, in \widehatO(mk2) time using the deterministic max-flow algorithm by [Brand et al. FOCS'23]. Our algorithm gives the first almost-linear-time bound for all k where √(log n)≤ k≤ no(1) and subsumes up to a sub polynomial factor the long-standing state-of-the-art algorithm by [Even'75] which requires O(n+k2) max-flow calls. Our key technique is a deterministic algorithm for terminal reduction for vertex connectivity: given a terminal set separated by a vertex mincut, output either a vertex mincut or a smaller terminal set that remains separated by a vertex mincut. We also show a deterministic (1+ε)-approximation algorithm for vertex connectivity that makes O(n/ε2) max-flow calls, improving the bound of O(n1.5) max-flow calls in the exact algorithm of [Gabow, FOCS'00]. The technique is based on Ramanujan graphs.