Tri-connectivity Augmentation in Trees

Original · EN

For a connected graph, a minimum vertex separator is a minimum set of vertices whose removal creates at least two connected components. The vertex connectivity of the graph refers to the size of the minimum vertex separator and a graph is k-vertex connected if its vertex connectivity is k, k≥ 1. Given a k-vertex connected graph G, the combinatorial problem vertex connectivity augmentation asks for a minimum number of edges whose augmentation to G makes the resulting graph (k+1)-vertex connected. In this paper, we initiate the study of r-vertex connectivity augmentation whose objective is to find a (k+r)-vertex connected graph by augmenting a minimum number of edges to a k-vertex connected graph, r ≥ 1. We shall investigate this question for the special case when G is a tree and r=2. In particular, we present a polynomial-time algorithm to find a minimum set of edges whose augmentation to a tree makes it 3-vertex connected. Using lower bound arguments, we show that any tri-vertex connectivity augmentation of trees requires at least 2l₁+l₂/2 edges, where l₁ and l₂ denote the number of degree one vertices and degree two vertices, respectively. Further, we establish that our algorithm indeed augments this number, thus yielding an optimum algorithm.