A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands

作者：Chitnis Rajesh^*; Esfandiari Hossein; Hajiaghayi MohammadTaghi; Khandekar Rohit; Kortsarz Guy; Seddighin Saeed

来源：Algorithmica, 2017, 77(4): 1216-1239.

DOI：10.1007/s00453-016-0145-8

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

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 subset of E of minimum weight such that G[H] contains an t(i) -> t(j) path for each 1 <= i not equal 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 omega : 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 F-1, F-2, ... , F-k1 from s -> t and k(2) paths B-1, B-2, ... , B-k2 from t -> s such that Sigma(omega(e) . phi(e))(e is an element of E) is minimized, where phi(e) = max {vertical bar{i is an element of [k(1)] : e is an element of F-i}vertical bar, vertical bar{j is an element of [k(2)] : e is an element of B-j}vertical bar}. 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].

• 出版日期2017-4
• 单位rutgers