Abstract
We introduce a new Steiner-type problem for directed graphs named q-Root Steiner Tree. Here one is given a directed graph \(G=(V,A)\) and two subsets of its vertices, R of size q and T, and the task is to find a minimum size subgraph of G that contains a path from each vertex of R to each vertex of T. The special case of this problem with \(q=1\) is the well known Directed Steiner Tree problem, while the special case with \(T=R\) is the Strongly Connected Steiner Subgraph problem.
We first show that the problem is W[1]-hard with respect to |T| for any \(q \ge 2\). Then we restrict ourselves to instances with \(R \subseteq T\) (Pedestal version). Generalizing the methods of Feldman and Ruhl [SIAM J. Comput. 2006], we present an algorithm for this restriction with running time \(O(2^{2q+4|T|}\cdot n^{2q+O(1)})\), i.e., this restriction is FPT with respect to |T| for any constant q. We further show that we can, without significantly affecting the achievable running time, loosen the restriction to only requiring that in the solution there is a vertex v and a path from each vertex of R to v and from v to each vertex of T (Trunk version).
Finally, we use the methods of Chitnis et al. [SODA 2014] to show that the Pedestal version can be solved in planar graphs in \(O(2^{O(q \log q+|T|\log q)}\cdot n^{O(\sqrt{q})})\) time.
O. Suchý—The research was supported by the grant 14-13017P of the Czech Science Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
ETH states that there is a positive constant c such that no algorithm can solve n-variable 3-SAT in \(O(2^{cn})\) time.
- 2.
Proofs of statements marked with (\(\star \)) were deferred to the full version of the paper.
References
Berman, P., Bhattacharyya, A., Makarychev, K., Raskhodnikova, S., Yaroslavtsev, G.: Approximation algorithms for spanner problems and directed Steiner forest. Inf. Comput. 222, 93–107 (2013)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets Möbius: fast subset convolution. In: STOC 2007, pp. 67–74. ACM (2007)
Charikar, M., Chekuri, C., Cheung, T.Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation algorithms for directed Steiner problems. J. Algorithms 33(1), 73–91 (1999)
Chitnis, R., Hajiaghayi, M., Marx, D.: Tight bounds for planar strongly connected Steiner subgraph with fixed number of terminals (and extensions). In: SODA 2014, pp. 1782–1801. SIAM (2014)
Chitnis, R., Hajiaghayi, M.T., Kortsarz, G.: Fixed-parameter and approximation algorithms: a new look. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 110–122. Springer, Heidelberg (2013)
Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1972)
Erickson, R.E., Monma, C.L., Veinott Jr., A.F.: Send-and-split method for minimum-concave-cost network flows. Math. Oper. Res. 12(4), 634–664 (1987)
Feldman, J., Ruhl, M.: The directed Steiner network problem is tractable for a constant number of terminals. SIAM J. Comput. 36(2), 543–561 (2006)
Feldmann, A.E., Marx, D.: The complexity landscape of fixed-parameter directed Steiner network problems. In: ICALP 2016. LIPIcs, vol. 55, pp. 27:1–27:4. Dagstuhl (2016). http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.27
Fuchs, B., Kern, W., Mölle, D., Richter, S., Rossmanith, P., Wang, X.: Dynamic programming for minimum Steiner trees. Theor. Comput. Syst. 41(3), 493–500 (2007)
Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32(4), 826–834 (1977)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Guo, J., Niedermeier, R., Suchý, O.: Parameterized complexity of arc-weighted directed Steiner problems. SIAM J. Discrete Math. 25(2), 583–599 (2011)
Hakimi, S.L.: Steiner’s problem in graphs and its implications. Networks 1, 113–133 (1971)
Halperin, E., Kortsarz, G., Krauthgamer, R., Srinivasan, A., Wang, N.: Integrality ratio for group Steiner trees and directed Steiner trees. SIAM J. Comput. 36(5), 1494–1511 (2007)
Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367–375 (2001)
Jones, M., Lokshtanov, D., Ramanujan, M.S., Saurabh, S., Suchý, O.: Parameterized complexity of directed Steiner tree on sparse graphs. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 671–682. Springer, Heidelberg (2013)
Kortsarz, G., Nutov, Z.: Approximating minimum cost connectivity problems. In: Handbook of Approximation Algorithms and Metaheuristics, chapt. 58. CRC (2007)
Levin, A.Y.: Algorithm for the shortest connection of a group of graph vertices. Sov. Math. Dokl. 12, 1477–1481 (1971)
Marx, D.: Can you beat treewidth? Theor. Comput. 6(1), 85–112 (2010)
Nederlof, J.: Fast polynomial-space algorithms using inclusion-exclusion. Algorithmica 65(4), 868–884 (2013)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)
Suchý, O.: On directed Steiner trees with multiple roots. CoRR abs/1604.05103(2016). http://arxiv.org/abs/1604.05103
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Suchý, O. (2016). On Directed Steiner Trees with Multiple Roots. In: Heggernes, P. (eds) Graph-Theoretic Concepts in Computer Science. WG 2016. Lecture Notes in Computer Science(), vol 9941. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53536-3_22
Download citation
DOI: https://doi.org/10.1007/978-3-662-53536-3_22
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53535-6
Online ISBN: 978-3-662-53536-3
eBook Packages: Computer ScienceComputer Science (R0)