<p>You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S&#39;$ of $S$ such that $\Sigma_{s&#39; \in S&#39;} s&#39; = t$. But this can be reduced to your interval cover problem with intervals $\{(0, s) : s \in S\}$, $k = t$, $L = 1$. Therefore the interval cover problem is NP-hard.</p>

<p>PS Why don't you make all the intervals, input and output, half-open at the same end? That way you eliminate the finite set of points at which the sum of indicator functions is different.</p>

CC BY-SA 2.5
2011-01-17T19:15:59.957Z
I thought about that, but I think there's a problem in that subset-sum can be solved in pseudo-polynomial time via dynamic programming.  So, this particular problem can be solved polynomially in $k=t$, whereas we don't know if that's always the case.
Jennifer Gao
CC BY-SA 2.5
2011-01-17T19:35:57.040Z
@Jennifer, to clarify, are you interested in the case where both $k$ and $L$ are bounded by polynomials (or maybe just one of them)?
Peter Shor 
CC BY-SA 2.5
2011-01-17T20:09:47.807Z
@Peter Shor, I want to know if it's possible to solve my problem polynomially in $n$, the number of input intervals, and $k$.  Does that make sense?
Jennifer Gao
CC BY-SA 2.5
2011-01-17T23:34:26.653Z
@Jennifer: When we say a positive integer is given as input, it means by default that it is given in binary.  Therefore, this reduction from the subset sum problem really answers what you asked.  If it does not answer what you wanted to know, it is because you did not ask the correct question.  It is better to accept the answer and ask a separate question than arguing how this does not address what you wanted to know.  When you ask a new question, please link to this one and clarify the difference from this.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-18T00:27:22.653Z
@Tsuyoshi Ito, @Peter Taylor: Sorry, I'm just having a hard time understanding the proof. It seems to me that the proof sketch is as follows: suppose (for a contradiction) my problem can be solved polynomially in $n$,$k$,and$L$. Then as Peter writes, we can formulate an instance of subset-sum as an instance of my problem, and (by initial assumption) we can solve it polynomially in $n$ and $k=t$. However, isn't that a true statement, not a contradiction, since subset-sum can be solved in $O(nt)$ running time with Dynamic Programming?  Thanks for your help so far, I apologize if I'm not clear!
Jennifer Gao
CC BY-SA 2.5
2011-01-18T00:36:52.417Z
Peter Talyer’s claim is that (unless P=NP) the problem cannot be solved in time polynomial in the input size.  Note that k and L can be exponentially large in the input size, and therefore “polynomial in the input size” is not the same as “polynomial in n, k and L.”
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-18T03:55:28.043Z
if this works, then you should probably accept this answer by clicking the check mark below the number of votes it has received
Suresh Venkat
CC BY-SA 2.5
2011-01-17T19:03:46.737Z
2011-01-17T19:03:46.737Z
Peter Taylor
<p>(I was redirected from mathoverflow in asking this)</p>

<p>Hello,
I'm trying to determine if the following problem is solvable in polynomial time:  given a collection of $n$ half-open intervals $[s_i, t_i)$ having integer endpoints, is it possible, for given integers $k$ and $L$, to find a subset $S$ of these intervals that are "exactly" covered with $k$ half-open intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at any particular instant?  Put another way, by William Thurston, "given a finite set of half-open intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functions of intervals of length $L$"?</p>

<p>For example, given the four intervals $[0,3), [2,4), [3, 6), [3, 8)$ with $k=2$ and $L=4$, we find that $[0,3)$, $[2,4)$, and $[3,6)$ can be exactly covered by the two intervals $[0,4)$ and $[2,6)$.  I hope I've stated this clearly.  One thing I've tried is a reduction via the subset-sum problem, but the fact that I'm dealing with intervals complicates it in a way I'm not comfortable with.  Thanks!</p>

<p>A clarification about "only covering one of the given intervals at any particular instant":  what I mean is that, for example, the interval $[0,5]$ could be said to cover either $(0,3)$ or $(0,4)$, but not both simultaneously.  </p>

CC BY-SA 2.5
2011-01-17T08:53:45.223Z
In your example, isn't $[0, 4]$ covering both $(0, 3)$ and $(2, 4)$ simultaneously?
Peter Taylor
CC BY-SA 2.5
2011-01-17T09:29:57.200Z
@Jennifer Gao: Please, indicate in your question that it was asked on mathoverflow too.
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-17T10:11:47.397Z
@Peter, it's possible the idea is that at any given point on the line, there are at most $k$ input intervals. In this case, between 0 and 2 there's one input interval and one answer interval. Between 2 and 4 there are two inputs and two outputs. Between 4 and 6 there is again one input and one output.
Suresh Venkat
CC BY-SA 2.5
2011-01-17T10:12:19.380Z
@Oleksandr, can you add a link in for the MO post ?
Suresh Venkat
CC BY-SA 2.5
2011-01-17T11:43:06.167Z
@Suresh Venkat: Here it is:http://mathoverflow.net/questions/52298/covering-a-set-of-intervals
Oleksandr Bondarenko
CC BY-SA 2.5
2011-01-17T18:53:57.310Z
@Jennifer, you should update your question with this note, rather than leaving it in comments. that would be very helpful
Suresh Venkat
CC BY-SA 2.5
2011-01-17T19:18:04.107Z
@Suresh Done.  Thanks for clarifying in your earlier comment as well.
Jennifer Gao
<cc.complexity-theory><cg.comp-geom><scheduling>
Covering a set of intervals
Jennifer Gao
# Covering a set of intervals

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

(I was redirected from mathoverflow in asking this)

Hello,
I'm trying to determine if the following problem is solvable in polynomial time: given a collection of $n$ half-open intervals $[s\_i, t\_i)$ having integer endpoints, is it possible, for given integers $k$ and $L$, to find a subset $S$ of these intervals that are "exactly" covered with $k$ half-open intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at any particular instant? Put another way, by William Thurston, "given a finite set of half-open intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functions of intervals of length $L$"?

For example, given the four intervals $[0,3), [2,4), [3, 6), [3, 8)$ with $k=2$ and $L=4$, we find that $[0,3)$, $[2,4)$, and $[3,6)$ can be exactly covered by the two intervals $[0,4)$ and $[2,6)$. I hope I've stated this clearly. One thing I've tried is a reduction via the subset-sum problem, but the fact that I'm dealing with intervals complicates it in a way I'm not comfortable with. Thanks!

A clarification about "only covering one of the given intervals at any particular instant": what I mean is that, for example, the interval $[0,5]$ could be said to cover either $(0,3)$ or $(0,4)$, but not both simultaneously.

**Tags:** cc.complexity-theory, cg.comp-geom, scheduling

> **Comments:**
> **username_1**: In your example, isn't $[0, 4]$ covering both $(0, 3)$ and $(2, 4)$ simultaneously?  
> **username_2**: @username_0: Please, indicate in your question that it was asked on mathoverflow too.  
> **username_3**: @Peter, it's possible the idea is that at any given point on the line, there are at most $k$ input intervals. In this case, between 0 and 2 there's one input interval and one answer interval. Between 2 and 4 there are two inputs and two outputs. Between 4 and 6 there is again one input and one output.  
> **username_3**: @Oleksandr, can you add a link in for the MO post ?  
> **username_2**: @username_3: Here it is:http://mathoverflow.net/questions/52298/covering-a-set-of-intervals  
> **username_3**: @Jennifer, you should update your question with this note, rather than leaving it in comments. that would be very helpful  
> **username_0**: @Suresh Done.  Thanks for clarifying in your earlier comment as well.  

---

## 1 answers

### Answer by username_1 on 2011-01-17. Score: 6 | Accepted answer

You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S'$ of $S$ such that $\Sigma\_{s' \in S'} s' = t$. But this can be reduced to your interval cover problem with intervals $\{(0, s) : s \in S\}$, $k = t$, $L = 1$. Therefore the interval cover problem is NP-hard.

PS Why don't you make all the intervals, input and output, half-open at the same end? That way you eliminate the finite set of points at which the sum of indicator functions is different.

> **Comments:**
> **username_0**: I thought about that, but I think there's a problem in that subset-sum can be solved in pseudo-polynomial time via dynamic programming.  So, this particular problem can be solved polynomially in $k=t$, whereas we don't know if that's always the case.  
> **username_4**: @Jennifer, to clarify, are you interested in the case where both $k$ and $L$ are bounded by polynomials (or maybe just one of them)?  
> **username_0**: @Peter Shor, I want to know if it's possible to solve my problem polynomially in $n$, the number of input intervals, and $k$.  Does that make sense?  
> **username_5**: @Jennifer: When we say a positive integer is given as input, it means by default that it is given in binary.  Therefore, this reduction from the subset sum problem really answers what you asked.  If it does not answer what you wanted to know, it is because you did not ask the correct question.  It is better to accept the answer and ask a separate question than arguing how this does not address what you wanted to know.  When you ask a new question, please link to this one and clarify the difference from this.  
> **username_0**: @username_5, @username_1: Sorry, I'm just having a hard time understanding the proof. It seems to me that the proof sketch is as follows: suppose (for a contradiction) my problem can be solved polynomially in $n$,$k$,and$L$. Then as Peter writes, we can formulate an instance of subset-sum as an instance of my problem, and (by initial assumption) we can solve it polynomially in $n$ and $k=t$. However, isn't that a true statement, not a contradiction, since subset-sum can be solved in $O(nt)$ running time with Dynamic Programming?  Thanks for your help so far, I apologize if I'm not clear!  
> **username_5**: Peter Talyer’s claim is that (unless P=NP) the problem cannot be solved in time polynomial in the input size.  Note that k and L can be exponentially large in the input size, and therefore “polynomial in the input size” is not the same as “polynomial in n, k and L.”  
> **username_3**: if this works, then you should probably accept this answer by clicking the check mark below the number of votes it has received  

---

