2-Node-Connectivity Network Design

We consider network design problems in which we are given a graph G= (V, E) with edge costs, and seek a min-cost/size 2-node-connected subgraph G^′= (V^′, E^′) that satisfies a prescribed property. In the Block-Tree Augmentation problem the goal is to augment a tree T by a min-size edge set F⊆ E such that G^′= T∪ F is 2-node-connected. We break the natural ratio of 2 for this problem and show that it admits approximation ratio 1.91. This result extends to the related Crossing Family Augmentation problem.In the 2-Connected Dominating Set problem G^′ should dominate V. We give the first non-trivial approximation algorithm for this problem, with expected ratio O~ (log⁴| V| ).In the 2-Connected Quota Subgraph problem we are given node profits p(v) and G^′ should have profit at least a given quota Q. We show expected ratio O~ (log²| V| ), almost matching the best known ratio O(log²| V| ). Our algorithms are very simple, and they combine three main ingredients: 1.A probabilistic spanning tree embedding with distortion O~ (log | V| ) results in a variant of the Block-Tree Augmentation problem.2.An approximation ratio preserving reduction of Block-Tree Augmentation variants to Node Weighted Steiner Tree problems.3.Using existing approximation algorithms for variants of the Node Weighted Steiner Tree problem.