A tight lower bound for planar Steiner Orientation

Research output: Contribution to journalArticlepeer-review

Standard

A tight lower bound for planar Steiner Orientation. / Chitnis, Rajesh; Feldmann, Andreas Emil; Suchý, Ondřej.

In: Algorithmica, Vol. 81, No. 8, 01.08.2019, p. 3200-3216.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Chitnis, Rajesh ; Feldmann, Andreas Emil ; Suchý, Ondřej. / A tight lower bound for planar Steiner Orientation. In: Algorithmica. 2019 ; Vol. 81, No. 8. pp. 3200-3216.

Bibtex

@article{eeea11aa313d4a7a933a29d2e85f67ef,
title = "A tight lower bound for planar Steiner Orientation",
abstract = "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{\textquoteright}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{\textquoteright}12, SIDMA{\textquoteright}13] designed an XP algorithm running in nO(k) time for all k≥ 1. Pilipczuk and Wahlstr{\"o}m [SODA{\textquoteright}16, TOCT{\textquoteright}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{\textquoteright}01] the Steiner Orientation problem does not admit an f(k) · no(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan et al. 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) · no(k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC{\textquoteright}16] and Manurangsi and Raghavendra [ICALP{\textquoteright}17], we are able to show that there is no constant ϑ> 0 such that Planar Steiner Orientation admits an (1920+ϑ)-approximation in FPT time, i.e., no f(k) · no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k·(1920+ϑ) pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.",
author = "Rajesh Chitnis and Feldmann, {Andreas Emil} and Ond{\v r}ej Such{\'y}",
year = "2019",
month = aug,
day = "1",
doi = "10.1007/s00453-019-00580-x",
language = "English",
volume = "81",
pages = "3200--3216",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer",
number = "8",

}

RIS

TY - JOUR

T1 - A tight lower bound for planar Steiner Orientation

AU - Chitnis, Rajesh

AU - Feldmann, Andreas Emil

AU - Suchý, Ondřej

PY - 2019/8/1

Y1 - 2019/8/1

N2 - 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 nO(k) time for all k≥ 1. Pilipczuk and Wahlström [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) · no(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan et al. 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) · no(k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant ϑ> 0 such that Planar Steiner Orientation admits an (1920+ϑ)-approximation in FPT time, i.e., no f(k) · no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k·(1920+ϑ) pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

AB - 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 nO(k) time for all k≥ 1. Pilipczuk and Wahlström [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) · no(k/logk) algorithm for any computable function f. In this paper, we give a short and easy proof that the nO(k) algorithm of Cygan et al. 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) · no(k) time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant ϑ> 0 such that Planar Steiner Orientation admits an (1920+ϑ)-approximation in FPT time, i.e., no f(k) · no(k) time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than k·(1920+ϑ) pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

UR - http://www.scopus.com/inward/record.url?scp=85065334356&partnerID=8YFLogxK

U2 - 10.1007/s00453-019-00580-x

DO - 10.1007/s00453-019-00580-x

M3 - Article

AN - SCOPUS:85065334356

VL - 81

SP - 3200

EP - 3216

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 8

ER -