# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### \(\mathcal{F}\)-Deletion Problems  
Let \(\mathcal{F}\) be a vertex-hereditary family of undirected graphs, which means that if \(G\in\mathcal{F}\) and \(H\) is a vertex-induced subgraph of \(G\), then \(H\in\mathcal{F}\) as well. \(\mathcal{F}\textsc{-Deletion}\) is the problem where given a graph \(G=(V,E)\), we are supposed to find \(S\subseteq V\) such that the subgraph induced by \(V\setminus S\) (denoted by \(G\setminus S\)) belongs to \(\mathcal{F}\). The goal is to minimize \(|S|\). The natural weighted version, where there is a non-negative weight \(w(v)\) for each vertex \(v\) and the goal is to minimize the sum of the weights of the vertices in \(S\), is called Weighted \(\mathcal{F}\)-Deletion. \(\mathcal{F}\textsc{-Deletion}\) captures numerous combinatorial optimization problems, including Vertex Cover (when \(\mathcal{F}\) includes all graphs with no edges), Feedback Vertex Set (when \(\mathcal{F}\) is the set of all forests), and Odd Cycle Transversal (when \(\mathcal{F}\) is the set of all bipartite graphs). There are a lot more interesting graph classes \(\mathcal{F}\) studied in structural and algorithmic graph theory. Some famous examples include planar graphs, perfect graphs, chordal graphs, and graphs with bounded treewidth. In addition to beautiful structural results that give multiple equivalent characterizations, these graph classes often admit very efficient algorithms for some tasks that are believed to be hard in general graphs. Therefore, a systematic study of \(\mathcal{F}\textsc{-Deletion}\) for more graph classes is not only an interesting algorithmic task by itself, but also a way to obtain better algorithms for other optimization problems when the given graph \(G\) is close to a nice class \(\mathcal{F}\) (i.e., deleting few vertices from \(G\) makes it belong to \(\mathcal{F}\).) Indeed, some algorithms for Independent Set for noisy planar/minor-free graphs discussed in Section 4.1 use an algorithm for \(\mathcal{F}\textsc{-Deletion}\) as a subroutine [89]. For the maximization version where the goal is to maximize \(|V\setminus S|\), a powerful but pessimistic characterization is known. Lund and Yannakakis [244] showed that whenever \(\mathcal{F}\) is vertex-hereditary and nontrivial (i.e., there are infinitely many graphs in \(\mathcal{F}\) and out of \(\mathcal{F}\)), the maximization version is hard to approximate within a factor \(2^{\log^{1/2-\varepsilon}n}\) for any \(\varepsilon>0\). So no nontrivial \(\mathcal{F}\) is likely to admit even a polylogarithmic approximation algorithm. However, the situation is different for the minimization problem, since Vertex Cover admits a 2-approximation algorithm, while Odd Cycle Transversal[245] and Perfect Deletion[246] are NP-hard to approximate within any constant factor approximation algorithm. (The first result assumes the Unique Games Conjecture.) It indicates that a characterization of approximabilities for the minimization versions will be more complex and challenging. There are two (closely related) frameworks to capture large graph classes. * Choose a graph width parameter (e.g., treewidth, pathwidth, cliquewidth, rankwidth, etc.) and \(k\in\mathbb{N}\). Let \(\mathcal{F}\) be the set of graphs \(G\) with the chosen width parameter at most \(k\). The parameter of \(\mathcal{F}\textsc{-Deletion}\) is \(k\). * Choose a notion of subgraph (e.g., subgraph, induced subgraph, minor, etc.) and a finite family of forbidden graphs \(\mathcal{H}\). Let \(\mathcal{F}\) be the set of graphs \(G\) that do not have any graph in \(\mathcal{H}\) as the chosen notion of subgraph. The parameter of \(\mathcal{F}\textsc{-Deletion}\) is \(|\mathcal{H}|:=\sum_{H\in\mathcal{H}}|V(H)|\). Many interesting classes are capture by the above frameworks. For example, to express Feedback Vertex Set, we can take \(\mathcal{F}\) to be the set of graphs with treewidth at most 1, or equivalently, the set of graphs that does not have the triangle graph \(K_{3}\) as a minor.