DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.92

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

Authors: Thatchaphol Saranurak and Wuwei Yuan

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

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].

Cite as

Thatchaphol Saranurak and Wuwei Yuan. Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 92:1-92:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{saranurak_et_al:LIPIcs.ESA.2023.92,
  author =	{Saranurak, Thatchaphol and Yuan, Wuwei},
  title =	{{Maximal k-Edge-Connected Subgraphs in Almost-Linear Time for Small k}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{92:1--92:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.92},
  URN =		{urn:nbn:de:0030-drops-187451},
  doi =		{10.4230/LIPIcs.ESA.2023.92},
  annote =	{Keywords: Graph algorithms, Maximal k-edge-connected subgraphs, Dynamic k-edge connectivity}
}

Search Results

Documents authored by Yuan, Wuwei

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

Abstract

Cite as

Thanks for your feedback!

Could not send message