## 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’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 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) · n^{o}^{(}^{k}^{/}^{log}^{k}^{)} algorithm for any computable function f. 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 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. 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) · n^{o}^{(}^{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.

Original language | English |
---|---|

Pages (from-to) | 3200-3216 |

Number of pages | 17 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 8 |

Early online date | 4 May 2019 |

DOIs | |

Publication status | Published - 1 Aug 2019 |

## ASJC Scopus subject areas

- Computer Science(all)
- Computer Science Applications
- Applied Mathematics