## Abstract

Given an edge-weighted directed graph G= (V, E) on n vertices and a set T= { t_{1}, t_{2}, … , t_{p}} of p terminals, the objective of the Strongly Connected Steiner Subgraph (p-SCSS) problem is to find an edge set H⊆ E of minimum weight such that G[H] contains an t_{i}→ t_{j} path for each 1 ≤ i≠ j≤ 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 ω: E→ R^{≥ 0}, two terminal vertices s, t, and integers k_{1}, k_{2}; the objective is to find a set of k_{1} paths F1,F2,…,Fk1 from s⇝ t and k_{2} paths B1,B2,…,Bk2 from t⇝ s such that ∑ _{e}_{∈}_{E}ω(e) · ϕ(e) is minimized, where ϕ(e)=max{|{i∈[k1]:e∈Fi}|,|{j∈[k2]:e∈Bj}|}. For each k≥ 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) · 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}} ≥ 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].

Original language | English |
---|---|

Pages (from-to) | 1216-1239 |

Number of pages | 24 |

Journal | Algorithmica |

Volume | 77 |

Issue number | 4 |

Early online date | 29 Mar 2016 |

DOIs | |

Publication status | Published - 1 Apr 2017 |

## Keywords

- Directed graphs
- Exponential time hypothesis
- FPT algorithms
- Strongly connected Steiner subgraph

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics