Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00334098" target="_blank" >RIV/68407700:21240/19:00334098 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2019.25" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2019.25</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2019.25" target="_blank" >10.4230/LIPIcs.STACS.2019.25</a>

Result language

angličtina

Original language name

Complexity of the Steiner Network Problem with Respect to the Number of Terminals

Original language description

In the Directed Steiner Network problem we are given an arc-weighted digraph G, a set of terminals $Tsubseteq V(G)$ with |T|=q, and an (unweighted) directed request graph R with V(R)=T. Our task is to output a subgraph $H subseteq G$ of the minimum cost such that there is a directed path from s to t in H for all st in A(R). It is known that the problem can be solved in time $|V(G)|^{O(|A(R)|)}$ [Feldman&Ruhl, SIAM J. Comput. 2006] and cannot be solved in time $|V(G)|^{o(|A(R)|)}$ even if G is planar, unless the Exponential-Time Hypothesis (ETH) fails [Chitnis et al., SODA 2014]. However, the reduction (and other reductions showing hardness of the problem) only shows that the problem cannot be solved in time $|V(G)|^{o(q)}$, unless ETH fails. Therefore, there is a significant gap in the complexity with respect to q in the exponent. We show that textsc{Directed Steiner Network} is solvable in time $f(q)cdot |V(G)|^{O(c_g cdot q)}$, where $c_g$ is a constant depending solely on the genus of G and f is a computable function. We complement this result by showing that there is no $f(q)cdot |V(G)|^{o(q^2/ log q)}$ algorithm for any function f for the problem on general graphs, unless ETH fails.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GA17-20065S" target="_blank" >GA17-20065S: Tight Parameterized Results for Directed Connectivity Problems</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany

ISBN

978-3-95977-100-9

ISSN

—

e-ISSN

1868-8969

Number of pages

17

Pages from-to

"25:1"-"25:17"

Publisher name

Schloss Dagstuhl - Leibniz Center for Informatics

Place of publication

Wadern

Event location

Berlín

Event date

Mar 13, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000472795800024