# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### \(\mathcal{F}\)-Deletion Problems
#### 4.6.1 Treewidth and Planar Minor Deletion
Does Treewidth \(k\)-Deletion admit a \(c\)-approximation algorithm with parameter \(k\) for some universal constant \(c\)?_Algorithms for Treewidth \(k\)-Deletion.Here we present high-level ideals of [255; 260] for Treewidth \(k\)-Deletion and Weighted Treewidth \(k\)-Deletion respectively. These two algorithms share the following two important ingredients:  
1. Graphs with bounded treewidth admit good separators. 2. There are good approximation algorithms to find such separators. Given an undirected and vertex-weighted graph \(G=(V,E)\) and an integer \(k\in\mathbb{N}\), let (Weighted) \(k\)-Vertex Separator be the problem whose goal is to remove the vertices of minimum total weight so that each connected component has at most \(k\) vertices. An algorithm is called an \(\alpha\)-bicriteria approximation algorithm if it returns a solution whose total weight is at most \(\alpha\cdot\textsc{Opt}\) and each connected component has at most \(1.1k\) vertices [262]. The case \(k=2n/3\) is called Balanced Separator and has been actively studied in the approximation algorithms community, and the best approximation algorithm achieves \(O(\sqrt{\log n})\)-bicriteria approximation [234]. When \(k\) is small, \(O(\log k)\)-bicriteria approximation is also possible [116]. Weighted Treewidth \(k\)-Deletion.Agrawal et al. [260] achieves an \(O(\log^{1.5}n)\)-approximation for Weighted Treewidth \(k\)-Deletion in time \(n^{O(k)}\). It would be interesting to see whether the running time can be made FPT with parameter \(k\). The main structure of their algorithm is top-down recursive. Deleting the optimal solution \(S^{*}\) from \(G\) reduces the treewidth of \(G\setminus S^{*}\) to \(k\), so from the forest decomposition of \(G\setminus S^{*}\), there exists a set \(M^{*}\subseteq G\setminus S^{*}\) with at most \(k+1\) vertices such that each connected component of \(G\setminus(M^{*}\cup S^{*})\) has at most \(2n/3\) vertices. While we do not know \(S^{*}\), we can exhaustively try every possible \(M\subseteq V\) with \(|M|\leq k+1\) and use the bicriteria approximation algorithm for Balanced Separator to find \(M\) and \(S\) such that (1) \(|M|\leq k+1\), (2) \(w(S)\leq O(\sqrt{\log n})\textsc{Opt}\), and (3) \(G\setminus(M\setminus S)\) has at most \(1.1\cdot(2n/3)\leq 3n/4\) vertices. Let \(G_{1},\ldots,G_{t}\) be the resulting connected components of \(G\setminus(S\cap M)\). We solve each \(G_{i}\) recursively to compute \(S_{i}\) such that each \(G_{i}\setminus S_{i}\) has treewidth at most \(k\). The weight of \(S\) was already bounded in terms of \(\textsc{Opt}\), but the weight of \(M\) was not, so we finally need to consider the graph induced by \(M\cup V(G_{1})\cup\cdots\cup V(G_{t})\) and delete vertices of small weight to ensure small treewidth. However, this task is easy since since the treewidth of each \(G_{i}\) is bounded by \(k\) and \(|M|\leq k+1\), which bounds the treewidth of the considered graph by \(2k+1\). So we can fetch the algorithm for small treewidth graphs to solve the problem optimally. Note that the total weight of removed vertices in this recursive call is at most \((O(\sqrt{\log n})+1)\textsc{Opt}\). Since \(\sum_{i}\textsc{Opt}(G_{i})\leq\textsc{Opt}(G)\) and the recursion depth is at most \(O(\log n)\), the total approximation ratio is \(O(\log^{1.5}n)\). Treewidth \(k\)-Deletion.Gupta et al. [255] give an \(O(\log k)\)-approximation algorithm that runs in time \(f(k)\cdot n^{O(1)}\) for the unweighted version of Treewidth \(k\)-Deletion. The main structure of this algorithm is bottom-up iterative refinement. The algorithm maintains a feasible solution \(S\subseteq V\) (we can start with \(S=V\)), and iteratively uses \(S\) to obtain another feasible solution \(S^{\prime}\). If the new solution is not smaller (i.e., \(|S^{\prime}|\geq|S|\)), then \(|S|\leq O(\log k)\cdot\textsc{Opt}\). Let us focus on one refinement step with the current feasible solution \(S\). Let \(S^{*}\) be the optimal solution, so that \(G\setminus S^{*}\) has treewidth at most \(k\).