The Strongly Connected Steiner Subgraph (SCSS) problem only demands strong connectivity between a set of terminals: nothing is specified about how many (disjoint) paths are required between each pair of terminals. Chitnis et al. [IPEC ’14, Algorithmica ’17] introduced a variant of SCSS (on two terminals) with demands for the number of paths between the two terminal pairs. Formally, the \(2\) -SCSS- \((k_1,k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) on n vertices with weight function \(\omega : E\rightarrow \mathbb {R}^{\ge 0}\) , two terminal vertices s, t, and integers \(k_1, k_2, p\) ; the question is whether there exists 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)\le p\) , 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\) , Chitnis et al. [IPEC ’14, Algorithmica ’17] designed a \(n^{O(k)}\) time algorithm for graphs with n vertices, and obtained a matching lower bound of \(f(k)\cdot n^{o(k)}\)  under the Exponential Time Hypothesis (ETH) for any computable function f. In this paper, we address the next natural questions for the \(2\) -SCSS- \((k,1)\) problem: As a consequence of our results, we also obtain W[1]-hardness of the \(2\) -SCSS- \((k,1)\) problem on general graphs parameterized by the cost p of the solution: this does not follow from the W[1]-hardness proof of Chitnis et al. [IPEC ’14, Algorithmica ’17] since the value of p in their reduction was a function of both k and n.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Exact & Approximate Complexity of the Strongly Connected Steiner Subgraph Problem on Two Terminals with Demands

  • Kevin Kurien Alex,
  • Rajesh Chitnis,
  • Alex Tempest

摘要

The Strongly Connected Steiner Subgraph (SCSS) problem only demands strong connectivity between a set of terminals: nothing is specified about how many (disjoint) paths are required between each pair of terminals. Chitnis et al. [IPEC ’14, Algorithmica ’17] introduced a variant of SCSS (on two terminals) with demands for the number of paths between the two terminal pairs. Formally, the \(2\) -SCSS- \((k_1,k_2)\) problem is defined as follows: given an edge-weighted directed graph \(G=(V,E)\) on n vertices with weight function \(\omega : E\rightarrow \mathbb {R}^{\ge 0}\) , two terminal vertices s, t, and integers \(k_1, k_2, p\) ; the question is whether there exists 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)\le p\) , 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\) , Chitnis et al. [IPEC ’14, Algorithmica ’17] designed a \(n^{O(k)}\) time algorithm for graphs with n vertices, and obtained a matching lower bound of \(f(k)\cdot n^{o(k)}\)  under the Exponential Time Hypothesis (ETH) for any computable function f. In this paper, we address the next natural questions for the \(2\) -SCSS- \((k,1)\) problem: As a consequence of our results, we also obtain W[1]-hardness of the \(2\) -SCSS- \((k,1)\) problem on general graphs parameterized by the cost p of the solution: this does not follow from the W[1]-hardness proof of Chitnis et al. [IPEC ’14, Algorithmica ’17] since the value of p in their reduction was a function of both k and n.