# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### \(\mathcal{F}\)-Deletion Problems
#### 4.6.1 Treewidth and Planar Minor Deletion  
The treewidth of a graph (see Definition 1) is arguably the most well-studied graph width parameter with numerous structural and algorithmic applications. It is one of the most important concepts in the graph minor project of Robertson and Seymour. Algorithmically, Courcelle's theorem [250] states that every problem expressible in the monadic second-order logic of graphs can be solved in FPT time parameterized by treewidth. We refer the reader to the survey of Bodlaender [251]. Computing treewidth is NP-hard in general [252], but if we parameterize by treewidth, it can be done in FPT time [253], and there is a faster constant-factor parameterized approximation algorithm [254]. Let \(k\in\mathbb{N}\) be the parameter. Treewidth \(k\)-Deletion (also known as Treewidth \(k\)-Modulator in the literature) is a special case of \(\mathcal{F}\)-Deletion where \(\mathcal{F}\) is the set of all graphs with treewidth at most \(k\). Note the case \(k=0\) yields Vertex Cover and \(k=1\) yields Feedback Vertex Set. Fomin et al. [247] gave a randomized \(f(k)\)-approximation algorithm that runs in \(g(k)\cdot nm\) for some computable functions \(f\) and \(g\). The approximation ratio was improved by Gupta et al. [255] that gave a deterministic \(O(\log k)\)-approximation algorithm that runs in \(f(k)\cdot n^{O(1)}\) some \(f\). This result has immediate applications to minor deletion problems. Let \(\mathcal{H}\) be a finite set of graphs, and consider \(\mathcal{H}\)-Minor Deletion, which is a special case of \(\mathcal{F}\)-Deletion when \(\mathcal{F}\) is the set of all graphs that do not have any graph in \(\mathcal{H}\) as a minor. Its parameterized and kernelization complexity (with parameter Opt) for family \(\mathcal{H}\) has been actively studied [247; 256; 257]. When \(\mathcal{H}\) contains a planar graph \(H\) (also known as Planar \(\mathcal{H}\)-Deletion in the literature), by the polynomial grid-minor theorem [258], any graph \(G\in\mathcal{F}\) has treewidth at most \(k:=\text{poly}(|V(H)|)\). Therefore, in order to solve \(\mathcal{H}\)-Minor Deletion, one can first solve Treewidth \(k\)-Deletion to reduce the treewidth to \(k\) and then solve \(\mathcal{H}\)-Minor Deletion optimally using Courcelle's theorem [250]. Combined with the above algorithm for Treewidth \(k\)-Deletion[255], this strategy yields an \(O(\log k)\)-approximation algorithm that runs in \(f(|\mathcal{H}|)\cdot n^{O(1)}\) time. Beyond Planar \(\mathcal{H}\)-Deletion, there are not many results known for \(\mathcal{H}\)-Minor Deletion. The case \(\mathcal{H}=\{K_{5},K_{3,3}\}\) is called Minimum Planarization and was recently shown to admit an \(O(\log^{O(1)}n)\)-approximation algorithm in \(n^{O(\log n/\log\log n)}\) time [259]. While the unweighted versions of Treewidth \(k\)-Deletion and Planar \(\mathcal{H}\)-Deletion admit an approximation algorithm whose approximation ratio only depends on \(k\) not \(n\), such an algorithm is not known for Weighted Treewidth \(k\)-Deletion or Weighted Planar \(\mathcal{H}\)-Deletion. Agrawal et al. [260] gave a randomized \(O(\log^{1.5}n)\)-approximation algorithm and a deterministic \(O(\log^{2}n)\)-approximation algorithm that run in polynomial time for fixed \(k\), i.e., the degree of the polynomial depends on \(k\). Bansal et al. [89] gave an \(O(\log n\log\log n)\)-approximation algorithm for the edge deletion version. The only graphs \(H\) whose weighted minor deletion problem is known to admit a constant factor approximation algorithm are single edge (Weighted Vertex Cover), triangle (Weighted Feedback Vertex Set), and diamond [261]. For the weighted versions, no hardness beyond Vertex Cover is known. **Open Question 15**. : _Does Weighted Treewidth \(k\)-Deletion admit an \(f(k)\)-approximation algorithm with parameter \(k\) for some function \(f\)?