Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Parinya Chalermsook*, Chien Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

1 Citation (Scopus)
14 Downloads (Pure)


In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the “uniform case” of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mnk) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n2) can be obtained, but with a higher approximation guarantee of (2k − 1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1 + ε)-approximates the optimal fractional solution in Õ(m/ε2) time (independent of k), which can be turned into a (2 + ε) approximation algorithm that runs in time (Equation presented) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.

Original languageEnglish
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Number of pages20
ISBN (Electronic)978-3-95977-235-8
Publication statusPublished - 1 Jul 2022
MoE publication typeA4 Conference publication
EventInternational Colloquium on Automata, Languages and Programming - Paris, France
Duration: 4 Jul 20228 Jul 2022
Conference number: 49

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
ISSN (Electronic)1868-8969


ConferenceInternational Colloquium on Automata, Languages and Programming
Abbreviated titleICALP
Internet address


  • Approximation Algorithms
  • Data Structures


Dive into the research topics of 'Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver'. Together they form a unique fingerprint.

Cite this