# Finding the minimum subset within a cycle

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?

• possible duplicate of Finding the minimum subset of intervals covering the whole set – Yuval Filmus Feb 9 '13 at 5:27
• 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
• 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

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