2023/06/30 by Saranurak, Thatchaphol, Yuan, Wuwei
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2307.00147
We give the first almost-linear time algorithm for computing the maximal k-edge-connected subgraphs of an undirected unweighted graph for any constant k. More specifically, given an n-vertex m-edge graph G=(V,E) and a number k = logo(1)n, we can deterministically compute in O(m+n1+o(1)) time the unique vertex partition \V1,…,Vz\ such that, for every i, Vi induces a k-edge-connected subgraph while every superset V'i⊃ Vi does not. Previous algorithms with linear time work only when k≤2 [Tarjan SICOMP'72], otherwise they all require Ω(m+n√(n)) time even when k=3 [Chechik~et~al.~SODA'17; Forster~et~al.~SODA'20]. Our algorithm also extends to the decremental graph setting; we can deterministically maintain the maximal k-edge-connected subgraphs of a graph undergoing edge deletions in m1+o(1) total update time. Our key idea is a reduction to the dynamic algorithm supporting pairwise k-edge-connectivity queries [Jin and Sun FOCS'20].