|
Published in:
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 egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2001}, |
| NUMBER | = | {TR-2001-04} |