Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $[c,d]$. Assume no two values are identical. For $(a,b)$, if $a > b$, the range is $[a,d] \cup [c,b]$; otherwise, it is $[a,b]$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

There exists an $O(n \log n)$ algorithm to find the smallest subset when, for any pair, $a$ is strictly less than $b$. I can run this algorithm for each pair to determine my solution. However, what is a more efficient algorithm to obtain the smallest subset?

share|improve this question
    
    
You should spend more effort on your own questions. Using the algorithms in the answers to your other question, it only remains to solve the case where $A$ covers the entire "circle". While I'm not sure how to do that, I'd appreciate if you gave it some thought first. –  Yuval Filmus Feb 9 '13 at 5:32
    
@Yuval, that's what makes the question more difficult. I have a solution, and I've spent considerable time thinking about it. Your comments are not constructive or helpful. –  idealistikz Feb 9 '13 at 5:38
    
At the very least, you can put a link to the $O(n\log n)$ algorithm. This could be helpful to people trying to solve the question. Another thing (which might be helpful) is that the algorithm on interval graphs mentioned in one of the answers also works for circular-arc graphs. However, it's not clear how to formulate the new problem as reachability. If you're happy to get the solution up to one interval, you can choose an arbitrary point and split all intervals at that point. –  Yuval Filmus Feb 9 '13 at 5:45
    
You could have edited the question and provided the link especially since you know this is not a duplicate question. –  idealistikz Feb 9 '13 at 6:16
add comment

1 Answer

up vote 2 down vote accepted

Using Kaveh's reduction in this related question, we only have to solve the case where the given intervals cover the entire circle $[c,d]$.

Here's an algorithm that almost calculates the optimum, in $O(n\log n)$. Replace each interval $[a,d] \cup [c,b]$ by the two intervals $[a,d],[c,b]$, and now solve the original problem. Let $O$ be the optimum of the original problem, and $S$ be the optimum of the new problem. I claim that $S-1 \leq O \leq S$.

First, given any solution to the new problem, we can find a solution to the old problem with the same cost, showing that $O \leq S$. For the other direction, take some optimal solution. If it doesn't use any split interval, then $S = O$. Otherwise, let $I_\min$ be the split interval minimizing $a$, and let $I_\max$ be the split interval maximizing $b$. If we drop all other split intervals, then whatever remains is still a cover of the circle. If $I_\min \neq I_\max$ then $S = O$, and otherwise all we know is that $S \leq O+1$.

It's plausible that this algorithm can be adapted somehow to actually find the optimum. (Most algorithms that work on interval graphs also work on circular-arc graphs.)

share|improve this answer
add comment

Your Answer

 
discard

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

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