Eiben, Eduard ;
Knop, Dusan ;
Panolan, Fahad ;
Suchý, Ondrej
Complexity of the Steiner Network Problem with Respect to the Number of Terminals
Abstract
In the Directed Steiner Network problem we are given an arcweighted 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 ExponentialTime 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.
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2019:10264,
author = {Eduard Eiben and Dusan Knop and Fahad Panolan and Ondrej Such{\'y}},
title = {{Complexity of the Steiner Network Problem with Respect to the Number of Terminals}},
booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
pages = {25:125:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771009},
ISSN = {18688969},
year = {2019},
volume = {126},
editor = {Rolf Niedermeier and Christophe Paul},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10264},
doi = {10.4230/LIPIcs.STACS.2019.25},
annote = {Keywords: Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis}
}
2019
Keywords: 

Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis 
Seminar: 

36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Issue date: 

2019 
Date of publication: 

2019 