# Connectivity Oracles for Predictable Vertex Failures

arXiv: https://arxiv.org/abs/2312.08489 · HTML: https://mlsanity.com/paper/2312.08489/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 47 references that are in the map.
- First posted on arXiv 13 Dec 2023.

## Builds on (most cited first, 21 of 21)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [On Dynamic Graph Algorithms with Predictions](https://mlsanity.com/paper/2307.09961/) (2023)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)
- [Popular conjectures imply strong lower bounds for dynamic problems](https://mlsanity.com/paper/1402.0054/) (2014)
- [Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture](https://mlsanity.com/paper/1511.06773/) (2015)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning](https://mlsanity.com/paper/1611.05248/) (2016)
- [Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv](https://mlsanity.com/paper/2202.11250/) (2022)
- [Near-Optimal Deterministic Vertex-Failure Connectivity Oracles](https://mlsanity.com/paper/2205.03930/) (2022)
- [Dynamic DFS Tree in Undirected Graphs: breaking the O(m) barrier](https://mlsanity.com/paper/1502.02481/) (2015)
- [Connectivity Oracles for Graphs Subject to Vertex Failures](https://mlsanity.com/paper/1607.06865/) (2016)
- [Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity](https://mlsanity.com/paper/1611.09072/) (2016)
- [Sensitive Distance and Reachability Oracles for Large Batch Updates](https://mlsanity.com/paper/1907.07982/) (2019)
- [Fault-Tolerant Labeling and Compact Routing Schemes](https://mlsanity.com/paper/2106.00374/) (2021)
- [Algorithms and data structures for first-order logic with connectivity under vertex failures](https://mlsanity.com/paper/2111.03725/) (2021)
- [~Optimal Dual Vertex Failure Connectivity Labels](https://mlsanity.com/paper/2208.10168/) (2022)
- [Deterministic Fault-Tolerant Connectivity Labeling Scheme](https://mlsanity.com/paper/2208.11459/) (2022)
- [Connectivity Queries under Vertex Failures: Not Optimal, but Practical](https://mlsanity.com/paper/2305.01756/) (2023)
- [Connectivity Labeling and Routing with Multiple Vertex Failures](https://mlsanity.com/paper/2307.06276/) (2023)

## Built on by (most cited first, 1 of 1)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)

## Abstract (arXiv)

The problem of designing connectivity oracles supporting vertex failures is one of the basic data structures problems for undirected graphs. It is already well understood: previous works [Duan--Pettie STOC'10; Long--Saranurak FOCS'22] achieve query time linear in the number of failed vertices, and it is conditionally optimal as long as we require preprocessing time polynomial in the size of the graph and update time polynomial in the number of failed vertices. We revisit this problem in the paradigm of algorithms with predictions: we ask if the query time can be improved if the set of failed vertices can be predicted beforehand up to a small number of errors. More specifically, we design a data structure that, given a graph G=(V,E) and a set of vertices predicted to fail widehatD subseteq V of size d=|widehatD|, preprocesses it in time tildeO(d|E|) and then can receive an update given as the symmetric difference between the predicted and the actual set of failed vertices widehatD triangle D = (widehatD setminus D) cup (D setminus widehatD) of size η = |widehatD triangle D|, process it in time tildeO(η4), and after that answer connectivity queries in G setminus D in time O(η). Viewed from another perspective, our data structure provides an improvement over the state of the art for the fully dynamic subgraph connectivity problem in the sensitivity setting [Henzinger--Neumann ESA'16]. We argue that the preprocessing time and query time of our data structure are conditionally optimal under standard fine-grained complexity assumptions.