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.1.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.2. 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~4 |V|).3. In the 2-CONNECTED QUOTA SUBGRAPH problem we are given node profits p(ⅴ) and G′ should have profit at least a given quota Q. We show expected ratio O(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 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.