Connectivity augmentation is fixed-parameter tractable

Abstract

In the vertex connectivity augmentation problem, we are given an undirected $n$-vertex graph $G$, a set of links $L\subseteq \left(\genfrac{}{}{0ex}{}{V(G)}{2}\right)\setminus E(G)$, and integers $\hat{I}»$ and $k$. The task is to insert at most $k$ links from $L$ to $G$ to make $G$ $\hat{I}»$-vertex-connected. We show that the problem is fixed-parameter tractable (FPT) when parameterized by $\hat{I}»$ and $k$, by giving an algorithm with running time $2^{O(k\log (k+\hat{I}»))}{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 $\hat{I}»\le 4$. We also consider the analogous edge connectivity augmentation problem, where the goal is to make $G$ $\hat{I}»$-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$.

16 pages