5
$\begingroup$

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

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

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Jennifer Gao
    Jan 17, 2011 at 19:15
  • 2
    $\begingroup$ @Jennifer, to clarify, are you interested in the case where both $k$ and $L$ are bounded by polynomials (or maybe just one of them)? $\endgroup$
    – Peter Shor
    Jan 17, 2011 at 19:35
  • $\begingroup$ @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? $\endgroup$
    – Jennifer Gao
    Jan 17, 2011 at 20:09
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Jan 17, 2011 at 23:34
  • 3
    $\begingroup$ 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.” $\endgroup$
    – Tsuyoshi Ito
    Jan 18, 2011 at 0:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.