A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

-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

o m e g a : E i g h t a r r o w m a t h b b R^{g e q 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}, l d o t s, F_{k_{1}}

from

s l e a d s t o t

and

k_{2}

paths

B_{1}, B_{2}, l d o t s, B_{k_{2}}

from

t l e a d s t o s

such that

s u m_{e i n E} o m e g a (e) c d o t p h i (e)

is minimized, where

p h i (e) = m a x B i g | i i n [k_{1}] : e i n F_{i} |, | j i n [k_{2}] : e i n B_{j} | B i g

. For each

k g e q 1

, we show the following: The sharing problem can be solved in

n^{O (k)}

time. A matching lower bound for our algorithm: the sharing problem does not have an

f (k) c d o t n^{o (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

m i n k_{1}, k_{2} g e q 2

. Therefore sharing is the most general problem one can attempt to solve with our techniques.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946016)