<p>Peter Taylor and Tsuyoshi Ito solved a previous question that I posted:</p>

<p><a href="https://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals">Covering a set of intervals</a></p>

<p>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:</p>

<p>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$?"</p>

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

<blockquote>
  <p>Does the complexity change if we
  require that all of the given
  intervals have length less than $L$?</p>
</blockquote>

<p>Thanks!</p>

CC BY-SA 2.5
2011-01-27T05:17:41.960Z
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.
Suresh Venkat
CC BY-SA 2.5
2011-01-27T11:19:01.867Z
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. :(
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-27T18:49:47.013Z
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.
mjqxxxx
CC BY-SA 2.5
2011-01-29T00:09:43.590Z
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?
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-29T05:19:23.777Z
@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.
Tsuyoshi Ito
<cc.complexity-theory><cg.comp-geom><scheduling>
Covering a set of intervals, continued
Jennifer Gao
# Covering a set of intervals, continued

(Asked by: username_0 on 2011-01-27)

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

[Covering a set of intervals](https://cstheory.stackexchange.com/questions/4358/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!

**Tags:** cc.complexity-theory, cg.comp-geom, scheduling
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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. :(  
> **username_3**: 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.  
> **username_4**: 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?  
> **username_2**: @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.  

---

## 0 answers

