# Covering a set of intervals

(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.

• In your example, isn't $[0, 4]$ covering both $(0, 3)$ and $(2, 4)$ simultaneously? Commented Jan 17, 2011 at 8:53
• @Jennifer Gao: Please, indicate in your question that it was asked on mathoverflow too. Commented Jan 17, 2011 at 9:29
• @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. Commented Jan 17, 2011 at 10:11
• @Suresh Venkat: Here it is:mathoverflow.net/questions/52298/covering-a-set-of-intervals Commented Jan 17, 2011 at 11:43
• @Jennifer, you should update your question with this note, rather than leaving it in comments. that would be very helpful Commented Jan 17, 2011 at 18:53

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.
• 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. Commented Jan 17, 2011 at 19:15
• @Jennifer, to clarify, are you interested in the case where both $k$ and $L$ are bounded by polynomials (or maybe just one of them)? Commented Jan 17, 2011 at 19:35
• @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? Commented Jan 17, 2011 at 20:09