Independence free graphs and vertex connectivity augmentation

Bill Jackson, Tibor Jordán

Published in:
J. Combin. Theory Ser. B 94 (2005) 31-77.


Given an undirected graph G and a positive integer k, the k-vertex-connectivity augmentation problem is to find a smallest set F of new edges for which G+F is k-vertex-connected. Polynomial algorithms for this problem have been found only for k \leq 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general.
In this paper we develop an algorithm which delivers an optimal solution in polynomial time for every fixed k. In the case when the size of an optimal solution is large compared to k, we also give a min-max formula for the size of a smallest augmenting set.
A key step in our proofs is a complete solution of the augmentation problem for a new family of graphs which we call k-independence free graphs. We also prove new splitting off theorems for vertex connectivity.

Bibtex entry:

AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor},
TITLE = {Independence free graphs and vertex connectivity augmentation},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2001},
NUMBER = {TR-2001-04}

Last modification: 29.12.2020. Please email your comments to Tamás Király!