An algorithm for (n-3)-connectivity augmentation problem: Jump system approach

We consider the problem of making a given (k - 1)-connected graph k-connected by adding a minimum number of new edges, which we call the k-connectivity augmentation problem. In this paper, we deal with the problem when k = n - 3 where n is the number of vertices of the input graph. By considering the complement graph, the (n - 3)-connectivity augmentation problem can be reduced to the problem of finding a maximum square-free 2-matching in a simple graph with maximum degree at most three. We give a polynomial-time algorithm to find a maximum square-free 2-matching in a simple graph with maximum degree at most three, which yields a polynomial-time algorithm for the (n - 3)-connectivity augmentation problem. Our algorithm is based on the fact that the square-free 2-matchings are endowed with a matroid structure called a jump system. We also show that the weighted (n - 3)-connectivity augmentation problem can be solved in polynomial time if the weights are induced by a function on the vertex set, whereas the problem is NP-hard for general weights. (C) 2011 Elsevier Inc. All rights reserved.