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

doi:10.4230/LIPIcs.ICALP.2022.37

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 proceeding › Conference article in proceedings › Scientific › peer-review

4 Citations (Scopus)

45 Downloads (Pure)

Abstract

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(n²) 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/ε²) 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 language	English
Title of host publication	49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Editors	Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-20
Number of pages	20
ISBN (Electronic)	978-3-95977-235-8
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2022.37
Publication status	Published - 1 Jul 2022
MoE publication type	A4 Conference publication
Event	International Colloquium on Automata, Languages, and Programming - Paris, France Duration: 4 Jul 2022 → 8 Jul 2022 Conference number: 49 https://icalp2022.irif.fr/

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Publisher	Schloss Dagstuhl-Leibniz-Zentrum für Informatik
Volume	229
ISSN (Electronic)	1868-8969

Conference

Conference	International Colloquium on Automata, Languages, and Programming
Abbreviated title	ICALP
Country/Territory	France
City	Paris
Period	04/07/2022 → 08/07/2022
Internet address	https://icalp2022.irif.fr/

Funding

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 759557 & 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415). Funding This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under grant agreement No 759557 & 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415).

Keywords

Approximation Algorithms
Data Structures

Access to Document

10.4230/LIPIcs.ICALP.2022.37Licence: CC BY

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP SolverFinal published version, 928 KBLicence: CC BY

Cite this

Chalermsook, P., Huang, C. C., Nanongkai, D., Saranurak, T., Sukprasert, P., & Yingchareonthawornchai, S. (2022). Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In M. Bojanczyk, E. Merelli, & D. P. Woodruff (Eds.), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 (pp. 1-20). Article 37 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 229). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2022.37

Chalermsook, Parinya ; Huang, Chien Chung ; Nanongkai, Danupon et al. / Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. editor / Mikolaj Bojanczyk ; Emanuela Merelli ; David P. Woodruff. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. pp. 1-20 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{813b0cceda7f46c89d8d3e2f70b98a19,

title = "Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver",

abstract = "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 {\~O}(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.",

keywords = "Approximation Algorithms, Data Structures",

author = "Parinya Chalermsook and Huang, \{Chien Chung\} and Danupon Nanongkai and Thatchaphol Saranurak and Pattara Sukprasert and Sorrachai Yingchareonthawornchai",

note = "| openaire: EC/H2020/759557/EU//ALGOCom | openaire: EC/H2020/715672/EU//DisDyn Funding Information: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 759557 \& 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415). Funding Information: Funding This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme under grant agreement No 759557 \& 715672. Nanongkai and Saranurak were also partially supported by the Swedish Research Council (Reg. No. 2015-04659.). Chalermsook was also supported by the Academy Research Fellowship (grant number 310415). Publisher Copyright: {\textcopyright} Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai; licensed under Creative Commons License CC-BY 4.0; International Colloquium on Automata, Languages, and Programming, ICALP ; Conference date: 04-07-2022 Through 08-07-2022",

year = "2022",

month = jul,

day = "1",

doi = "10.4230/LIPIcs.ICALP.2022.37",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--20",

editor = "Mikolaj Bojanczyk and Emanuela Merelli and Woodruff, \{David P.\}",

booktitle = "49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022",

address = "Germany",

url = "https://icalp2022.irif.fr/",

}

Chalermsook, P, Huang, CC, Nanongkai, D, Saranurak, T, Sukprasert, P & Yingchareonthawornchai, S 2022, Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. in M Bojanczyk, E Merelli & DP Woodruff (eds), 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022., 37, Leibniz International Proceedings in Informatics, LIPIcs, vol. 229, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-20, International Colloquium on Automata, Languages, and Programming, Paris, France, 04/07/2022. https://doi.org/10.4230/LIPIcs.ICALP.2022.37

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. / Chalermsook, Parinya; Huang, Chien Chung; Nanongkai, Danupon et al.
49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. ed. / Mikolaj Bojanczyk; Emanuela Merelli; David P. Woodruff. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. p. 1-20 37 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 229).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

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

AU - Chalermsook, Parinya

AU - Huang, Chien Chung

AU - Nanongkai, Danupon

AU - Saranurak, Thatchaphol

AU - Sukprasert, Pattara

AU - Yingchareonthawornchai, Sorrachai

N1 - Conference code: 49

PY - 2022/7/1

Y1 - 2022/7/1

N2 - 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.

AB - 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.

KW - Approximation Algorithms

KW - Data Structures

UR - https://www.scopus.com/pages/publications/85133440936

U2 - 10.4230/LIPIcs.ICALP.2022.37

DO - 10.4230/LIPIcs.ICALP.2022.37

M3 - Conference article in proceedings

AN - SCOPUS:85133440936

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 1

EP - 20

BT - 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

A2 - Bojanczyk, Mikolaj

A2 - Merelli, Emanuela

A2 - Woodruff, David P.

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - International Colloquium on Automata, Languages, and Programming

Y2 - 4 July 2022 through 8 July 2022

ER -

Chalermsook P, Huang CC, Nanongkai D, Saranurak T, Sukprasert P, Yingchareonthawornchai S. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In Bojanczyk M, Merelli E, Woodruff DP, editors, 49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2022. p. 1-20. 37. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.ICALP.2022.37

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

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this

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

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Combinatorics of Graph Packing and Online Binary Search Trees

Cite this