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$?


  • 4
    $\begingroup$ 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. $\endgroup$ Commented Jan 27, 2011 at 5:17
  • $\begingroup$ 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. :( $\endgroup$ Commented Jan 27, 2011 at 11:19
  • $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Commented Jan 27, 2011 at 18:49
  • $\begingroup$ 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? $\endgroup$ Commented Jan 29, 2011 at 0:09
  • $\begingroup$ @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. $\endgroup$ Commented Jan 29, 2011 at 5:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.