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)$$G=(V,E) on n vertices and a set $$T=\\{t_1, t_2, \\ldots , t_p\\}$$T={t1,t2,¿,tp} of p terminals, the objective of the Strongly Connected Steiner Subgraph (p-SCSS) problem is to find an edge set $$H\\subseteq E$$H⊆E of minimum weight such that G[H] contains an $$t_{i}\\rightarrow t_j$$ti¿tj path for each $$1\\le i\\ne j\\le p$$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)}$$nO(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$$2-SCSS-$$(k_1, k_2)$$(k1,k2) problem is defined as follows: given an edge-weighted directed graph $$G=(V,E)$$G=(V,E) with weight function $$\\omega : E\\rightarrow {\\mathbb {R}}^{\\ge 0}$$¿:E¿R¿0, two terminal vertices s, t, and integers $$k_1, k_2$$k1,k2; the objective is to find a set of $$k_1$$k1 paths $$F_1, F_2, \\ldots , F_{k_1}$$F1,F2,¿,Fk1 from $$s\\leadsto t$$s¿t and $$k_2$$k2 paths $$B_1, B_2, \\ldots , B_{k_2}$$B1,B2,¿,Bk2 from $$t\\leadsto s$$t¿s such that $$\\sum _{e\\in E} \\omega (e)\\cdot \\phi (e)$$¿e¿E¿(e)·¿(e) is minimized, where $$\\phi (e)= \\max \\Big \\{|\\{i\\in [k_1] : e\\in F_i\\}|\\ ,\\ |\\{j\\in [k_2] : e\\in B_j\\}|\\Big \\}$$¿(e)=max{|{i¿[k1]:e¿Fi}|,|{j¿[k2]:e¿Bj}|}. For each $$k\\ge 1$$k¿1, we show the following:The $$2$$2-SCSS-$$(k,1)$$(k,1) problem can be solved in time $$n^{O(k)}$$nO(k).A matching lower bound for our algorithm: the $$2$$2-SCSS-$$(k,1)$$(k,1) problem does not have an $$f(k)\\cdot n^{o(k)}$$f(k)·no(k) time algorithm for any computable function f, unless the Exponential Time Hypothesis fails. Our algorithm for $$2$$2-SCSS-$$(k,1)$$(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$$2-SCSS-$$(k_1, k_2)$$(k1,k2) problem if $$\\min \\{k_1, k_2\\}\\ge 2$$min{k1,k2}¿2. Therefore $$2$$2-SCSS-$$(k,1)$$(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
2015
10.1007/s00453-016-0145-8
Algorithmica
Keywords
Field
DocType
FPT algorithms,Directed graphs,Strongly connected Steiner subgraph,Exponential time hypothesis
Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Algorithm,Omega,Strongly connected component,Mathematics,Computable function,Exponential time hypothesis
Journal
Volume
Issue
ISSN
abs/1506.03760
4
0178-4617
Citations 
PageRank 
References 
0
0.34
16
Authors
6
Name
Order
Citations
PageRank
Rajesh Chitnis182.92
Hossein Esfandiari28815.38
MohammadTaghi Hajiaghayi33082201.38
Rohit Khandekar4105767.79
Guy Kortsarz51539126.16
Saeed Seddighin63512.24