We study the approximability of the NP-complete 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: Maximum Minimal Vertex Cover, for which the best achievable approximation ratio is n, and Upper Dominating Set, which does not admit any n1−ϵ approximation. We confirm and quantify this intuition by showing the first non-trivial polynomial time approximation for Maximum Minimal Feedback Vertex Set with a ratio of O(n2/3), as well as a matching hardness of approximation bound of n2/3−ϵ, improving the previously known hardness of n1/2−ϵ. 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 nO(n/r3/2). This time-approximation trade-off is essentially tight under the ETH.

A mixed dominating set $S$ of a graph $G=(V,E)$ is a subset $ S \subseteq V \cup E$ such that each element $v\in (V \cup E) \setminus S$ is adjacent or incident to at least one element in $S$. The mixed domination number $γ_m(G)$ of a graph $G$ is the minimum cardinality among all mixed dominating sets in $G$. The problem of finding $γ_{m}(G)$ is know to be NP-complete. In this paper, we present an explicit polynomial-time algorithm to construct a mixed dominating set of size $γ_{m}(G)$ by a parse tree when $G$ is a generalized series-parallel graph.