Algorithm tracks graph vertex connectivity quickly as edges are added
Incremental Exact Vertex Connectivity
Data Structures and Algorithms
Summary
This paper addresses how to keep track of a graph’s vertex connectivity—a number showing how many vertices need to be removed to break the graph apart—as new edges are added. The authors present an algorithm that updates this connectivity information much faster than previously known methods, especially for larger connectivity values. Their algorithm not only reports the current connectivity but also identifies a specific set of vertices whose removal disconnects the graph. They also provide evidence that any algorithm outputting connectivity after each edge insertion must take a significant amount of time when connectivity is very large.
What this means in practice
- •For network reliability engineers: Improve real-time monitoring of critical nodes in communication networks as new connections form.
- •For graph database maintainers: Efficiently update connectivity information in dynamic graph datasets during incremental edge additions.
Authors
Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann
Abstract
We study the problem of maintaining the vertex connectivity $κ$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O(κ^4 \log^2 n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $κ$, plus a set of $κ$ vertices whose removal disconnects the graph. Our algorithm is Monte-Carlo randomized and works with a randomness-adaptive adversary. The algorithm also works on directed graphs against an oblivious adversary, which is equivalent to an output-adaptive adversary if we only have to output the current value of $κ$. Previously, algorithms for maintaining the vertex connectivity with $o(n)$ time per edge insertion were only known for $κ\le 2$, and need $\tilde{O}(\log^2 n)$ and $O(\sqrt{n})$ time per edge insertion for $κ= 1,2$, respectively. Moreover, for $κ> 4$, no algorithm faster than recomputation from scratch was known. We complement our algorithm with a conditional lower bound: Under the OMv conjecture, any insertions-only algorithm that outputs the current value of $κ$ after every insertion needs $Ω(n^{1-\varepsilon})$ amortized time per edge insertion for $κ= Θ(n)$. Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.