WorksComputer Science
Partial Interval Multicover Is NP-Complete Even for Unit Intervals
Abstract
For a interval family \calI, a point set , demands , and , partial interval multicover asks for a subfamily S\subseteq\calI minimizing subject to |\{x\in X:\dep_S(x)\ge d(x)\}|\ge p, \qquad \dep_S(x)=|\{I\in S:x\in I\}|. We prove that the unweighted decision problem is NP-complete even for unit intervals, answering the open question in~\cite{Li2026}.