  We consider questions that arise from the intersection between the areas of
polynomial-time approximation algorithms, subexponential-time algorithms, and
fixed-parameter tractable algorithms. The questions, which have been asked
several times (e.g., [Marx08, FGMS12, DF13]), are whether there is a
non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and
Minimum Dominating Set (DomSet) problems parameterized by the size of the
optimal solution. In particular, letting $\text{OPT}$ be the optimum and $N$ be
the size of the input, is there an algorithm that runs in
$t(\text{OPT})\text{poly}(N)$ time and outputs a solution of size
$f(\text{OPT})$, for any functions $t$ and $f$ that are independent of $N$ (for
Clique, we want $f(\text{OPT})=\omega(1)$)?
  In this paper, we show that both Clique and DomSet admit no non-trivial
FPT-approximation algorithm, i.e., there is no
$o(\text{OPT})$-FPT-approximation algorithm for Clique and no
$f(\text{OPT})$-FPT-approximation algorithm for DomSet, for any function $f$
(e.g., this holds even if $f$ is the Ackermann function). In fact, our results
imply something even stronger: The best way to solve Clique and DomSet, even
approximately, is to essentially enumerate all possibilities. Our results hold
under the Gap Exponential Time Hypothesis (Gap-ETH) [Dinur16, MR16], which
states that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable
3SAT formula and one which is not even $(1 - \epsilon)$-satisfiable for some
constant $\epsilon > 0$.
  Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for
Maximum Balanced Biclique, Maximum Subgraphs with Hereditary Properties, and
Maximum Induced Matching in bipartite graphs. Additionally, we rule out
$k^{o(1)}$-FPT-approximation algorithm for Densest $k$-Subgraph although this
ratio does not yet match the trivial $O(k)$-approximation algorithm.
