A Tight Lower Bound for Steiner Orientation

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10386943" target="_blank" >RIV/00216208:11320/18:10386943 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/978-3-319-90530-3_7" target="_blank" >https://doi.org/10.1007/978-3-319-90530-3_7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-90530-3_7" target="_blank" >10.1007/978-3-319-90530-3_7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

A Tight Lower Bound for 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 -&gt; t path for each terminal pair (s, t) is an element of T. Arkin and Hassin [DAM&apos; 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, Kortsarz and Nutov [ESA&apos;12, SIDMA&apos;13] designed an XP algorithm running in n(O(k)) time for all k &gt;= 1. Pilipczuk andWahlstrom [SODA&apos;16] 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&apos;01] the Steiner Orientation problem does not admit an f(k).n(o(k/log k)) algorithm for any computable function f. That is, the n(O(k)) algorithm of Cygan et al. is almost optimal. In this paper, we give a short and easy proof that the n(O(k)) algorithm of Cygan et al. is asymptotically optimal, even if the input graph has genus 1. Formally, we show that the 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 function f even if the underlying undirected graph has genus 1. We give a reduction from the Grid Tiling problem which has turned out to be very useful in proving W[1]-hardness of several problems on planar graphs. As a result of our work, the main remaining open question is whether Steiner Orientation admits the &quot;square-root phenomenon&quot; on planar graphs (graphs with genus 0): can one obtain an algorithm running in time f(k).n(O(root k)) for Planar Steiner Orientation, or does the lower bound of f(k).n(O(k))) also translate to planar graphs?

Název v anglickém jazyce

A Tight Lower Bound for 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 -&gt; t path for each terminal pair (s, t) is an element of T. Arkin and Hassin [DAM&apos; 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, Kortsarz and Nutov [ESA&apos;12, SIDMA&apos;13] designed an XP algorithm running in n(O(k)) time for all k &gt;= 1. Pilipczuk andWahlstrom [SODA&apos;16] 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&apos;01] the Steiner Orientation problem does not admit an f(k).n(o(k/log k)) algorithm for any computable function f. That is, the n(O(k)) algorithm of Cygan et al. is almost optimal. In this paper, we give a short and easy proof that the n(O(k)) algorithm of Cygan et al. is asymptotically optimal, even if the input graph has genus 1. Formally, we show that the 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 function f even if the underlying undirected graph has genus 1. We give a reduction from the Grid Tiling problem which has turned out to be very useful in proving W[1]-hardness of several problems on planar graphs. As a result of our work, the main remaining open question is whether Steiner Orientation admits the &quot;square-root phenomenon&quot; on planar graphs (graphs with genus 0): can one obtain an algorithm running in time f(k).n(O(root k)) for Planar Steiner Orientation, or does the lower bound of f(k).n(O(k))) also translate to planar graphs?

Druh

D - Stať ve sborníku

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í

2018

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 statě ve sborníku

COMPUTER SCIENCE - THEORY AND APPLICATIONS, CSR 2018

ISBN

978-3-319-90529-7

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

13

Strana od-do

65-77

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Higher Sch Economics

Datum konání akce

6. 6. 2018

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000445826800007