TY - GEN
T1 - A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
AU - Chitnis, Rajesh Hemant
AU - Esfandiari, Hossein
AU - Hajiaghayi, Mohammad Taghi
AU - Khandekar, Rohit
AU - Kortsarz, Guy
AU - Seddighin, Saeed
PY - 2014/12/3
Y1 - 2014/12/3
N2 - Given an edge-weighted directed graph G = (V, E) on n vertices and a set T = {t1, t2,… tp} of p terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find an edge set H ⊆ E of minimum weight such that G[H] contains a ti → tj path for each 1 ≤ i _= j ≤ p. The problem is NP-hard, but Feldman and Ruhl [FOCS’99; SICOMP’06] gave a novel nO(p) algorithm for the p-SCSS problem. 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-(k1, k2) problem is defined as follows: given an edge-weighted directed graph G = (V, E) with weight function ω: E → R≥0, two terminal vertices s, t, and integers k1, k2; the objective is to find a set of k1 paths F1, F2,…, Fk1 from s → t and k2 paths B1, B2,…, Bk2 from t → s such that ∑e∈E ω(e)·φ(e) is minimized, where φ(e) = max{|{i: i ∈ [k1], e ∈ Fi}|; |{j: j ∈ [k2], e ∈ Bj}|}. For each k ≥ 1, we show the following:-The 2-SCSS-(k, 1) problem can be solved in nO(k) time.-A matching lower bound for our algorithm: the 2-SCSS-(k, 1) problem does not have an f(k) · no(k) algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for 2-SCSS-(k, 1) relies on a structural result regarding the 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-(k1, k2) problem if min{k1, k2} ≥ 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].
AB - Given an edge-weighted directed graph G = (V, E) on n vertices and a set T = {t1, t2,… tp} of p terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find an edge set H ⊆ E of minimum weight such that G[H] contains a ti → tj path for each 1 ≤ i _= j ≤ p. The problem is NP-hard, but Feldman and Ruhl [FOCS’99; SICOMP’06] gave a novel nO(p) algorithm for the p-SCSS problem. 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-(k1, k2) problem is defined as follows: given an edge-weighted directed graph G = (V, E) with weight function ω: E → R≥0, two terminal vertices s, t, and integers k1, k2; the objective is to find a set of k1 paths F1, F2,…, Fk1 from s → t and k2 paths B1, B2,…, Bk2 from t → s such that ∑e∈E ω(e)·φ(e) is minimized, where φ(e) = max{|{i: i ∈ [k1], e ∈ Fi}|; |{j: j ∈ [k2], e ∈ Bj}|}. For each k ≥ 1, we show the following:-The 2-SCSS-(k, 1) problem can be solved in nO(k) time.-A matching lower bound for our algorithm: the 2-SCSS-(k, 1) problem does not have an f(k) · no(k) algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. Our algorithm for 2-SCSS-(k, 1) relies on a structural result regarding the 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-(k1, k2) problem if min{k1, k2} ≥ 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].
UR - http://www.scopus.com/inward/record.url?scp=84920000589&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-13524-3_14
DO - 10.1007/978-3-319-13524-3_14
M3 - Conference contribution
AN - SCOPUS:84920000589
SN - 9783319135236
T3 - Lecture Notes in Computer Science
SP - 159
EP - 171
BT - Parameterized and Exact Computation
A2 - Cygan, Marek
A2 - Heggernes, Pinar
PB - Springer Verlag
T2 - 9th International Symposium on Parameterized and Exact Computation, IPEC 2014
Y2 - 10 September 2014 through 12 September 2014
ER -