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

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.

Example:

Input {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}

A possible Solution would be: {{(1,2), (3,4)}, {(13,14)}}

Another could be {{(1, 3)}, {(13,14)}},
it's not important that the solution above has more 'subelements',
its only important that 2 = |{{(1,2), (3,4)}, {(13,14)}}| = |{{(1, 3)}, {(13,14)}}|

Now i am looking for a good/efficient Algorithm to solve that problem.

share|improve this question

3 Answers 3

Call the set containing the sets of intervals $S$ and build a graph $G_S$ from $S$ as follows: Each set of intervals $I \in S$ becomes a vertex, and there is an edge between interval set $I$ and interval set $J$ if and only if some interval in $I$ overlaps with some interval in $J$. So for your example, the graph would have three vertices:

$$ A = \{(1,2),(3,4)\}, B = \{(1,3)\}, C = \{(13,14)\}$$

And there is an edge from $A$ to $B$ since $(1,2)$ overlaps $(1,3)$.

Now, the number of connected components of $G_S$ gives you the "number of non-pairwise overlapping interval sets" and picking a vertex from each connected component furnishes a solution to your problem.

So back to your example: the connected components are $AB$ and $C$, so you can pick either $A$ and $C$ or $B$ and $C$, as you have said.

Regarding efficiency: the worst-case complexity of building this graph is $O(m^2n^2)$ where $m$ is the cardinality of $S$ and $n$ is the maximal cardinality of any interval set $I \in S$.

share|improve this answer
    
What if a connected component forms a long path? For instance ${{(1,4)},{(3,6)},{(5,8)},{(7,10)},{(9,12)}}$. Then ${{(1,4)},{(5,8)}.{(9,12)}}$ has no overlaps, but has multiple vertices from a single connected component., –  Will Sawin Jun 2 '12 at 20:22
    
Yeah, now i think hes right... We are looking for the maximum independent set... and that takes too much time. –  Nick Russler Jun 5 '12 at 0:32
up vote 1 down vote accepted

Vel Nias gave almost the right answer in:

How to get the largest subset of a set of sets of intervals with no overlapping intervals

but instead of the connected components we are looking for the maximum independent set in this graph.

share|improve this answer

This paper claims to solve the problem.

share|improve this answer
    
Maybe i dont understand the paper right, but as far as i can tell this paper only deals with a Set of Intervall's not a Set of Set's of Intervalls. –  Nick Russler Jun 5 '12 at 10:22
    
D'oh! I got confused when reading the example. –  Watson Ladd Jun 6 '12 at 16:09

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.