Fixed-parameter tractability and lower bounds for stabbing problems (Q359746)

The authors study the parametrized complexity of several instances of the general geometric stabbing (or hitting) problem: Given a set \(S\) of \(n\) translates of an object in \({\mathbb R}^d\) and a positive integer \(k\), select at most \(k\) lines such that every object is intersected by at least one of the selected lines. This is a typical algorithmical problem the parametrized complexity theory deals with (see [\textit{J. Flum} and \textit{M. Grohe}, Parametrized complexity theory. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer (2006; Zbl 1143.68016)]): when the input can be broken into two parts one having length \(k\) (the number of selected lines, the parameter) and the other having length \(n\) (the number of copies of the translated object), with the expectation that \(k<<n\). The class of problems solvable by algorithms running in time \(f(k)\cdot poly(n)\), where \(f\) is a computable function, is called the class of fixed-parameter tractable problems. The first level in the hierarchy of fixed-parameter intractability is denoted by \(W(1)\). Some results are proven in the negative sense: let \(O\) be a connected object in the plane, if the stabbing lines are to parallel to two different directions that are part of the input, the problem of stabbing a set of disjoint translates of \(O\) with \(k\) lines is \(W(1)\)-hard with respect to \(k\), in general. The same happens when the lines have arbitrary directions. Such results generalize those contained in the paper by \textit{M. Dom} et al. [Algorithmica 62, No. 1--2, 564--594 (2012; Zbl 1236.68083)]. In the positive sense two instances are shown to be fixed-parameter tractable: stabbing a set of \(n\) axis-parallel disjoint unit squares with \(k\) axis-parallel lines and, stabbing a set of \(n\) translates of a planar connected object with \(k\) lines with respect to \(k\), the number of lines' directions and the maximum number of objects that can be simultaneously intersected by two lines with different directions. Finally, the higher-dimensional problem of stabbing \(n\) unit balls in \({\mathbb R}^d\) with one line is shown to be \(W(1)\)-hard with respect to \(d\).