2026-07-25T14:47:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11874 2024-03-06T10:48:54Z ddc:004 open_access

On Covering Segments with Unit Intervals Bergren, Dan Eiben, Eduard Ganian, Robert Kanj, Iyad Segment covering unit intervals NP-completeness parameterized complexity We study the problem of covering a set of segments on a line with the minimum number of unit-length intervals, where an interval covers a segment if at least one of the two endpoints of the segment falls in 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 all the segments have the same length are NP-hard. This result implies several NP-hardness results in the literature for variants and generalizations of the problems under consideration. We then study the parameterized complexity of the aforementioned problems. We provide tight results for most of them by showing that they are fixed-parameter tractable for the restrictions in which all the segments have the same length, and are W[1]-complete otherwise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dan Bergren and Eduard Eiben and Robert Ganian and Iyad Kanj 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.13 urn:nbn:de:0030-drops-118741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode