TY - GEN

T1 - Optimal Decremental Connectivity in Non-Sparse Graphs

AU - Aamand, Anders

AU - Karczmarz, Adam

AU - Łącki, Jakub

AU - Parotsidis, Nikos

AU - Rasmussen, Peter M.R.

AU - Thorup, Mikkel

N1 - Publisher Copyright: © Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup.

PY - 2023

Y1 - 2023

N2 - 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 + npoly 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 Ω(npoly 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(mlog(n2/m) + npoly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n2) 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].

AB - 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 + npoly 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 Ω(npoly 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(mlog(n2/m) + npoly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n2) 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].

KW - decremental connectivity

KW - dynamic connectivity

U2 - 10.4230/LIPIcs.ICALP.2023.6

DO - 10.4230/LIPIcs.ICALP.2023.6

M3 - Article in proceedings

AN - SCOPUS:85162769409

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 17

BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

A2 - Etessami, Kousha

A2 - Feige, Uriel

A2 - Puppis, Gabriele

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

Y2 - 10 July 2023 through 14 July 2023

ER -