  An upper dominating set is a minimal dominating set in a graph. In the
\textsc{Upper Dominating Set} problem, the goal is to find an upper dominating
set of maximum size. We study the complexity of parameterized algorithms for
\textsc{Upper Dominating Set}, as well as its sub-exponential approximation.
First, we prove that, under ETH, \textsc{$k$-Upper Dominating Set} cannot be
solved in time $O(n^{o(k)})$ (improving on $O(n^{o(\sqrt{k})})$), and in the
same time we show under the same complexity assumption that for any constant
ratio $r$ and any $\varepsilon > 0$, there is no $r$-approximation algorithm
running in time $O(n^{k^{1-\varepsilon}})$. Then, we settle the problem's
complexity parameterized by pathwidth by giving an algorithm running in time
$O^*(6^{pw})$ (improving the current best $O^*(7^{pw})$), and a lower bound
showing that our algorithm is the best we can get under the SETH. Furthermore,
we obtain a simple sub-exponential approximation algorithm for this problem: an
algorithm that produces an $r$-approximation in time $n^{O(n/r)}$, for any
desired approximation ratio $r < n$. We finally show that this
time-approximation trade-off is tight, up to an arbitrarily small constant in
the second exponent: under the randomized ETH, and for any ratio $r > 1$ and
$\varepsilon > 0$, no algorithm can output an $r$-approximation in time
$n^{(n/r)^{1-\varepsilon}}$. Hence, we completely characterize the
approximability of the problem in sub-exponential time.
