Parameterized Approximation of Rectangle Stabbing

Abstract

In the Rectangle Stabbing problem, input is a set $\mathcal{R}$ of axis-parallel rectangles and a set $\mathcal{L}$ of axis parallel lines in the plane. The task is to find a minimum size set ${\mathcal{L}}^{\ast }\subseteq \mathcal{L}$ such that for every rectangle $R\in \mathcal{R}$ there is a line $\ell \in {\mathcal{L}}^{\ast }$ such that $\ell$ intersects $R$. Gaur et al. [Journal of Algorithms, 2002] gave a polynomial time $2$-approximation algorithm, while Dom et al. [WALCOM 2009] and Giannopolous et al. [EuroCG 2009] independently showed that, assuming FPT $\ne$ W[1], there is no algorithm with running time $f(k)(|\mathcal{L}||\mathcal{R}|{)}^{O(1)}$ that determines whether there exists an optimal solution with at most $k$ lines. We give the first parameterized approximation algorithm for the problem with a ratio better than $2$. In particular we give an algorithm that given $\mathcal{R}$, $\mathcal{L}$, and an integer $k$ runs in time $k^{O(k)}(|\mathcal{L}||\mathcal{R}|{)}^{O(1)}$ and either correctly concludes that there does not exist a solution with at most $k$ lines, or produces a solution with at most $\frac{7k}{4}$ lines. We complement our algorithm by showing that unless FPT $=$ W[1], the Rectangle Stabbing problem does not admit a $(\frac{5}{4}-\hat{I}\mu )$-approximation algorithm running in $f(k)(|\mathcal{L}||\mathcal{R}|{)}^{O(1)}$ time for any function $f$ and $\hat{I}\mu >0$.