Document Open Access Logo

The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems

Authors Andreas Emil Feldmann, Dániel Marx

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.27.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Andreas Emil Feldmann
Dániel Marx

Cite As Get BibTex

Andreas Emil Feldmann and Dániel Marx. The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.27

Abstract

Given a directed graph G and a list (s_1, t_1), ..., (s_k, t_k) of terminal pairs, the Directed Steiner Network problem asks for a minimum-cost subgraph of G that contains a directed s_i -> t_i path for every 1 <= i <= k. The special case Directed Steiner Tree (when we ask for paths from a root r to terminals t_1, . . . , t_k) is known to be fixed-parameter tractable parameterized by the number of terminals, while the special case Strongly Connected Steiner Subgraph (when we ask for a path from every t_i to every other t_j ) is known to be W[1]-hard parameterized by the number of terminals. We systematically explore the complexity landscape of directed Steiner problems to fully understand which other special cases are FPT or W[1]-hard. Formally, if H is a class of directed graphs, then we look at the special case of Directed Steiner Network where the list (s_1, t_1), ..., (s_k, t_k) of requests form a directed graph that is a member of H. Our main result is a complete characterization of the classes H resulting in fixed-parameter tractable special cases: we show that if every pattern in H has the combinatorial property of being "transitively equivalent to a bounded-length caterpillar with a bounded number of extra edges," then the problem is FPT, and it is W[1]-hard for every recursively enumerable H not having this property. This complete dichotomy unifies and generalizes the known results showing that Directed Steiner Tree is FPT [Dreyfus and Wagner, Networks 1971], Strongly Connected Steiner Subgraph is W[1]-hard [Guo et al., SIAM J. Discrete Math. 2011], and Directed Steiner Network is solvable in polynomial-time for constant number of terminals [Feldman and Ruhl, SIAM J. Comput. 2006], and moreover reveals a large continent of tractable cases that were not known before.

Subject Classification

Keywords
  • Directed Steiner Tree
  • Directed Steiner Network
  • fixed-parameter tractability
  • dichotomy

Metrics

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

References

  1. Ajit Agrawal, Philip N. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. URL: http://dx.doi.org/10.1137/S0097539792236237.
  2. MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, and Dániel Marx. Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011. URL: http://dx.doi.org/10.1145/2027216.2027219.
  3. MohammadHossein Bateni and MohammadTaghi Hajiaghayi. Euclidean prize-collecting Steiner forest. Algorithmica, 62(3-4):906-929, 2012. URL: http://dx.doi.org/10.1007/s00453-011-9491-8.
  4. MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Vahid Liaghat. Improved approximation algorithms for (budgeted) node-weighted Steiner problems. In 40th International Colloquium on Automata, Languages, and Programming, pages 81-92, 2013. URL: http://dx.doi.org/10.1007/978-3-642-39206-1_8.
  5. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Fourier meets Möbius: fast subset convolution. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 67-74, 2007. Google Scholar
  6. Hans L. Bodlaender. Some classes of graphs with bounded treewidth. Bulletin of the EATCS, 36:116-125, 1988. Google Scholar
  7. Glencora Borradaile, Philip N. Klein, and Claire Mathieu. An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Transactions on Algorithms, 5(3), 2009. URL: http://dx.doi.org/10.1145/1541885.1541892.
  8. Glencora Borradaile, Philip N. Klein, and Claire Mathieu. A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Transactions on Algorithms, 11(3):19:1-19:20, 2015. URL: http://dx.doi.org/10.1145/2629654.
  9. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6, 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
  10. 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: http://dx.doi.org/10.1006/jagm.1999.1042.
  11. Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev. Set connectivity problems in undirected graphs and the directed steiner network problem. ACM Transactions on Algorithms, 7(2):18, 2011. URL: http://dx.doi.org/10.1145/1921659.1921664.
  12. Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, and Mohammad R. Salavatipour. Approximation algorithms for node-weighted buy-at-bulk network design. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1265-1274, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283519.
  13. Rajesh Hemant Chitnis, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Rohit Khandekar, Guy Kortsarz, and Saeed Seddighin. A tight algorithm for strongly connected Steiner subgraph on two terminals with demands (extended abstract). In 9th International Symposium on Parameterized and Exact Computation, pages 159-171, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13524-3_14.
  14. Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, and Dániel 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, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.129.
  15. Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Philip N. Klein. Node-weighted Steiner tree and group Steiner tree in planar graphs. ACM Transactions on Algorithms, 10(3):13:1-13:20, 2014. URL: http://dx.doi.org/10.1145/2601070.
  16. Reinhard Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, third edition, 2005. Google Scholar
  17. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
  18. Jon Feldman and Matthias Ruhl. The directed Steiner network problem is tractable for a constant number of terminals. SIAM J. Comput., 36(2):543-561, 2006. URL: http://dx.doi.org/10.1137/S0097539704441241.
  19. Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci., 410(1):53-61, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.09.065.
  20. Martin Grohe and Dániel Marx. On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B, 99(1):218-228, 2009. URL: http://dx.doi.org/10.1016/j.jctb.2008.06.004.
  21. Jiong Guo, Rolf Niedermeier, and Ondrej Suchý. Parameterized complexity of arc-weighted directed Steiner problems. SIAM J. Discrete Math., 25(2):583-599, 2011. URL: http://dx.doi.org/10.1137/100794560.
  22. Richard M. Karp. Reducibility among combinatorial problems. In Complexity of computer computations, pages 85-103. Plenum, 1972. Google Scholar
  23. Philip N. Klein and R. Ravi. A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms, 19(1):104-115, 1995. URL: http://dx.doi.org/10.1006/jagm.1995.1029.
  24. Sridhar Rajagopalan and Vijay V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem. In Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 742-751, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314909.
  25. Ondřej Suchý. On directed steiner trees with multiple roots. To appear in WG 2016. arXiv:1604.05103. Google Scholar
  26. Gabriel Robins and Alexander Zelikovsky. Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math., 19(1):122-134, 2005. URL: http://dx.doi.org/10.1137/S0895480101393155.
  27. Alexander Zelikovsky. A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica, 18(1):99-110, 1997. URL: http://dx.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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact