On four-connecting a triconnected graph

We consider the problem of finding a smallest set of edges whose addition f our-connects a triconnected graph. This is a fundamental graph-theoretic pr oblem that has applications in designing reliable networks and improving st atistical database security. We present an O(n.alpha(m, n) + m)-time algori thm for four-connecting an undirected graph G that is triconnected by addin g the smallest number of edges, where n and m are the number of vertices an d edges in G, respectively, and alpha(m, n) is the inverse Ackermann functi on. This is the first polynomial time algorithm to solve this problem exact ly. In deriving our algorithm, we present a new lower bound for the number of e dges needed to four-connect a triconnected graph. The form of this lower bo und is different from the form of the lower bound known for bioconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies fur arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k - 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algor ithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph. (C) 2000 Academic Pre ss.