Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Authors Eduard Eiben , Dušan Knop , Fahad Panolan, Ondřej Suchý

PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.25.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Eduard Eiben
  • Department of Informatics, University of Bergen, Bergen, Norway
Dušan Knop
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
Fahad Panolan
  • Department of Informatics, University of Bergen, Bergen, Norway
Ondřej Suchý
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic

Funding

  • Eiben, Eduard: Eduard Eiben was supported by Pareto-Optimal Parameterized Algorithms (ERC Starting Grant 715744).
  • Knop, Dušan: Partially supported by DFG under project "MaMu", NI 369/19.
  • Suchý, Ondřej: Supported by grant 17-20065S of the Czech Science Foundation.

Cite AsGet BibTex

Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.25

Abstract

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals T subseteq V(G) with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph H subseteq G of the minimum cost such that there is a directed path from s to t in H for all st in A(R). It is known that the problem can be solved in time |V(G)|^{O(|A(R)|)} [Feldman and Ruhl, SIAM J. Comput. 2006] and cannot be solved in time |V(G)|^{o(|A(R)|)} even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time |V(G)|^{o(q)}, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that Directed Steiner Network is solvable in time f(q)* |V(G)|^{O(c_g * q)}, where c_g is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no f(q)* |V(G)|^{o(q^2/ log q)} algorithm for any function f for the problem on general graphs, unless ETH fails.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Directed Steiner Network
  • Planar Graphs
  • Parameterized Algorithms
  • Bounded Genus
  • Exponential Time Hypothesis

Metrics

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

Related Versions

References

  1. Marshall W. Bern and Paul E. Plassmann. The Steiner Problem with Edge Lengths 1 and 2. Inf. Process. Lett., 32(4):171-176, 1989. URL: http://dx.doi.org/10.1016/0020-0190(89)90039-2.
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proceedings of the 39th ACM Symposium on Theory of Computing, STOC 2007, pages 67-74. ACM, 2007. Google Scholar
  3. Jarosław Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM, 60(1):6:1-6:33, February 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
  4. 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. URL: http://dx.doi.org/10.1006/jagm.1999.1042.
  5. Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Trans. Algorithms, 7(2):18:1-18:17, 2011. URL: http://dx.doi.org/10.1145/1921659.1921664.
  6. Rajesh Chitnis, Andreas Emil Feldmann, and Pasin Manurangsi. Parameterized Approximation Algorithms for Bidirected Steiner Network Problems. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.20.
  7. Rajesh Chitnis, Mohammadtaghi Hajiaghayi, and Daniel Marx. Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1782-1801. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.129.
  8. Dietmar Cieslik. Steiner minimal trees, volume 23 of Nonconvex Optimization and Its Applications. Springer Science &Business Media, 1998. Google Scholar
  9. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On Problems as Hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41, 2016. URL: http://dx.doi.org/10.1145/2925416.
  10. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner’s Contraction. Algorithmica, 54(2):142-180, 2009. URL: http://dx.doi.org/10.1007/s00453-007-9138-y.
  11. Reinhard Diestel. Graph Theory, 5th Edition, volume 173 of Graduate texts in mathematics. Springer, 2017. Google Scholar
  12. Irit Dinur and Pasin Manurangsi. ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ITCS.2018.36.
  13. Yevgeniy Dodis and Sanjeev Khanna. Design Networks with Bounded Pairwise Distance. In Proc. 31th STOC, pages 750-759. ACM, 1999. Google Scholar
  14. Stuart E. Dreyfus and Robert A. Wagner. The Steiner problem in graphs. Networks, 1:195-207, 1972. Google Scholar
  15. David Eppstein. Diameter and Treewidth in Minor-Closed Graph Families. Algorithmica, 27(3):275-291, 2000. URL: http://dx.doi.org/10.1007/s004530010020.
  16. Ranel E. Erickson, Clyde L. Monma, and Arthur F. Veinott, Jr. Send-and-Split Method for Minimum-Concave-Cost Network Flows. Mathematics of Operations Research, 12(4):634-664, 1987. URL: http://dx.doi.org/10.1287/moor.12.4.634.
  17. Jon Feldman and Matthias Ruhl. The Directed Steiner Network Problem Is Tractable for a Constant Number of Terminals. SIAM Journal on Computing, 36(2):543-561, 2006. Google Scholar
  18. Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.27.
  19. Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. CoRR, abs/1707.06808, 2017. URL: http://arxiv.org/abs/1707.06808.
  20. Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings, Part I, volume 9134 of LNCS, pages 494-505. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_40.
  21. Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 470-479. IEEE Computer Society, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.62.
  22. Bernhard Fuchs, Walter Kern, Daniel Mölle, Stefan Richter, Peter Rossmanith, and Xinhui Wang. Dynamic Programming for Minimum Steiner Trees. Theory of Computing Systems, 41(3):493-500, 2007. URL: http://dx.doi.org/10.1007/s00224-007-1324-4.
  23. Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. J. Combin. Theory Ser. B, 99(1):218-228, 2009. URL: http://dx.doi.org/10.1016/j.jctb.2008.06.004.
  24. Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Wiley-Interscience, New York, NY, USA, 1987. Google Scholar
  25. Jiong Guo, Rolf Niedermeier, and Ondřej Suchý. Parameterized Complexity of Arc-Weighted Directed Steiner Problems. SIAM Journal on Discrete Mathematics, 25(2):583-599, 2011. Google Scholar
  26. Eran Halperin and Robert Krauthgamer. Polylogarithmic Inapproximability. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 585-594, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/780542.780628.
  27. Frank K. Hwang, Dana S. Richards, and Pawel Winter. The Steiner Tree Problem, volume 53 of Annals of Discrete Mathematics. Elsevier, 1992. URL: http://dx.doi.org/10.1016/S0167-5060(08)70188-2.
  28. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  29. Richard M. Karp. Reducibility among Combinatorial Problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors, Proceedings of a symposium on the Complexity of Computer Computations, 1972, pages 85-103, Boston, MA, 1972. Springer US. URL: http://dx.doi.org/10.1007/978-1-4684-2001-2_9.
  30. Anatolii Y. Levin. Algorithm for the shortest connection of a group of graph vertices. Sov. Math. Dokl., 12:1477-1481, 1971. Google Scholar
  31. Leonid Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-662-07003-1.
  32. Dániel Marx. Can You Beat Treewidth? Theory of Computing, 6(1):85-112, 2010. URL: http://dx.doi.org/10.4086/toc.2010.v006a005.
  33. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins series in the mathematical sciences. Johns Hopkins University Press, 2001. Google Scholar
  34. Jesper Nederlof. Fast Polynomial-Space Algorithms Using Inclusion-Exclusion. Algorithmica, 65(4):868-884, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9630-x.
  35. Hans Jürgen Prömel and Angelika Steger. The Steiner Tree Problem; a Tour through Graphs, Algorithms, and Complexity. Vieweg, 2002. Google Scholar
  36. Ondřej Suchý. On Directed Steiner Trees with Multiple Roots. In Pinar Heggernes, editor, Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, volume 9941 of Lecture Notes in Computer Science, pages 257-268, 2016. URL: http://dx.doi.org/10.1007/978-3-662-53536-3_22.
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