2021/11/03 by Gálvez, Waldo, Sanhueza-Matamala, Francisco, Soto, José A. · 1 citation
#68W25 #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2111.02234
Given a k-vertex-connected graph G and a set S of extra edges (links), the goal of the k-vertex-connectivity augmentation problem is to find a set S' ⊆ S of minimum size such that adding S' to G makes it (k+1)-vertex-connected. Unlike the edge-connectivity augmentation problem, research for the vertex-connectivity version has been sparse. In this work we present the first polynomial time approximation algorithm that improves the known ratio of 2 for 2-vertex-connectivity augmentation, for the case in which G is a cycle. This is the first step for attacking the more general problem of augmenting a 2-connected graph. Our algorithm is based on local search and attains an approximation ratio of 1.8704. To derive it, we prove novel results on the structure of minimal solutions.