A Branch-and-Cut-and-Price Algorithm for Vertex-Biconnectivity Augmentation

In this article, the first approach for solving the vertex-biconnectivity augmentation problem (V2AUG) to optimality is proposed. Given a spanning subgraph of an edge-weighted graph, we search for the cheapest subset of edges to augment this subgraph to make it vertex-biconnected. The problem is reduced to augmentation of the corresponding block-cut tree [Khuller and Thummella, J Algorithms 14 (1993), 214-225], and its connectivity properties are exploited to develop two minimum-cut-based ILP formulations: a directed and an undirected one. In contrast to the recently obtained result for the more general vertex-biconnected Steiner network problem [Chimani et al., Proceedings of 2nd Annual International Conference on Combinatorial Optimization and Applications, Lecture Notes in Computer Science, Vol. 5165, Springer, 2008, pp. 190-200.], our theoretical comparison shows that orienting the undirected graph does not help in improving the quality of lower bounds. Hence, starting from the undirected cut formulation, we develop a branch-and-cut-and-price (BCP) algorithm which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of BCP: complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than state-of-the-art metaheuristics and approximation algorithms, for graphs up to 200 vertices. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported. (C) 2009 Wiley Periodicals, Inc. NETWORKS, Vol. 56(3), 169-182 2010