DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.139

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition

Authors: Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, and Benyu Wang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We study connectivity oracle under vertex failures, one of the most fundamental graph data structures with many applications. We provide a new deterministic connectivity oracle that handles update in O(k⁶) time and answers query in O(k) time, while using 2^O(k²) n + O(k²n α_c(n)) space and k^O(k²) n + O(m + k³ n log² n + k⁶n log n) preprocessing time. Although some previous works achieve k² ⋅ n^o(1) update time and O(k) query time [Long and Saranurak, 2022; Yaowei Long and Yunfan Wang, 2024], the update time is still n-dependent, while oracles that have n-independent update and query times [Michal Pilipczuk et al., 2022; Jan van den Brand and Thatchaphol Saranurak, 2019] cannot achieve optimal O(k) query time [Monika Henzinger et al., 2015] and often have Ω(n²) space and processing time. Our solution would be the first vertex-failure connectivity oracle that achieves O(k) query time with update time completely independent of n, while improving space usage and having competitive preprocessing time.

Cite as

Xizhe Li, Yaowei Long, David Pidugu, Thatchaphol Saranurak, and Benyu Wang. Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 139:1-139:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ICALP.2026.139,
  author =	{Li, Xizhe and Long, Yaowei and Pidugu, David and Saranurak, Thatchaphol and Wang, Benyu},
  title =	{{Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{139:1--139:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.139},
  URN =		{urn:nbn:de:0030-drops-265285},
  doi =		{10.4230/LIPIcs.ICALP.2026.139},
  annote =	{Keywords: Graphs, Fault tolerant, Oracles}
}

Search Results

Documents authored by Pidugu, David

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition

Abstract

Cite as

Thanks for your feedback!

Could not send message