Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

EDIT: I posted this question to http://cstheory.stackexchange.com/questions/4358/covering-a-set-of-intervals , which looks like a more appropriate venue for such a question.

Hello, I'm trying to determine if the following problem is in P or NP: given a collection of $n$ 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 (i.e., the symmetric difference is a finite set of points) with $k$ closed intervals of length $L$, with each of these $k$ "covering intervals" only covering one of the given intervals at a time?

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!

share|improve this question
    
I don't understand the condition "covering one of the given intervals at a time"; the interpretation that comes to mind seems to be violated by your example, as $[0,4]$ covers both $(0,3)$ and $(2, 4)$. In any case, this sort of problem is generally in NP, as a cover suffices as a certificate. –  Daniel Litt Jan 17 '11 at 7:38
    
You may have more luck on cstheory.stackexchange.com –  Anthony Labarre Jan 17 '11 at 7:54
    
Thanks, I didn't know about that site! –  Jennifer Gao Jan 17 '11 at 8:02
3  
@Jennifer, Could you restate the problem in precise mathematical language, avoiding words like "cover", saying what the two sets are of which you take the symmetric difference, etc.? @Gerry, obviously Jennifer was speaking slightly loosely and strictly speaking meant "NP-complete". –  gowers Jan 17 '11 at 10:19
1  
@Jennifer Gao: Are you asking that the total multiplicty of the covering intervals equals the total multiplicity of the given intervals at all but finitely many points (which are various endpoints)? I.e., given a finite set of intervals, is there a subset of them so the sum of their characteristic functions can be expressed as a sum of characteristic functionof intervals of length L? –  Bill Thurston Jan 17 '11 at 10:27
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.