2-node-connectivity network design

02/10/2020
by   Zeev Nutov, et al.
0

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 Õ(log^4 |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 Õ(log^2|V|), almost matching the best known ratio O(log^2|V|). Our algorithms are very simple, and they combine three main ingredients. 1. A probabilistic spanning tree embedding with distortion Õ(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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset