Incremental Exact Vertex Connectivity
In the authors' words
We study the problem of maintaining the vertex connectivity of a graph under edge insertions. For undirected graphs, our algorithm uses 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 time per edge insertion were only known for , and need and time per edge insertion for , respectively. Moreover, for , 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 amortized time per edge insertion for . Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.
Appeared: Friday, October 16. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: To appear at SODA 2027