Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning sub graph problem, assuming that the number of nodes is at least k3(k-1)+k. We apply a combinatorial preprocessing, based on the Frank-Tardos algorithm for k-out connectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant-factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of k.

Authors

• Joseph Cheriyan
• László A. Végh

Keywords

• Costs
• Approximation algorithms
• Iterative algorithms
• Standards
• Directed graphs
• Transforms
• Linear programming
• Switches
• Polynomials
• Optimization
• Estimation Algorithm
• Iterative Rounds
• Running Time
• Unique Set
• Proof Of Theorem
• Undirected
• Root Node
• Directed Graph
• Basic Solution
• Algorithm For Problem
• Demand Function
• Multiple Edges
• Graph Properties
• Constant Approximation
• Linear Programming Relaxation
• Graph connectivity
• Iterative rounding