License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.92
URN: urn:nbn:de:0030-drops-187451
URL: https://drops.dagstuhl.de/opus/volltexte/2023/18745/
Go to the corresponding LIPIcs Volume Portal

Saranurak, Thatchaphol ; Yuan, Wuwei

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

pdf-format:
LIPIcs-ESA-2023-92.pdf (0.7 MB)

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

BibTeX - Entry

@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/opus/volltexte/2023/18745},
  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}
}

Keywords: Graph algorithms, Maximal k-edge-connected subgraphs, Dynamic k-edge connectivity
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI