Document Open Access Logo

Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs

Authors Chun-Hsiang Chan, Bundit Laekhanukit , Hao-Ting Wei, Yuhao Zhang

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2020.63.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Approximation Algorithms
  • Network Design
  • Directed Graphs

Metrics

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

Abstract

In the k-Connected Directed Steiner Tree problem (k-DST), we are given a directed graph G = (V,E) with edge (or vertex) costs, a root vertex r, a set of q terminals T, and a connectivity requirement k > 0; the goal is to find a minimum-cost subgraph H of G such that H has k edge-disjoint paths from the root r to each terminal in T. The k-DST problem is a natural generalization of the classical Directed Steiner Tree problem (DST) in the fault-tolerant setting in which the solution subgraph is required to have an r,t-path, for every terminal t, even after removing k-1 vertices or edges. Despite being a classical problem, there are not many positive results on the problem, especially for the case k ≥ 3. In this paper, we present an O(log k log q)-approximation algorithm for k-DST when an input graph is quasi-bipartite, i.e., when there is no edge joining two non-terminal vertices. To the best of our knowledge, our algorithm is the only known non-trivial approximation algorithm for k-DST, for k ≥ 3, that runs in polynomial-time Our algorithm is tight for every constant k, due to the hardness result inherited from the Set Cover problem.

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 63:1-63:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.63

Author Details

Chun-Hsiang Chan
  • Department of Computer Science, University of Michigan, Ann Arbor, MI, USA
Bundit Laekhanukit
  • Institute for Theoretical Computer Science, Shanghai University of Finance & Economics, China
Hao-Ting Wei
  • Department of IEOR, Columbia University, New York, NY, USA
Yuhao Zhang
  • Department of Computer Science, The University of Hong Kong, China

Funding

  • Laekhanukit, Bundit: Partially 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. Also, partially supported by the 1000-talent award by the Chinese Government.

Acknowledgements

The works were initiated while all the authors were at the Institute for Theoretical Computer Science at the Shanghai University of Finance and Economics, and the work were done while Chun-Hsiang Chan and Hao-Ting Wei were in bachelor and master programs in Computer Science at the Institute of Information Science, Academia Sinica, Taipei.

References

  1. Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016. Google Scholar
  2. Mihir Bellare, Shafi Goldwasser, Carsten Lund, and A. Russeli. Efficient probabilistically checkable proofs and applications to approximations. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 294-304. ACM, 1993. URL: https://doi.org/10.1145/167088.167174.
  3. Kristóf Bérczi and Erika Renáta Kovács. A note on strongly edge-disjoint arborescences. In 7th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, pages 10-18, 2011. Also, in EGRES Technical Reports series TR-2011-04. Google Scholar
  4. Dimitris Bertsimas and Rakesh Vohra. Rounding algorithms for covering problems. Mathematical Programming, 80:63-89, 1998. URL: https://doi.org/10.1007/BF01582131.
  5. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. Preliminary version in STOC'10. URL: https://doi.org/10.1145/2432622.2432628.
  6. Deeparnab Chakrabarty, Nikhil R. Devanur, and Vijay V. Vazirani. New geometry-inspired relaxations and algorithms for the metric steiner tree problem. Math. Program., 130(1):1-32, 2011. Preliminary version in IPCO'08. URL: https://doi.org/10.1007/s10107-009-0299-0.
  7. Tanmoy Chakraborty, Julia Chuzhoy, and Sanjeev Khanna. Network design for vertex connectivity. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 167-176. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374403.
  8. 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.
  9. Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li. Approximation algorithms for directed steiner problems. J. Algorithms, 33(1):73-91, 1999. URL: https://doi.org/10.1006/jagm.1999.1042.
  10. Chandra Chekuri and Nitish Korula. A graph reduction step preserving element-connectivity and applications. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 254-265. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_22.
  11. Joseph Cheriyan and Bundit Laekhanukit. Approximation algorithms for minimum-cost k- connected digraphs. SIAM J. Discrete Math., 27(3):1450-1481, 2013. URL: https://doi.org/10.1137/100818728.
  12. Joseph Cheriyan, Bundit Laekhanukit, Guyslain Naves, and Adrian Vetta. Approximating rooted steiner networks. ACM Trans. Algorithms, 11(2):8:1-8:22, 2014. Preliminary version in SODA'12. URL: https://doi.org/10.1145/2650183.
  13. Julia Chuzhoy and Sanjeev Khanna. Algorithms for single-source vertex connectivity. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 105-114. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.63.
  14. Julia Chuzhoy and Sanjeev Khanna. An o(k³log n)-approximation algorithm for vertex-connectivity survivable network design. Theory of Computing, 8(1):401-413, 2012. Preliminary version in FOCS'09. URL: https://doi.org/10.4086/toc.2012.v008a018.
  15. 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.
  16. Yevgeniy Dodis and Sanjeev Khanna. Design networks with bounded pairwise distance. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 750-759. ACM, 1999. URL: https://doi.org/10.1145/301250.301447.
  17. Jittat Fakcharoenphol and Bundit Laekhanukit. An o(log² k)-approximation algorithm for the k-vertex connected spanning subgraph problem. SIAM J. Comput., 41(5):1095-1109, 2012. Preliminary version in STOC'08. URL: https://doi.org/10.1137/110855910.
  18. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. Preliminary version in STOC'96. URL: https://doi.org/10.1145/285055.285059.
  19. Moran Feldman, Guy Kortsarz, and Zeev Nutov. Improved approximating algorithms for directed steiner forest. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 922-931. SIAM, 2009. URL: https://doi.org/10.1137/1.9781611973068.
  20. Lisa Fleischer, Kamal Jain, and David P. Williamson. Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems. J. Comput. Syst. Sci., 72(5):838-867, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.006.
  21. András Frank. Kernel systems of directed graphs. Acta Sci. Math.(Szeged), 41(1-2):63-76, 1979. Google Scholar
  22. András Frank. Increasing the rooted-connectivity of a digraph by one. Math. Program., 84(3):565-576, 1999. URL: https://doi.org/10.1007/s101070050040.
  23. András Frank and Tibor Jordán. Directed vertex-connectivity augmentation. Math. Program., 84(3):537-553, 1999. URL: https://doi.org/10.1007/s101070050038.
  24. András Frank and Tibor Jordán. Graph connectivity augmentation. In Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, pages 315-348. CRC Press, 2016. Google Scholar
  25. Zachary Friggstad, Jochen Könemann, Young Kun-Ko, Anand Louis, Mohammad Shadravan, and Madhur Tulsiani. Linear programming hierarchies suffice for directed steiner tree. In Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings, pages 285-296, 2014. URL: https://doi.org/10.1007/978-3-319-07557-0_24.
  26. Zachary Friggstad, Jochen Könemann, and Mohammad Shadravan. 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, June 22-24, 2016, Reykjavik, Iceland, volume 53 of LIPIcs, pages 3:1-3:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.SWAT.2016.3.
  27. Naveen Garg, Goran Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms, 37(1):66-84, 2000. Preliminary version in SODA'98. URL: https://doi.org/10.1006/jagm.2000.1096.
  28. Loukas Georgiadis and Robert E. Tarjan. Dominator tree certification and divergent spanning trees. ACM Transactions on Algorithms, 12(1):11, 2016. Preliminary version in SODA'05. URL: https://doi.org/10.1145/2764913.
  29. Rohan Ghuge and Viswanath Nagarajan. A quasi-polynomial algorithm for submodular tree orienteering in directed graphs. CoRR, abs/1812.01768, 2018. URL: http://arxiv.org/abs/1812.01768.
  30. 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 Daniel Dominic Sleator, editor, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA., pages 223-232. ACM/SIAM, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314497.
  31. Michel X. Goemans, Neil Olver, Thomas Rothvoß, and Rico Zenklusen. Matroids and integrality gaps for hypergraphic steiner tree relaxations. In Howard J. Karloff and Toniann Pitassi, editors, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 1161-1176. ACM, 2012. URL: https://doi.org/10.1145/2213977.2214081.
  32. Fabrizio Grandoni and Bundit Laekhanukit. Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed steiner tree. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 420-428. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055445.
  33. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O(log^2 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, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 253-264, 2019. URL: https://doi.org/10.1145/3313276.3316349.
  34. Tomoya Hibi and Toshihiro Fujito. Multi-rooted greedy approximation of directed steiner trees with applications. Algorithmica, 74(2):778-786, 2016. URL: https://doi.org/10.1007/s00453-015-9973-1.
  35. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. Preliminary version in FOCS'01. URL: https://doi.org/10.1007/s004930170004.
  36. Philip N. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted steiner trees. J. Algorithms, 19(1):104-115, 1995. Preliminary version in IPCO'93. URL: https://doi.org/10.1006/jagm.1995.1029.
  37. Jochen Könemann, David Pritchard, and Kunlun Tan. A partition-based relaxation for steiner trees. Math. Program., 127(2):345-370, 2011. URL: https://doi.org/10.1007/s10107-009-0289-2.
  38. 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. Preliminary version in APPROX'02. URL: https://doi.org/10.1137/S0097539702416736.
  39. Guy Kortsarz and Zeev Nutov. Approximating k-node connected subgraphs via critical graphs. SIAM J. Comput., 35(1):247-257, 2005. Preliminary version in STOC'04. URL: https://doi.org/10.1137/S0097539703435753.
  40. Guy Kortsarz and David Peleg. Approximating shallow-light trees (extended abstract). In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 5-7 January 1997, New Orleans, Louisiana, USA., pages 103-110, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314191.
  41. Bundit Laekhanukit. Parameters of two-prover-one-round game and the hardness of connectivity problems. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1626-1643. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.118.
  42. Bundit Laekhanukit. An improved approximation algorithm for the minimum cost subset k-connected subgraph problem. Algorithmica, 72(3):714-733, 2015. Preliminary version in ICALP'11. URL: https://doi.org/10.1007/s00453-014-9869-5.
  43. Bundit Laekhanukit. Approximating directed steiner problems via tree embedding. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 74:1-74:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.74.
  44. Dana Moshkovitz. The projection games conjecture and the np-hardness of ln n-approximating set-cover. Theory of Computing, 11:221-235, 2015. Preliminary version in APPROX'12. URL: https://doi.org/10.4086/toc.2015.v011a007.
  45. Zeev Nutov. Approximating minimum power covers of intersecting families and directed edge-connectivity problems. Theor. Comput. Sci., 411(26-28):2502-2512, 2010. Preliminary version in APPROX'06. URL: https://doi.org/10.1016/j.tcs.2010.03.009.
  46. Zeev Nutov. Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Trans. Algorithms, 9(1):1:1-1:16, 2012. Preliminary version in FOCS'09. URL: https://doi.org/10.1145/2390176.2390177.
  47. Zeev Nutov. Approximating subset k-connectivity problems. J. Discrete Algorithms, 17:51-59, 2012. Preliminary version in WAOA'11. URL: https://doi.org/10.1016/j.jda.2012.08.001.
  48. Zeev Nutov. Approximating minimum-cost edge-covers of crossing biset-families. Combinatorica, 34(1):95-114, 2014. Preliminary version in SODA'09. URL: https://doi.org/10.1007/s00493-014-2773-4.
  49. Zeev Nutov. Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Trans. Algorithms, 14(3):37:1-37:8, 2018. URL: https://doi.org/10.1145/3186991.
  50. Harald Räcke. Optimal hierarchical decompositions for congestion minimization in networks. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 255-264. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374415.
  51. Sridhar Rajagopalan and Vijay V. Vazirani. On the bidirected cut relaxation for the metric steiner tree problem. In Robert Endre Tarjan and Tandy J. Warnow, editors, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 17-19 January 1999, Baltimore, Maryland, USA., pages 742-751. ACM/SIAM, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314909.
  52. Romeo Rizzi. On rajagopalan and vazirani’s 3/2-approximation bound for the iterated 1-steiner heuristic. Inf. Process. Lett., 86(6):335-338, 2003. URL: https://doi.org/10.1016/S0020-0190(03)00210-2.
  53. Gabriel Robins and Alexander Zelikovsky. Improved steiner tree approximation in graphs. In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9-11, 2000, San Francisco, CA, USA., pages 770-779. ACM/SIAM, 2000. URL: http://dl.acm.org/citation.cfm?id=338219.338638.
  54. Thomas Rothvoß. Directed steiner tree and the lasserre hierarchy. CoRR, abs/1111.5473, 2011. URL: http://arxiv.org/abs/1111.5473.
  55. David P. Williamson, Michel X. Goemans, Milena Mihail, and Vijay V. Vazirani. A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica, 15(3):435-454, 1995. Preliminary version in STOC'93. URL: https://doi.org/10.1007/BF01299747.
  56. Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed steiner tree problem. Algorithmica, 18(1):99-110, 1997. URL: https://doi.org/10.1007/BF02523690.
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact