2026-07-22T14:20:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18058 2024-03-06T11:00:54Z ddc:004 open_access

Optimal Decremental Connectivity in Non-Sparse Graphs Aamand, Anders Karczmarz, Adam Łącki, Jakub Parotsidis, Nikos Rasmussen, Peter M. R. Thorup, Mikkel decremental connectivity dynamic connectivity We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in O(m + n poly log n) total time. Interspersed with the deletions, it can answer queries whether any two given vertices currently belong to the same (2-edge-)connected component in constant time. Our result is based on a general Monte-Carlo randomized reduction from decremental c-edge-connectivity to a variant of fully-dynamic c-edge-connectivity on a sparse graph. For non-sparse graphs with Ω(n poly log n) edges, our connectivity and 2-edge-connectivity algorithms handle all deletions in optimal linear total time, using existing algorithms for the respective fully-dynamic problems. This improves upon an O(m log (n² / m) + n poly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n²) edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an Ω(log n/log log n) worst-case time lower bound in the decremental setting [Alstrup, Husfeldt, and Rauhe FOCS'98] as well as an Ω(log n) amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC'04]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anders Aamand and Adam Karczmarz and Jakub Łącki and Nikos Parotsidis and Peter M. R. Rasmussen and Mikkel Thorup 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.6 urn:nbn:de:0030-drops-180581 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.6 eng https://creativecommons.org/licenses/by/4.0/legalcode