Independence Free Graphs and Vertex Connectivity Augmentation

Tibor Jordán Department of Operations Research Eötvös University, Budapest

October 30, 2000

Abstract

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 are known only for k ≤ 4 and a major open question in graph connectivity is whether this problem is solvable in polynomial time in general.

I’ll present some recent results on this problem. Together with Bill Jackson we have developed an algorithm for finding an optimal solution to the augmentation problem and a min-max formula which determines the size of an optimal solution. The running time of the algorithm is polynomial for fixed values of k and the min-max formula applies when the size of an optimal solution is large compared to k. A key step in our proofs is the complete solution of the problem for a new family of graphs which we call k-independence free graphs. email: jordan@cs.elte.hu