Strongly Connected Steiner Subgraph

• INSTANCE: A directed graph $G=(V,E)$ , edge weights $c_e,e\in E$ , set of terminals $S=\{s_1,\ldots , s_p\}$
• SOLUTION: A set of edges $H\subset E$ such that for all $1\leq i,j\leq p,i\neq j$ the induced subgraph $G[H]$ contains a directed $s_i,s_j$ -path
• COST FUNCTION: $c(H)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within $p^{\epsilon}$ for every $\epsilon >0$ [27].
• Hardness: For every fixed $\epsilon >0$ , the SCSS cannot be approximated within ratio $\log^{2\textbf{-}\epsilon}n$ , unless $NP\subseteq ZTIME(n^{polylog(n)})$ [61].
• Comment: In a variant $2$ -SCSS$(k_1,k_2)$ , the number of terminals is $p=2$ , and the task is to construct a subset $H\subseteq E$ such that $G[H]$ contains $k_1$ $s_1,s_2$ -paths and $k_2$ $s_2,s_1$ -paths. The objective is to minimize $\sum_{e\in H}c_e\cdot \phi (e)$ , where $\phi (e)$ is the maximum number of $s_1,s_2$ -paths or $s_2,s_1$ -paths using edge $e$ . The $2$ -SCSS$(k,1)$ can be solved in $n^{O(k)}$ time but does not have an $f(k)\cdot n^{o(k)}$ algorithm for any computable function $f$ , unless the Exponential Time Hypothesis (ETH) fails [35].