dc.contributor.author | Eiben, Eduard | |
dc.contributor.author | Knop, Dusan | |
dc.contributor.author | Panolan, Fahad | |
dc.contributor.author | Suchý, Ondřej | |
dc.date.accessioned | 2021-01-13T12:53:30Z | |
dc.date.available | 2021-01-13T12:53:30Z | |
dc.date.created | 2019-12-12T13:39:40Z | |
dc.date.issued | 2019 | |
dc.Published | Leibniz International Proceedings in Informatics. 2019, 126, 25:1-25:17. | en_US |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2722779 | |
dc.description.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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Complexity of the Steiner Network Problem with Respect to the Number of Terminals | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2019 The Authors | en_US |
dc.source.articlenumber | 25 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.STACS.2019.25 | |
dc.identifier.cristin | 1760060 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.40 | 126 | en_US |
dc.source.pagenumber | 25:1-25:17 | en_US |