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

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.

-

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

-
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

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.

-

This paper claims to solve the problem.

-
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