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.

• Publication year

  2012

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2012-12-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/120902847arXiv 1212.3981
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

  2014cited by this paper
• A bad example for the iterative rounding method for mincost k-connected spanning subgraphs

  2013influential reference
• An O(k3log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design

  2012cited by this paper
• Approximating k-median via pseudo-approximation

  2012influential reference
• Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

  2012cited by this paper
• Degree-Constrained Node-Connectivity

  2012influential reference
• Approximating minimum-cost edge-covers of crossing biset-families

  2012influential reference
• Simpler analysis of LP extreme points for traveling salesman and survivable network design problems

  2010influential reference
• Rooted k-connections in digraphs

  2009influential reference
• An almost O(log k)-approximation for k-connected subgraphs

  2009influential reference
• Network design for vertex connectivity

  2008cited by this paper
• Additive approximation for bounded degree survivable network design

  2008cited by this paper
• An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem

  2008cited by this paper
• Survivable network design with degree or order constraints

  2007cited by this paper
• Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems

  2006influential reference
• Approximating k-node Connected Subgraphs via Critical Graphs

  2005influential reference
• Proof of Theorem 4

  2005cited by this paper
• An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph

  2003influential reference
• Approximating Node Connectivity Problems via Set Covers

  2003influential reference
• Independence Free Graphs and Vertex Connectivity Augmentation

  2002cited by this paper
• Hardness of Approximation for Vertex-Connectivity Network Design Problems

  2002cited by this paper
• A 2-approximation for Minimum Cost {0, 1, 2} Vertex Connectivity

  2001cited by this paper
• Integer Programming and Combinatorial Optimization

  2001cited by this paper
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

  2000cited by this paper
• A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time

  2000cited by this paper
• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

  1998influential reference
• Improved approximation algorithms for uniform connectivity problems

  1995cited by this paper
• Minimal Edge-Coverings of Pairs of Sets

  1995influential reference
• Approximate graph coloring by semidefinite programming

  1994influential reference
• Approximate Graph Coloring by Semideenite Programming

  1994cited by this paper
• An application of submodular flows

  1989influential reference
• Improving the performance guarantee for approximate graph coloring

  1983cited by this paper
• Endlichkeitssätze fürk-kritische Graphen

  1977cited by this paper

• Placing Green Bridges Optimally for Robust Habitat Reconnection

  2026cites this paper
• Streaming Algorithms for Network Design

  2025cites this paper
• Bicriteria approximation for k-edge-connectivity

  2025cites this paper
• Streaming Algorithms for Connectivity Augmentation

  2024cites this paper
• Node Connectivity Augmentation of Highly Connected Graphs

  2023cites this paper
• A logarithmic approximation algorithm for the activation edge multicover problem

  2023cites this paper
• A Parameterized Algorithm for Vertex Connectivity Survivable Network Design Problem with Uniform Demands

  2023cites this paper
• Ghost Value Augmentation for k-Edge-Connectivity

  2023cites this paper
• Survivable Network Design Revisited: Group-Connectivity

  2022cites this paper
• Parameterized algorithms for node connectivity augmentation problems

  2022cites this paper
• Node connectivity augmentation via iterative randomized rounding

  2021cites this paper
• Augmenting the Algebraic Connectivity of Graphs

  2020cites this paper
• A spectral approach to network design

  2020cites this paper
• On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem

  2019influential citation
• D S ] 2 2 Ja n 20 19 A ( 4 + ǫ )-approximation for k-connected subgraphs

  2019influential citation
• A $(4+\epsilon)$-approximation for $k$-connected subgraphs

  2019influential citation
• Approximating k-Connected m-Dominating Sets

  2019cites this paper
• Network Design for s-t Effective Resistance

  2019cites this paper
• Optimization Everywhere: Convex, Combinatorial, and Economic

  2018cites this paper
• Activation Network Design Problems

  2018cites this paper
• The Complexity of Network Design for s-t Eff ective Resistance

  2018cites this paper
• The k-Connected Subgraph Problem

  2018cites this paper
• Maximum Bounded Rooted-Tree Problem : Algorithms and Polyhedra

  2017cites this paper
• Improved Approximation Algorithms for Minimum Cost Node-Connectivity Augmentation Problems

  2017influential citation
• Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

  2017cites this paper
• Improved Approximation Algorithms for Min-Cost Connectivity Augmentation Problems

  2016cites this paper
• An Algorithm for k-Connectivity Under Pure SINR Model

  2016cites this paper
• Surviving in Directed Graphs: A Polylogarithmic Approximation for Two-Connected Directed Steiner Tree

  2016cites this paper
• On Survivable Set Connectivity

  2015cites this paper
• A unified algorithm for degree bounded survivable network design

  2014cites this paper
• Approximating minimum-cost edge-covers of crossing biset-families

  2014cites this paper
• Approximability status of Survivable Network problems

  2014cites this paper
• Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements

  2014cites this paper
• Fixed-Parameter Algorithms for Minimum-Cost Edge-Connectivity Augmentation

  2013cites this paper
• Approximating minimum-cost edge-covers of crossing biset-families

  2012cites this paper
• Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

  2012influential citation
• Approximating minimum power edge-multi-covers

  2011cites this paper
• Research Plan

  year unknowncites this paper