  We study the approximability of the NP-complete \textsc{Maximum Minimal
Feedback Vertex Set} problem. Informally, this natural problem seems to lie in
an intermediate space between two more well-studied problems of this type:
\textsc{Maximum Minimal Vertex Cover}, for which the best achievable
approximation ratio is $\sqrt{n}$, and \textsc{Upper Dominating Set}, which
does not admit any $n^{1-\epsilon}$ approximation. We confirm and quantify this
intuition by showing the first non-trivial polynomial time approximation for
\textsc{Max Min FVS} with a ratio of $O(n^{2/3})$, as well as a matching
hardness of approximation bound of $n^{2/3-\epsilon}$, improving the previous
known hardness of $n^{1/2-\epsilon}$. The approximation algorithm also gives a
cubic kernel when parameterized by the solution size. Along the way, we also
obtain an $O(\Delta)$-approximation and show that this is asymptotically best
possible, and we improve the bound for which the problem is NP-hard from
$\Delta\ge 9$ to $\Delta\ge 6$.
  Having settled the problem's approximability in polynomial time, we move to
the context of super-polynomial time. We devise a generalization of our
approximation algorithm which, for any desired approximation ratio $r$,
produces an $r$-approximate solution in time $n^{O(n/r^{3/2})}$. This
time-approximation trade-off is essentially tight: we show that under the ETH,
for any ratio $r$ and $\epsilon>0$, no algorithm can $r$-approximate this
problem in time $n^{O((n/r^{3/2})^{1-\epsilon})}$, hence we precisely
characterize the approximability of the problem for the whole spectrum between
polynomial and sub-exponential time, up to an arbitrarily small constant in the
second exponent.
