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 $Deltage 9$ to $Deltage 6$. Having settled the problems 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.
Download