# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Packing Problems
#### 4.1.1 Independent Set  
The Independent Set problem is notoriously hard in general. Not only is there no polynomial time \(n^{1-\epsilon}\)-approximation algorithm [81] for any constant \(\epsilon>0\), unless P = NP, but also, under Gap-ETH, no \(g(k)\)-approximation can be computed in \(f(k)n^{O(1)}\) time [39] for any computable functions \(f\) and \(g\), where \(k\) is the solution size. On the other hand, for planar graphs a PTAS exists [82]. Hence a natural question is how the problem behaves for graphs that are \"close\" to being planar. One way to generalize planar graphs is to consider minor-free graphs, because planar graphs are exactly those excluding \(K_{5}\) and \(K_{3,3}\) as minors. When parameterizing by the size of an excluded minor, the Independent Set problem is paraNP-hard, since the problem is NP-hard on planar graphs [83]. Nevertheless a PAS can be obtained for this parameter [84]. **Theorem 9** ([84; 85]). : _Let \(H\) be a fixed graph. For \(H\)-minor-free graphs, Independent Set admits an \((1+\epsilon)\)-approximation algorithm that runs in \(f(H,\epsilon)n^{O(1)}\) time for some function \(f\)._  
This result is part of the large framework of \"bidimensionality theory\" where any graph in an appropriate minor-closed class has treewidth bounded above in terms of the problem's solution value, typically by the square root of that value. These properties lead to efficient, often subexponential, fixed-parameter algorithms, as well as polynomial-time approximation schemes, for bidimensional problems in many minor-closed graph classes. The bidimensionality theory is based on algorithmic and combinatorial extensions to parts of the Robertson-Seymour Graph Minor Theory, in particular initiating a parallel theory of graph contractions. The foundation of this work is the topological theory of drawings of graphs on surfaces. We refer the reader to the survey of [86] and more recent papers [85; 87; 88]. A different way to generalize planar graphs is to consider a planar deletion set, i.e., a set of vertices in the input graph whose removal leaves a planar graph. Taking the size of such a set as a parameter, Independent Set is again paraNP-hard [83]. However, by first finding a minimum sized planar deletion set, then guessing the intersection of this set with the optimum solution to Independent Set, and finally using the PTAS for planar graphs [82], a PAS can be obtained parameterized by the size of a planar deletion set [8]. **Theorem 10** ([8]). : _For the Independent Set problem a \((1+\epsilon)\)-approximation can be computed in \(2^{k}n^{O(1/\epsilon)}\) time for any \(\epsilon>0\), where \(k\) is the size of a minimum planar deletion set._Ideas using linear programming allow us to generalize and handle larger noise at the expense of worse dependence on \(\varepsilon\). Bansal et al. (1998) showed that given a graph obtained by adding \(\delta n\) edges to some planar graph, one can compute a \((1+O(\varepsilon+\delta))\)-approximate independent set in time \(n^{O(1/\varepsilon^{4})}\), which is faster than the \(2^{k}n^{O(1/\varepsilon)}\) running time of Theorem 10 for large \(k=\delta n\). Magen and Moharrami (2017) showed that for every graph \(H\) and \(\varepsilon>0\), given a graph \(G=(V,E)\) that can be made \(H\)-minor-free after at most \(\delta n\) deletions and additions of vertices or edges, the size of the maximum independent set can be approximately computed within a factor \((1+\varepsilon+O(\delta|H|\sqrt{\log|H|}))\) in time \(n^{f(\varepsilon,H)}\). Note that this algorithm does not find an independent set. Recently, Demaine et al. (2018) presented a general framework to obtain better approximation algorithms for various problems including Independent Set and Chromatic Number, when the input graph is close to well-structured graphs (e.g., bounded degeneracy, degree, or treewidth).