A Single-Exponential FPT Algorithm for 2-Vertex-Connectivity Augmentation

Abstract

We study restricted-link augmentation to $2$-vertex-connectivity. An instance consists of a graph $G$, possibly disconnected, a set $L$ of admissible links on its vertices, integer link costs in $\{1,\dots,W\}$, and an integer $k$; the task is to add at most $k$ links of minimum total cost so that the resulting multigraph is $2$-vertex-connected. Recent work gives $O^*(k^{O(k)})$-time algorithms for unweighted $\lambda$-vertex-connectivity augmentation for every $\lambda\leq 4$ [Carmesin and Ramanujan, SODA 2026], and an $O^*((k+\lambda)^{O(k)})$-time algorithm for arbitrary $\lambda$ [Korhonen and Thorup, arXiv 2026]. We give a deterministic algorithm with running time $O^*(36^kW)$. Thus, for $\lambda=2$, the unweighted running time improves from $O^*(k^{O(k)})$ to $O^*(36^k)$, and the algorithm also handles link costs with pseudo-polynomial dependence on $W$. We reduce the problem to a boundary-pair variant of $2$-vertex-connected spanning subgraph, where each vertex is assigned a pair of incident edges with an associated pair cost. We solve this variant using a cancellation identity, inspired by Cut&Count [Cygan et al., TALG 2022], obtained by applying M\"obius inversion to decompositions along cut vertices: the identity cancels every connected spanning graph with more than one block and keeps exactly the $2$-vertex-connected spanning graphs.