Augmenting to 4-vertex connectivity is fixed-parameter tractable
Abstract
We present fixed-parameter algorithms (FPT algorithms) for the \(\lambda\)-vertex connectivity augmentation (\(\lambda\)-VCA) problem for all values of \(\lambda \le 4\); that is, we give an algorithm that given a graph \(G\), a set \(L\) of non-edges, and an integer \(k\), determines in time \(k^{\mathcal{O}(k)} \cdot n^{c}\) (for some constant \(c\) independent of \(k\)) whether \(G\) can be made \(\lambda\)-vertex connected by adding at most \(k\) elements from \(L\).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Distributed systems and fault tolerance
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 2015–2042
- Publication date
- 1 January 2026
- Language
- EN