# Covering a set of intervals, continued

Peter Taylor and Tsuyoshi Ito solved a previous question that I posted:

Covering a set of intervals

I have a slight variation on that question that I'd also like to ask. I'm not sure what the etiquette here is here but I'll post the original question + modification here (if that's discouraged then I sincerely apologize!) The question posted was:

Is the following question in NP: "Given a finite set of half-open intervals and integers $k$ and $L$, is there a subset of the intervals so the sum of their characteristic functions can be expressed as a sum of characteristic functions of $k$ intervals of length $L$?"

The problem is NP-complete via a reduction from the subset-sum problem. My variation is:

Does the complexity change if we require that all of the given intervals have length less than $L$?

Thanks!

• I think it's perfectly fine (and recommended) to do as you did. I'd also recommend that you post a link here in the original question, so readers visiting that question will know that there's followup discussion here. Jan 27, 2011 at 5:17
• It it great that you posted this as a separate question because this was what I was thinking when I saw your previous question. Not that I know the answer to this version. :( Jan 27, 2011 at 11:19
• Slight correction... the previous version is NP-complete, not just in NP. This version is clearly in NP, too; the question is whether it's still NP-complete. Jan 27, 2011 at 18:49
• By reduction from SUBSET-SUM problem we only know that this problem is binary NP-complete. Isn't this question about strong NP-completeness of the problem? Jan 29, 2011 at 0:09
• @Oleksandr: That is a closely related question, but not necessarily exactly the same. Here each number (the coordinates of the endpoints of the given segments) can be large. If the problem is strongly NP-complete, then the problem in this question is also NP-complete. Jan 29, 2011 at 5:19