1
$\begingroup$

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.

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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., $\endgroup$
    – Will Sawin
    Jun 2, 2012 at 20:22
  • $\begingroup$ Yeah, now i think hes right... We are looking for the maximum independent set... and that takes too much time. $\endgroup$ Jun 5, 2012 at 0:32
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

This paper claims to solve the problem.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 5, 2012 at 10:22
  • $\begingroup$ D'oh! I got confused when reading the example. $\endgroup$ Jun 6, 2012 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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