Document Open Access Logo

Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity

Authors Chao Liao, Qingyun Chen, Bundit Laekhanukit, Yuhao Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.89.pdf
  • Filesize: 0.78 MB
  • 17 pages

Document Identifiers

Author Details

Chao Liao
  • Shanghai Jiao Tong University, China
Qingyun Chen
  • University of California, Merced, CA, USA
Bundit Laekhanukit
  • Shanghai University of Finance and Economics, China
Yuhao Zhang
  • Shanghai Jiao Tong University, China

Funding

  • Chen, Qingyun: Qingyun Chen is supported in part by NSF grants CCF-2121745 and CCF-1844939.
  • Laekhanukit, Bundit: Bundit Laekhanukit is supported by the 1000-talent plan award by the Chinese government, supported by Science and Technology Innovation 2030 –- "New Generation of Artificial Intelligence" Major Project No.(2018AAA0100903), NSFC grant 61932002, Program for Innovative Research Team of Shanghai University of Finance and Economics (IRTSHUFE) and the Fundamental Research Funds for the Central Universities.
  • Zhang, Yuhao: Yuhao Zhang is supported by National Natural Science Foundation of China (NSFC) under Grant No. 62102251.

Cite As Get BibTex

Chao Liao, Qingyun Chen, Bundit Laekhanukit, and Yuhao Zhang. Almost Tight Approximation Hardness for Single-Source Directed k-Edge-Connectivity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ICALP.2022.89

Abstract

In the k-outconnected directed Steiner tree problem (k-DST), we are given an n-vertex directed graph G = (V,E) with edge costs, a connectivity requirement k, a root r ∈ V and a set of terminals T ⊆ V. The goal is to find a minimum-cost subgraph H ⊆ G that has k edge-disjoint paths from the root vertex r to every terminal t ∈ T. The problem is NP-hard, and inapproximability results are known in several parameters, e.g., hardness in terms of n: log^{2-ε}n-hardness for k = 1 [Halperin and Krauthgamer, STOC'03], 2^{log^{1-ε}n}-hardness for general case [Cheriyan, Laekhanukit, Naves and Vetta, SODA'12], hardness in terms of k [Cheriyan et al., SODA'12; Laekhanukit, SODA'14; Manurangsi, IPL'19] and hardness in terms of |T| [Laekhanukit, SODA'14].
In this paper, we show the approximation hardness of k-DST for various parameters.  
- Ω(|T|/log |T|)-approximation hardness, which holds under the standard complexity assumption NP≠ ZPP. The inapproximability ratio is tightened to Ω(|T|) under the Strongish Planted Clique Hypothesis [Manurangsi, Rubinstein and Schramm, ITCS 2021]. The latter hardness result matches the approximation ratio of |T| obtained by a trivial approximation algorithm, thus closing the long-standing open problem.
- Ω(2^{k/2} / k)-approximation hardness for the general case of k-DST under the assumption NP≠ZPP. This is the first hardness result known for survivable network design problems with an inapproximability ratio exponential in k.
- Ω((k/L)^{L/4})-approximation hardness for k-DST on L-layered graphs for L ≤ O(log n). This almost matches the approximation ratio of O(k^{L-1}⋅ L ⋅ log |T|) achieved in O(n^L)-time due to Laekhanukit [ICALP'16]. 
We further extend our hardness results in terms of |T| to the undirected cases of k-DST, namely the single-source k-vertex-connected Steiner tree and the k-edge-connected group Steiner tree problems. Thus, we obtain Ω(|T|/log |T|) and Ω(|T|) approximation hardness for both problems under the assumption NP≠ ZPP and the Strongish Planted Clique Hypothesis, respectively. This again matches the upper bound obtained by trivial algorithms.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Approximation algorithms
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Directed Steiner Tree
  • Hardness of Approximation
  • Fault-Tolerant and Survivable Network Design

Metrics

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

Related Versions

References

  1. Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 184-193. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/SFCS.1996.548477.
  2. Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoss, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1), February 2013. URL: https://doi.org/10.1145/2432622.2432628.
  3. Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. Survivable network design for group connectivity in low-treewidth graphs. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, volume 116 of LIPIcs, pages 8:1-8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.8.
  4. Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, and Daniel Vaz. Beyond metric embedding: Approximating group steiner trees on bounded treewidth graphs. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 737-751. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.47.
  5. Parinya Chalermsook, Fabrizio Grandoni, and Bundit Laekhanukit. On survivable set connectivity. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 25-36. SIAM, 2014. Google Scholar
  6. Parinya Chalermsook, Fabrizio Grandoni, and Bundit Laekhanukit. On survivable set connectivity. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 25-36. SIAM, 2015. URL: https://doi.org/10.1137/1.9781611973730.3.
  7. Chun-Hsiang Chan, Bundit Laekhanukit, Hao-Ting Wei, and Yuhao Zhang. Polylogarithmic approximation algorithm for k-connected directed steiner tree on quasi-bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), volume 176, pages 63:1-63:20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  8. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. Journal of Algorithms, 33(1):73-91, 1999. Google Scholar
  9. Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via trees: Deterministic approximation algorithms for group steiner trees and k-median. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 114-123. ACM, 1998. URL: https://doi.org/10.1145/276698.276719.
  10. Chandra Chekuri, Guy Even, and Guy Kortsarz. A greedy approximation algorithm for the group steiner problem. Discret. Appl. Math., 154(1):15-34, 2006. URL: https://doi.org/10.1016/j.dam.2005.07.010.
  11. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Approximating rooted steiner networks. ACM Transactions on Algorithms (TALG), 11(2):1-22, 2014. Google Scholar
  12. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 624-633. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591884.
  13. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. URL: https://doi.org/10.1016/j.jcss.2004.04.011.
  14. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: https://doi.org/10.1145/285055.285059.
  15. Lisa Fleischer, Kamal Jain, and David P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. Journal of Computer and System Sciences, 72(5):838-867, 2006. Special Issue on FOCS 2001. Google Scholar
  16. András Frank. Rooted k-connections in digraphs. Discret. Appl. Math., 157(6):1242-1254, 2009. URL: https://doi.org/10.1016/j.dam.2008.03.040.
  17. András Frank and Éva Tardos. Generalized polymatroids and submodular flows. Math. Program., 42(1-3):489-563, 1988. URL: https://doi.org/10.1007/BF01589418.
  18. Zachary Friggstad, Jochen Könemann, and Shadravan Mohammad. A Logarithmic Integrality Gap Bound for Directed Steiner Tree in Quasi-bipartite Graphs . In Rasmus Pagh, editor, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), volume 53 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:11, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Google Scholar
  19. Naveen Garg, Goran Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms, 37(1):66-84, 2000. URL: https://doi.org/10.1006/jagm.2000.1096.
  20. Rohan Ghuge and Viswanath Nagarajan. Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1039-1048. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.63.
  21. Michel X Goemans, Neil Olver, Thomas Rothvoß, and Rico Zenklusen. Matroids and integrality gaps for hypergraphic steiner tree relaxations. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1161-1176. SIAM, 2012. Google Scholar
  22. Fabrizio Grandoni and Bundit Laekhanukit. Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed steiner tree. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 420-428, 2017. Google Scholar
  23. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O (log² k/log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 253-264, 2019. Google Scholar
  24. Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi. Tree embeddings for two-edge-connected network design. In Moses Charikar, editor, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1521-1538. SIAM, 2010. URL: https://doi.org/10.1137/1.9781611973075.124.
  25. Eran Halperin, Guy Kortsarz, Robert Krauthgamer, Aravind Srinivasan, and Nan Wang. Integrality ratio for group steiner trees and directed steiner trees. SIAM J. Comput., 36(5):1494-1511, 2007. URL: https://doi.org/10.1137/S0097539704445718.
  26. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 585-594. ACM, 2003. URL: https://doi.org/10.1145/780542.780628.
  27. Tomoya Hibi and Toshihiro Fujito. Multi-rooted greedy approximation of directed steiner trees with applications. Algorithmica, 74(2):778-786, 2016. Google Scholar
  28. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Google Scholar
  29. Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. Approximating fault-tolerant group-steiner problems. Theor. Comput. Sci., 416:55-64, 2012. URL: https://doi.org/10.1016/j.tcs.2011.08.021.
  30. Samir Khuller and Uzi Vishkin. Biconnectivity approximations and graph carvings. J. ACM, 41(2):214-235, 1994. URL: https://doi.org/10.1145/174652.174654.
  31. Guy Kortsarz, Robert Krauthgamer, and James R. Lee. Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput., 33(3):704-720, 2004. URL: https://doi.org/10.1137/S0097539702416736.
  32. Bundit Laekhanukit. Parameters of two-prover-one-round game and the hardness of connectivity problems. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1626-1643. SIAM, 2014. Google Scholar
  33. Bundit Laekhanukit. Approximating directed steiner problems via tree embedding. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  34. Pasin Manurangsi. A note on degree vs gap of min-rep label cover and improved inapproximability for connectivity problems. Information Processing Letters, 145:24-29, 2019. Google Scholar
  35. Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The strongish planted clique hypothesis and its consequences. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 10:1-10:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.10.
  36. Zeev Nutov. Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Transactions on Algorithms (TALG), 9(1):1-16, 2012. Google Scholar
  37. Zeev Nutov. On rooted k-connectivity problems in quasi-bipartite digraphs. In International Computer Science Symposium in Russia, pages 339-348. Springer, 2021. Google Scholar
  38. Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica, 18(1):99-110, 1997. 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 About DROPS Imprint Privacy Contact