eng
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Leibniz International Proceedings in Informatics
1868-8969
2023-08-30
92:1
92:9
10.4230/LIPIcs.ESA.2023.92
article
Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k
Saranurak, Thatchaphol
1
https://orcid.org/0000-0001-8386-7168
Yuan, Wuwei
2
https://orcid.org/0009-0009-3611-3297
University of Michigan, Ann Arbor, MI, USA
Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China
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 = log^o(1) n, we can deterministically compute in O(m+n^{1+o(1)}) time the unique vertex partition {V_1,… ,V_z} such that, for every i, V_i induces a k-edge-connected subgraph while every superset V'_i ⊃ V_{i} 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 m^{1+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].
https://drops.dagstuhl.de/storage/00lipics/lipics-vol274-esa2023/LIPIcs.ESA.2023.92/LIPIcs.ESA.2023.92.pdf
Graph algorithms
Maximal k-edge-connected subgraphs
Dynamic k-edge connectivity