# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Packing Problems
#### 4.1.1 Independent Set
It is also worth noting here that Independent Set problem can be generalized to the \(d\)-Scattered Set problem where we are given an (edge-weighted) graph and are asked to select at least \(k\) vertices, so that the distance between any pair is at least \(d\)(Kurz and Goyal, 2017). Recently in (Kurz and Goyal, 2017) some lower and upper bounds on the approximation of the \(d\)-Scattered Set problem have been provided. A special case of Independent Set is the Independent Set of Rectangles problem, where a set of axis-parallel rectangles is given in the two-dimensional plane, and the task is to find a maximum sized subset of non-intersecting rectangles. This is a special case, since pairwise intersections of rectangles can be encoded by edges in a graph for which the vertices are the rectangles. Parameterized by the solution size, the problem is W[1]-hard (Kurz and Goyal, 2017), and while a QPTAS is known (Kurz and Goyal, 2017), it is a challenging open question whether a PTAS exists. It was shown (Kurz and Goyal, 2017) however that both a PAS and a PSAKS exist for Independent Set of Rectangles parameterized by the solution size, even for the weighted version. The runtime of this PAS is \(f(k,\varepsilon)n^{\delta(\varepsilon)}\) for some functions \(f\) and \(g\), where \(k\) is the solution size. Note that the dependence on \(\varepsilon\) in the degree of the polynomial factor of this algorithm cannot be removed, unless FPT=W[1], since any efficient PAS with runtime \(f(k,\varepsilon)n^{O(1)}\) could be used to compute the optimum solution in FPT time by setting \(\varepsilon\) to \(\frac{1}{k+1}\) in the W[1]-hard unweighted version of the problem (Kurz and Goyal, 2017). However, in the so-called shrinking model an efficient PAS can be obtained (Kurz and Goyal, 2017) for Independent Set of Rectangles. The parameter in this case is a factor \(0<\delta<1\) by which every rectangle is shrunk before computing an approximate solution, which is compared to the optimum solution without shrinking. Theorem 11 (Kurz and Goyal, 2017; Kurz and Goyal, 2017): _For the Independent Set of Rectangles problem a \((1+\varepsilon)\)-approximation can be computed in \(k^{O(k/\varepsilon^{8})}n^{O(1/\varepsilon^{8})}\) time for any \(\varepsilon>0\), where \(k\) is the size of the optimum solution, or in \(f(\delta,\varepsilon)n^{O(1)}\) time for some computable function \(f\) and any \(\varepsilon>0\) and \(0<\delta<1\), where \(\delta\) is the shrinking factor. Moreover, a \((1+\varepsilon)\)-approximate kernel with \(k^{O(1/\varepsilon^{8})}\) rectangles can be computed in polynomial time._  
Another special case of Independent Set is the Independent Set on Unit Disk graph problem, where given set of \(n\) unit disks in the Euclidean plane, the task is to determine if there exists a set of \(k\) non-intersecting disks. The problem is NP-hard (Kurz and Goyal, 2017) but admits a PTAS (Kurz and Goyal, 2017). Marx (Kurz and Goyal, 2017) showed that, when parameterized by the solution size, the problem is W[1]-hard; this also rules out EPTAS (and even efficient PAS) for the problem, assuming FPT \(\
eq\) W[1]. On the other hand, in (Kurz and Goyal, 2017) the authors give an FPT algorithm for a special case of Independent Set on Unit Disk graph when there is a lower bound on the distance between any pair of centers.