Node connectivity augmentation via iterative randomized rounding
Haris Angelidakis, Dylan Hyatt-Denesik, Laura Sanità
Abstract
Abstract Many network design problems deal with the design of low-cost networks that are resilient to the failure of their elements (such as nodes or links). One such problem is Connectivity Augmentation, with the goal of cheaply increasing the (edge- or node-)connectivity of a given network from a value k to $$k+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> . The problem is NP-hard for $$k \ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>≥</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> , and the most studied setting focuses on the case of edge-connectivity with $$k=1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> . In this work, we give a 1.892-approximation algorithm for the NP-hard problem of augmenting the node-connectivity of any given graph from 1 to 2, which improves upon the state-of-the-art approximation previously developed in the literature. The starting point of our work is a known reduction from Connectivity Augmentation to some specific instances of the Node-Steiner Tree problem, and our result is obtained by developing a new and simple analysis of the iterative randomized rounding technique when applied to such Steiner Tree instances. Our results also imply a 1.892-approximation algorithm for the problem of augmenting the edge-connectivity of a given graph from any value k to $$k+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>k</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:math> . While this does not beat the best approximation factor known for this problem, a key point of our work is that the analysis of our approximation factor is less involved when compared to previous results in the literature. In addition, our work gives new insights on the iterative randomized rounding method, that might be of independent interest.