# Maximal $k$-Edge-Connected Subgraphs in Almost-Linear Time for Small $k$

Preprint · Thatchaphol Saranurak, Wuwei Yuan

- Archive id: arxiv:2307.00147
- Published: 2023-06-30
- arXiv: https://arxiv.org/abs/2307.00147
- Source URL: https://arxiv.org/abs/2307.00147
- PDF: https://arxiv.org/pdf/2307.00147
- Provenance: arxiv

## Abstract

We give the first almost-linear time algorithm for computing the \\emph{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},\\dots,V\_{z}\\}$ such that, for every $i$, $V\_{i}$ induces a $k$-edge-connected subgraph while every superset $V'\_{i}\\supset V\_{i}$ does not. Previous algorithms with linear time work only when $k\\le2$ {\[}Tarjan SICOMP'72{\]}, otherwise they all require $Ω(m+n\\sqrt{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{\]}.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.