A 4/3 Approximation For 2-Vertex-Connectivity

Miguel Bosch-Calvo; Fabrizio Grandoni; Afrouz Jabal Ameli

doi:10.4230/LIPIcs.ICALP.2023.29

A 4/3 Approximation For 2-Vertex-Connectivity

Miguel Bosch-Calvo, Fabrizio Grandoni, Afrouz Jabal Ameli

Combinatorial Optimization

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

3 Downloads (Pure)

Abstract

The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]).
Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

Original language	English
Title of host publication	50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Editors	Kousha Etessami , Uriel Feige, Gabriele Puppis
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	29:1-29:13
Number of pages	13
ISBN (Electronic)	978-3-95977-278-5
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2023.29
Publication status	Published - 5 Jul 2023
Event	50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany Duration: 10 Jul 2023 → 14 Jul 2023

Publication series

Name	Leibniz International Proceedings in Informatics, LIPcs
Volume	261
ISSN (Print)	1868-8969

Conference

Conference	50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
Abbreviated title	ICALP 2023
Country/Territory	Germany
City	Paderborn
Period	10/07/23 → 14/07/23

Access to Document

10.4230/LIPIcs.ICALP.2023.29

pdfFinal published version, 688 KBLicence: CC BY

Cite this

Bosch-Calvo, M., Grandoni, F., & Jabal Ameli, A. (2023). A 4/3 Approximation For 2-Vertex-Connectivity. In K. Etessami , U. Feige, & G. Puppis (Eds.), 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 (pp. 29:1-29:13). Article 29 (Leibniz International Proceedings in Informatics, LIPcs; Vol. 261). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.29

Bosch-Calvo, Miguel ; Grandoni, Fabrizio ; Jabal Ameli, Afrouz. / A 4/3 Approximation For 2-Vertex-Connectivity. 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. editor / Kousha Etessami ; Uriel Feige ; Gabriele Puppis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. pp. 29:1-29:13 (Leibniz International Proceedings in Informatics, LIPcs).

@inproceedings{8170cc0368b14f0b8fe7f17c247627e4,

title = "A 4/3 Approximation For 2-Vertex-Connectivity",

abstract = "The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]).Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are {"}almost{"} 3-vertex-connected. The latter reduction might be helpful in future work.",

author = "Miguel Bosch-Calvo and Fabrizio Grandoni and {Jabal Ameli}, Afrouz",

year = "2023",

month = jul,

day = "5",

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

language = "English",

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

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

pages = "29:1--29:13",

editor = "{Etessami }, Kousha and Uriel Feige and Gabriele Puppis",

booktitle = "50th International Colloquium on Automata, Languages, and Programming, ICALP 2023",

note = "50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, ICALP 2023 ; Conference date: 10-07-2023 Through 14-07-2023",

}

Bosch-Calvo, M, Grandoni, F & Jabal Ameli, A 2023, A 4/3 Approximation For 2-Vertex-Connectivity. in K Etessami , U Feige & G Puppis (eds), 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023., 29, Leibniz International Proceedings in Informatics, LIPcs, vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 29:1-29:13, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, 10/07/23. https://doi.org/10.4230/LIPIcs.ICALP.2023.29

A 4/3 Approximation For 2-Vertex-Connectivity. / Bosch-Calvo, Miguel; Grandoni, Fabrizio; Jabal Ameli, Afrouz.
50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. ed. / Kousha Etessami ; Uriel Feige; Gabriele Puppis. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. p. 29:1-29:13 29 (Leibniz International Proceedings in Informatics, LIPcs; Vol. 261).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A 4/3 Approximation For 2-Vertex-Connectivity

AU - Bosch-Calvo, Miguel

AU - Grandoni, Fabrizio

AU - Jabal Ameli, Afrouz

PY - 2023/7/5

Y1 - 2023/7/5

N2 - The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]).Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

AB - The 2-Vertex-Connected Spanning Subgraph problem (2VCSS) is among the most basic NP-hard (Survivable) Network Design problems: we are given an (unweighted) undirected graph G. Our goal is to find a subgraph S of G with the minimum number of edges which is 2-vertex-connected, namely S remains connected after the deletion of an arbitrary node. 2VCSS is well-studied in terms of approximation algorithms, and the current best (polynomial-time) approximation factor is 10/7 by Heeger and Vygen [SIDMA'17] (improving on earlier results by Khuller and Vishkin [STOC'92] and Garg, Vempala and Singla [SODA'93]).Here we present an improved 4/3 approximation. Our main technical ingredient is an approximation preserving reduction to a conveniently structured subset of instances which are "almost" 3-vertex-connected. The latter reduction might be helpful in future work.

U2 - 10.4230/LIPIcs.ICALP.2023.29

DO - 10.4230/LIPIcs.ICALP.2023.29

M3 - Conference contribution

T3 - Leibniz International Proceedings in Informatics, LIPcs

SP - 29:1-29:13

BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

A2 - Etessami , Kousha

A2 - Feige, Uriel

A2 - Puppis, Gabriele

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

T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

Y2 - 10 July 2023 through 14 July 2023

ER -

Bosch-Calvo M, Grandoni F, Jabal Ameli A. A 4/3 Approximation For 2-Vertex-Connectivity. In Etessami K, Feige U, Puppis G, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2023. p. 29:1-29:13. 29. (Leibniz International Proceedings in Informatics, LIPcs). doi: 10.4230/LIPIcs.ICALP.2023.29

A 4/3 Approximation For 2-Vertex-Connectivity

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this