A tight lower bound for steiner orientation

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, Kortsarz and Nutov [ESA’12, SIDMA’13] designed an XP algorithm running in n^O(k) time for all k ≥ 1. Pilipczuk and Wahlström [SODA ’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’01] the Steiner Orientation problem does not admit an f(k) · n^o(k/logk) 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 “square-root phenomenon” on planar graphs (graphs with genus 0): can one obtain an algorithm running in time f(k) · n^O(√k) for Planar Steiner Orientation, or does the lower bound of f(k) · n^o(k) also translate to planar graphs?.