2026-07-22T20:50:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10264 2024-03-06T10:45:40Z ddc:004 open_access

Complexity of the Steiner Network Problem with Respect to the Number of Terminals Eiben, Eduard Knop, Dušan Panolan, Fahad Suchý, Ondřej Directed Steiner Network Planar Graphs Parameterized Algorithms Bounded Genus Exponential Time Hypothesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Dušan Knop and Fahad Panolan and Ondřej Suchý 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.25 urn:nbn:de:0030-drops-102642 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.25 eng https://creativecommons.org/licenses/by/3.0/legalcode