Inapproximability within W[1]: the case of Steiner Orientation.
Michał Włodarczyk · arXiv (Cornell University) · 2019
In the $k$-Steiner Orientation problem we are given a mixed graph, that is, with both directed and undirected edges, and a set of $k$ terminal pairs. The goal is to find an orientation of the undirected edges that maximizes the number of terminal pairs for which there is a path from the source to the sink. The problem is known to be W[1]-hard when parameterized by $k$ and hard to approximate up to some constant for FPT algorithms assuming Gap-ETH. On the other hand, no approximation better than $O(k)$ is known. We show that $k$-Steiner Orientation admits no sublogarithmic approximation algorithm, even with a parameterized running time, assuming W[1] $ e$ FPT. To obtain this result, we reduce the problem to itself via a hashing-based gap amplification technique, which turns out useful even outside of the FPT paradigm. Precisely, we rule out any approximation ratio of the form $(\log k)^{o(1)}$ for parameterized algorithms and $(\log n)^{o(1)}$ for purely polynomial running time, under the same assumption. This constitutes a novel inapproximability result for polynomial time algorithms obtained via tools from the FPT theory. Moreover, we prove $k$-Steiner Orientation to be W[1]-complete, what provides an example of a natural approximation task that is complete in a parameterized complexity class. Finally, we apply our technique to the maximization version of Directed Multicut and obtain a simple proof that the problem admits no FPT approximation with ratio $O(k^{\frac 1 2 - \epsilon})$ (assuming W[1] $ e$ FPT) and no polynomial-time approximation with ratio $O(m^{\frac 1 2 - \epsilon})$ (assuming NP $ ot\subseteq$ co-RP).