Document Open Access Logo

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

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

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.37.pdf
  • Filesize: 0.9 MB
  • 20 pages

Document Identifiers

Author Details

Parinya Chalermsook
  • Aalto University, Espoo, Finland
Chien-Chung Huang
  • École Normale Supérieure, Paris, France
Danupon Nanongkai
  • University of Copenhagen, Denmark
  • KTH Royal Institute of Technology, Stockholm, Sweden
Thatchaphol Saranurak
  • University of Michigan, Ann Arbor, MI, USA
Pattara Sukprasert
  • Northwestern University, Evanston, IL, USA
Sorrachai Yingchareonthawornchai
  • Aalto University, Espoo, Finland

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

Acknowledgements

We thank the 2021 Hausdorff Research Institute for Mathematics Program Discrete Optimization during which part of this work was developed. Parinya Chalermsook thanks Chandra Chekuri for clarifications of his FOCS 2017 paper and for giving some pointers. We thank Corinna Coupette for bringing [Michel X. Goemans et al., 1994] to our attention.

Cite AsGet BibTex

Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.37

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(mn k) 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 Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Approximation Algorithms
  • Data Structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. David Adjiashvili. Beating approximation factor two for weighted tree augmentation with bounded costs. ACM Transactions on Algorithms (TALG), 15(2):1-26, 2018. Google Scholar
  2. András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput., 44(2):290-319, 2015. Google Scholar
  3. André Berger and Michelangelo Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar graphs. In International Colloquium on Automata, Languages, and Programming, pages 90-101. Springer, 2007. Google Scholar
  4. Glencora Borradaile, Erik D Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 68(2):287-311, 2014. Google Scholar
  5. Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. Survivable network design for group connectivity in low-treewidth graphs. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2018. Google Scholar
  6. Chandra Chekuri and Kent Quanrud. Approximating the held-karp bound for metric TSP in nearly-linear time. CoRR, abs/1702.04307, 2017. URL: http://arxiv.org/abs/1702.04307.
  7. Chandra Chekuri and Kent Quanrud. Fast approximations for metric-tsp via linear programming. CoRR, abs/1802.01242, 2018. URL: http://arxiv.org/abs/1802.01242.
  8. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs/1910.08025, 2019. URL: http://arxiv.org/abs/1910.08025.
  9. Béla Csaba, Marek Karpinski, and Piotr Krysta. Approximability of dense and sparse instances of minimum 2-connectivity, tsp and path problems. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 74-83. Society for Industrial and Applied Mathematics, 2002. Google Scholar
  10. Artur Czumaj, Michelangelo Grigni, Papa Sissokho, and Hairong Zhao. Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 496-505. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  11. Artur Czumaj and Andrzej Lingas. On approximability of the minimum-cost k-connected spanning subgraph problem. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 281-290. Citeseer, 1999. Google Scholar
  12. Artur Czumaj and Andrzej Lingas. Fast approximation schemes for euclidean multi-connectivity problems. In International Colloquium on Automata, Languages, and Programming, pages 856-868. Springer, 2000. Google Scholar
  13. Artur Czumaj and Andrzej Lingas. Approximation schemes for minimum-cost k-connectivity problems in geometric graphs. In Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall/CRC, 2007. Google Scholar
  14. Andreas Emil Feldmann, Jochen Könemann, Kanstantsin Pashkovich, and Laura Sanità. Fast approximation algorithms for the generalized survivable network design problem. In ISAAC, volume 64 of LIPIcs, pages 33:1-33:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  15. Cristina G Fernandes. A better approximation ratio for the minimum sizek-edge-connected spanning subgraph problem. Journal of Algorithms, 28(1):105-124, 1998. Google Scholar
  16. Samuel Fiorini, Martin Groß, Jochen Könemann, and Laura Sanità. Approximating weighted tree augmentation via chvátal-gomory cuts. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 817-831. SIAM, 2018. Google Scholar
  17. Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math., 13(4):505-520, 2000. Google Scholar
  18. Lisa Fleischer. A fast approximation scheme for fractional covering problems with variable upper bounds. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1001-1010, 2004. Google Scholar
  19. Greg N. Frederickson and Joseph JáJá. Approximation algorithms for several graph augmentation problems. SIAM J. Comput., 10(2):270-283, 1981. Google Scholar
  20. Harold N Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, 1995. Google Scholar
  21. Harold N Gabow, Michel X Goemans, Éva Tardos, and David P Williamson. Approximating the smallest k-edge connected spanning subgraph by lp-rounding. Networks: An International Journal, 53(4):345-357, 2009. Google Scholar
  22. Harold N. Gabow, Michel X. Goemans, and David P. Williamson. An efficient approximation algorithm for the survivable network design problem. Math. Program., 82:13-40, 1998. announced at IPCO'93. Google Scholar
  23. Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630-652, 2007. Google Scholar
  24. Michel X. Goemans, Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos, and David P. Williamson. Improved approximation algorithms for network design problems. In SODA, pages 223-232. ACM/SIAM, 1994. Google Scholar
  25. Fabrizio Grandoni, Christos Kalaitzis, and Rico Zenklusen. Improved approximation for tree augmentation: saving by rewiring. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 632-645, 2018. Google Scholar
  26. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. URL: https://doi.org/10.1007/s004930170004.
  27. David R Karger. Minimum cuts in near-linear time. Journal of the ACM (JACM), 47(1):46-76, 2000. announced at STOC'96. Google Scholar
  28. David R Karger, Philip N Klein, and Robert E Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM (JACM), 42(2):321-328, 1995. Google Scholar
  29. Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi. On a cut-matching game for the sparsest cut problem. Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2007-177, 2007. Google Scholar
  30. Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4):19:1-19:15, 2009. URL: https://doi.org/10.1145/1538902.1538903.
  31. Samir Khuller and Ramakrishna Thurimella. Approximation algorithms for graph augmentation. Journal of Algorithms, 14(2):214-225, 1993. Google Scholar
  32. Samir Khuller and Uzi Vishkin. Biconnectivity approximations and graph carvings. J. ACM, 41(2):214-235, 1994. announced at STOC'92. Google Scholar
  33. Bundit Laekhanukit, Shayan Oveis Gharan, and Mohit Singh. A rounding by sampling approach to the minimum size k-arc connected subgraph problem. In International Colloquium on Automata, Languages, and Programming, pages 606-616. Springer, 2012. Google Scholar
  34. Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. Vertex connectivity in poly-logarithmic max-flows. In STOC, pages 317-329. ACM, 2021. Google Scholar
  35. Aleksander Madry. Fast approximation algorithms for cut-based problems in undirected graphs. In FOCS, pages 245-254. IEEE Computer Society, 2010. Google Scholar
  36. Aleksander Madry. Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 121-130, 2010. URL: https://doi.org/10.1145/1806689.1806708.
  37. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, las vegas, and o (n1/2-ε)-time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1122-1129, 2017. Google Scholar
  38. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS, pages 950-961. IEEE Computer Society, 2017. Google Scholar
  39. David Pritchard. k-edge-connectivity: Approximation and LP relaxation. In WAOA, volume 6534 of Lecture Notes in Computer Science, pages 225-236. Springer, 2010. Google Scholar
  40. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In SODA, pages 2616-2635. SIAM, 2019. Google Scholar
  41. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  42. Jonah Sherman. Breaking the multicommodity flow barrier for o(vlog n)-approximations to sparsest cut. In FOCS, pages 363-372. IEEE Computer Society, 2009. Google Scholar
  43. Jonah Sherman. Nearly maximum flows in nearly linear time. In FOCS, pages 263-269. IEEE Computer Society, 2013. Google Scholar
  44. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS, pages 919-930. IEEE, 2020. Google Scholar
  45. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 1130-1143, 2017. URL: https://doi.org/10.1145/3055399.3055415.
  46. Neal E. Young. Nearly linear-time approximation schemes for mixed packing/covering and facility-location linear programs. CoRR, abs/1407.3015, 2014. URL: http://arxiv.org/abs/1407.3015.
  47. Rico Zenklusen. Connectivity interdiction. Oper. Res. Lett., 42(6-7):450-454, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact