[Back]

D. Bergren, E. Eiben, R. Ganian, I. Kanj:
"On Covering Segments with Unit Intervals";
Talk: Symposium on Theoretical Aspects of Computer Science (STACS), Montpellier, Frankreich; 2020-03-10 - 2020-03-13; in: "37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)", LIPICS, 154 (2020), ISBN: 978-3-95977-140-5; Paper ID 13, 17 pages.

We study the problem of covering a set of segments on a line with the minimum number of unit-lengthintervals, where an interval covers a segment if at least one of the two endpoints of the segment fallsin the unit interval. We also study several variants of this problem.We show that the restrictions of the aforementioned problems to the set of instances in which allthe segments have the same length areNP-hard. This result implies severalNP-hardness results inthe literature for variants and generalizations of the problems under consideration.We then study the parameterized complexity of the aforementioned problems. We provide tightresults for most of them by showing that they are fixed-parameter tractable for the restrictions inwhich all the segments have the same length, and areW[1]-complete otherwise.

http://dx.doi.org/10.4230/LIPIcs.STACS.2020.13

https://publik.tuwien.ac.at/files/publik_293770.pdf