2015/06/11 by Rajesh Chitnis, Hossein Esfandiari, Chitnis, Rajesh +9
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1506.03760
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 \scss (p-SCSS) problem is to find an edge set H⊆ E of minimum weight such that G[H] contains an ti→ tj path for each 1≤ i≠ j≤ p. 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 \sharinggeneral problem is defined as follows: given an edge-weighted directed graph G=(V,E) with weight function ω: E→ ℝ≥ 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\leadsto t and k2 paths B1, B2, …, Bk2 from t\leadsto 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 \sharing problem can be solved in nO(k) time. A matching lower bound for our algorithm: the \sharing 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 \sharing 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 \sharinggeneral problem if min\k1, k2\≥ 2. Therefore \sharing is the most general problem one can attempt to solve with our techniques.