TIGHT BOUNDS FOR PLANAR STRONGLY CONNECTED STEINER SUBGRAPH WITH FIXED NUMBER OF TERMINALS (AND EXTENSIONS)

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420358" target="_blank" >RIV/00216208:11320/20:10420358 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Dj.bGq4SDu" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Dj.bGq4SDu</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/18M122371X" target="_blank" >10.1137/18M122371X</a>

Jazyk výsledku

angličtina

Název v původním jazyce

TIGHT BOUNDS FOR PLANAR STRONGLY CONNECTED STEINER SUBGRAPH WITH FIXED NUMBER OF TERMINALS (AND EXTENSIONS)

Popis výsledku v původním jazyce

Given a vertex-weighted directed graph G = (V, E) and a set T = {t(1), t(2), ..., t(k)} of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H subset of V of minimum weight such that G[H] contains a t(i) -&gt; t(j) path for each i not equal j. The prob- lem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543-561] gave a novel n(O(k)) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2(O(k)).n(O(root k)) algorithm for planar SCSS, which is an improvement of a factor of O(root k) in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k).n(o(root k)) algorithm for any computable function f, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is O(root k), and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, https://arxiv.org/abs/1707.06808] . To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our 2(O(k)).n(O(root k)) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the n(O(k)) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k).n(o(k/log k)) algorithm for any computable function f. Feldman and Ruhl generalized their n(O(k)) algorithm to the more general DIRECTED STEINER NETWORK (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source s(i) there is a path to the corresponding terminal t(i). We show that, assuming ETH, there is no f(k).n(o(k)) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

Název v anglickém jazyce

TIGHT BOUNDS FOR PLANAR STRONGLY CONNECTED STEINER SUBGRAPH WITH FIXED NUMBER OF TERMINALS (AND EXTENSIONS)

Popis výsledku anglicky

Given a vertex-weighted directed graph G = (V, E) and a set T = {t(1), t(2), ..., t(k)} of k terminals, the objective of the STRONGLY CONNECTED STEINER SUBGRAPH (SCSS) problem is to find a vertex set H subset of V of minimum weight such that G[H] contains a t(i) -&gt; t(j) path for each i not equal j. The prob- lem is NP-hard, but Feldman and Ruhl [SIAM J. Comput., 36 (2006), pp. 543-561] gave a novel n(O(k)) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a 2(O(k)).n(O(root k)) algorithm for planar SCSS, which is an improvement of a factor of O(root k) in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an f(k).n(o(root k)) algorithm for any computable function f, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is O(root k), and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, https://arxiv.org/abs/1707.06808] . To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our 2(O(k)).n(O(root k)) algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the n(O(k)) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k).n(o(k/log k)) algorithm for any computable function f. Feldman and Ruhl generalized their n(O(k)) algorithm to the more general DIRECTED STEINER NETWORK (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source s(i) there is a path to the corresponding terminal t(i). We show that, assuming ETH, there is no f(k).n(o(k)) time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

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

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název periodika

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

49

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

47

Strana od-do

318-364

Kód UT WoS článku

000546873800003

EID výsledku v databázi Scopus

2-s2.0-85084462604