Publication Date:
2016-03-30
Description:
Given an edge-weighted directed graph \(G=(V,E)\) on n vertices and a set \(T=\{t_1, t_2, \ldots , t_p\}\) of p terminals, the objective of the Strongly Connected Steiner Subgraph ( p -SCSS) problem is to find an edge set \(H\subseteq E\) of minimum weight such that G [ H ] contains an \(t_{i}\rightarrow t_j\) path for each \(1\le i\ne j\le p\) . The p -SCSS problem is NP-hard, but Feldman and Ruhl [FOCS ’99; SICOMP ’06] gave a novel \(n^{O(p)}\) time algorithm. In this paper, we investigate the computational complexity of a variant of 2-SCSS where we have demands for the number of paths between each terminal pair. Formally, the \(2\) -SCSS- \((k_1, k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) with weight function \(\omega : E\rightarrow {\mathbb {R}}^{\ge 0}\) , two terminal vertices s , t , and integers \(k_1, k_2\) ; the objective is to find a set of \(k_1\) paths \(F_1, F_2, \ldots , F_{k_1}\) from \(s\leadsto t\) and \(k_2\) paths \(B_1, B_2, \ldots , B_{k_2}\) from \(t\leadsto s\) such that \(\sum _{e\in E} \omega (e)\cdot \phi (e)\) is minimized, where \(\phi (e)= \max \Big \{|\{i\in [k_1] : e\in F_i\}|\ ,\ |\{j\in [k_2] : e\in B_j\}|\Big \}\) . For each \(k\ge 1\) , we show the following: The \(2\) -SCSS- \((k,1)\) problem can be solved in time \(n^{O(k)}\) . A matching lower bound for our algorithm: the \(2\) -SCSS- \((k,1)\) problem does not have an \(f(k)\cdot n^{o(k)}\) time algorithm for any computable function f , unless the Exponential Time Hypothesis fails. Our algorithm for \(2\) -SCSS- \((k,1)\) relies on a structural result regarding an optimal solution followed by using the idea of a “token game” similar to that of Feldman and Ruhl. We show with an example that the structural result does not hold for the \(2\) -SCSS- \((k_1, k_2)\) problem if \(\min \{k_1, k_2\}\ge 2\) . Therefore \(2\) -SCSS- \((k,1)\) is the most general problem one can attempt to solve with our techniques. To obtain the lower bound matching the algorithm, we reduce from a special variant of the Grid Tiling problem introduced by Marx [FOCS ’07; ICALP ’12].
Print ISSN:
0178-4617
Electronic ISSN:
1432-0541
Topics:
Computer Science
,
Mathematics
Permalink