  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 factor better than $O(k)$ is known.
  We show that $k$-Steiner Orientation is unlikely to admit an approximation
algorithm with any constant factor, even within FPT running time. To obtain
this result, we construct a self-reduction via a hashing-based gap
amplification technique, which turns out useful even outside of the FPT
paradigm. Precisely, we rule out any approximation factor of the form $(\log
k)^{o(1)}$ for FPT algorithms (assuming FPT $\ne$ W[1]) and $(\log n)^{o(1)}$
for~purely polynomial-time algorithms (assuming that the class W[1] does not
admit randomized FPT algorithms). Moreover, we prove $k$-Steiner Orientation to
belong to W[1], which entails W[1]-completeness of $(\log
k)^{o(1)}$-approximation for $k$-Steiner Orientation This 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 - Max $(k,p)$-Directed Multicut - where we are given a directed graph,
$k$ terminals pairs, and a budget $p$. The goal is to maximize the number of
separated terminal pairs by removing $p$ edges. We present a simple proof that
the problem admits no FPT approximation with factor $O(k^{\frac 1 2 -
\epsilon})$ (assuming FPT $\ne$ W[1]) and no polynomial-time approximation with
ratio $O(|E(G)|^{\frac 1 2 - \epsilon})$ (assuming NP $\not\subseteq$ co-RP).
