Paper Info
Title
A Tight Algorithm For Strongly Connected Steiner Subgraph On Two Terminals With Demands
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 (SCSS) problem is to find an edge set H subset of E of minimum weight such that G[H] contains a ti -> tj path for each 1 <= i not equal j <= p. The problem is NP-hard, but Feldman and Ruhl [FOCS '99; SICOMP '06] gave a novel n(O(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-(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(e is an element of E)omega(e).phi(e) is minimized, where phi(e) = max {vertical bar{i : i is an element of [k(1)], e is an element of F-i}vertical bar; vertical bar{j : 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 n(O(k)) time.A matching lower bound for our algorithm: the 2-SCSS-(k, 1) problem does not have an f(k) . n(o(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-(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].
Year
DOI
Venue
2014
10.1007/978-3-319-13524-3_14
PARAMETERIZED AND EXACT COMPUTATION, IPEC 2014
Field
DocType
Volume
Discrete mathematics,Combinatorics,Vertex (geometry),Directed graph,Algorithm,Minimum weight,Strongly connected component,Mathematics
Conference
8894
ISSN
Citations 
PageRank 
0302-9743
3
0.39
References 
Authors
8
6
Name
Order
Citations
PageRank
Rajesh Hemant Chitnis11018.44
Hossein Esfandiari28815.38
MohammadTaghi Hajiaghayi33082201.38
Rohit Khandekar4105767.79
Guy Kortsarz51539126.16
Saeed Seddighin63512.24