Connectivity augmentation is fixed-parameter tractable
For graph theory and algorithm designers, this resolves the parameterized complexity of connectivity augmentation for general λ, and simplifies the edge case.
The paper shows that vertex connectivity augmentation is fixed-parameter tractable (FPT) when parameterized by λ and k, with a 2^{O(k log(k+λ))} n^{O(1)} algorithm, improving on prior work that only handled λ ≤ 4. It also proves edge connectivity augmentation is FPT parameterized by k alone with a 2^{O(k log k)} n^{O(1)} algorithm, removing previous assumptions.
In the vertex connectivity augmentation problem, we are given an undirected $n$-vertex graph $G$, a set of links $L \subseteq \binom{V(G)}{2} \setminus E(G)$, and integers $λ$ and $k$. The task is to insert at most $k$ links from $L$ to $G$ to make $G$ $λ$-vertex-connected. We show that the problem is fixed-parameter tractable (FPT) when parameterized by $λ$ and $k$, by giving an algorithm with running time $2^{O(k \log (k + λ))} n^{O(1)}$. This improves upon a recent result of Carmesin and Ramanujan [SODA'26], who showed that the problem is FPT parameterized by $k$ but only when $λ\le 4$. We also consider the analogous edge connectivity augmentation problem, where the goal is to make $G$ $λ$-edge-connected. We show that the problem is FPT when parameterized by $k$ only, by giving an algorithm with running time $2^{O(k \log k)} n^{O(1)}$. Previously, such results were known only under additional assumptions on the edge connectivity of $G$.