Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Abstract

In the Directed Steiner Network problem we are given an arc-weighted digraph $G$, a set of terminals $T\subseteq V(G)$, and an (unweighted) directed request graph $R$ with $V(R)=T$. Our task is to output a subgraph $G^{\prime }\subseteq G$ of the minimum cost such that there is a directed path from $s$ to $t$ in $G^{\prime }$ for all $st\in A(R)$. It is known that the problem can be solved in time $|V(G){|}^{O(|A(R)|)}$ [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G){|}^{o(|A(R)|)}$ even if $G$ is planar, unless Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, as this reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G){|}^{o(|T|)}$ unless ETH fails, there is a significant gap in the complexity with respect to $|T|$ in the exponent. We show that Directed Steiner Network is solvable in time $f(R)\cdot |V(G){|}^{O(c_g\cdot |T|)}$, 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(R)\cdot |V(G){|}^{o(|T{|}^2/\log |T|)}$ algorithm for any function $f$ for the problem on general graphs, unless ETH fails.