A Tight Lower Bound for Planar Steiner Orientation
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403064" target="_blank" >RIV/00216208:11320/19:10403064 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/19:00338417
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cR7ytSXKfQ" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cR7ytSXKfQ</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-019-00580-x" target="_blank" >10.1007/s00453-019-00580-x</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
A Tight Lower Bound for Planar Steiner Orientation
Popis výsledku v původním jazyce
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs T. The question is whether we can orient the undirected edges in a way such that there is a directed s-t path for each terminal pair (s,t)T. Arkin and Hassin [DAM'02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when k=2. From the viewpoint of exact algorithms, Cygan et al.[ESA'12, SIDMA'13] designed an XP algorithm running in n^O(k) time for all k>=1. Pilipczuk and Wahlstrom [SODA'16, TOCT'18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS'01] the Steiner Orientation problem does not admit an f(k)*n^o(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the n^O(k) algorithm of Cygan etal. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in f(k)n^o(k) time for any computable function f.
Název v anglickém jazyce
A Tight Lower Bound for Planar Steiner Orientation
Popis výsledku anglicky
In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs T. The question is whether we can orient the undirected edges in a way such that there is a directed s-t path for each terminal pair (s,t)T. Arkin and Hassin [DAM'02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when k=2. From the viewpoint of exact algorithms, Cygan et al.[ESA'12, SIDMA'13] designed an XP algorithm running in n^O(k) time for all k>=1. Pilipczuk and Wahlstrom [SODA'16, TOCT'18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS'01] the Steiner Orientation problem does not admit an f(k)*n^o(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the n^O(k) algorithm of Cygan etal. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in f(k)n^o(k) time for any computable function f.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2019
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ů
Údaje specifické pro druh výsledku
Název periodika
Algorithmica
ISSN
0178-4617
e-ISSN
—
Svazek periodika
81
Číslo periodika v rámci svazku
8
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
17
Strana od-do
3200-3216
Kód UT WoS článku
000472831500007
EID výsledku v databázi Scopus
2-s2.0-85065334356