Incremental Exact Vertex Connectivity

Abstract

We study the problem of maintaining the vertex connectivity $\kappa$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O({\kappa }^4{\log }^{2}n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $\kappa$, plus a set of $\kappa$ 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 $\kappa$. Previously, algorithms for maintaining the vertex connectivity with $o(n)$ time per edge insertion were only known for $\kappa \le 2$, and need $\tilde{O}({\log }^{2}n)$ and $O(\sqrt{n})$ time per edge insertion for $\kappa =1,2$, respectively. Moreover, for $\kappa >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 $\kappa$ after every insertion needs $\Omega (n^{1-\epsilon })$ amortized time per edge insertion for $\kappa =\Theta (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.

To appear at SODA 2027