In this paper, 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 in order to make it vertex-biconnected. The problem is reduced to the augmentation of the corresponding block-cut tree, whose 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, 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 algorithm (BCP) which represents the first exact approach to V2AUG. Our computational experiments show the practical feasibility of the BCP: Complete graphs with more than 400 vertices can be solved to provable optimality. Furthermore, BCP is even faster than the state-of-the-art metaheuristics and approximation algorithms, as far as graphs with up to 200 vertices are considered. For large graphs with more than 2000 vertices, optimality gaps that are strictly below 2% are reported.
Citation
Technical Report Nr. [2009-02], Department of Statistics and Decision Support Systems, Univesity of Vienna, 2009 (submitted to Networks)
Article
View A Branch-and-Cut-and-Price Algorithm for Vertex-Biconnectivity Augmentation