most recent 30 from http://mathoverflow.net 2013-06-19T10:06:10Z http://mathoverflow.net/feeds/question/98651 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i Nick Russler 2012-06-02T12:31:13Z 2012-06-05T11:44:38Z

<p>Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}</p> <p>Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.</p> <p>Example:</p> <pre> 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)}}| </pre> <p>Now i am looking for a good/efficient Algorithm to solve that problem.</p>

http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663 Vidit Nanda 2012-06-02T15:28:48Z 2012-06-02T17:09:52Z

<p>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:</p> <p>$$ A = {(1,2),(3,4)}, B = {(1,3)}, C = {(13,14)}$$</p> <p>And there is an edge from $A$ to $B$ since $(1,2)$ overlaps $(1,3)$.</p> <p>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.</p> <p>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.</p> <p>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$.</p>

http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98686#98686 Watson Ladd 2012-06-02T22:12:22Z 2012-06-02T22:12:22Z

<p><a href="http://www.cccg.ca/proceedings/2005/50.pdf" rel="nofollow">This paper</a> claims to solve the problem.</p>

http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98863#98863 Nick Russler 2012-06-05T11:44:38Z 2012-06-05T11:44:38Z

<p>Vel Nias gave almost the right answer in:</p> <p><a href="http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663" rel="nofollow">http://mathoverflow.net/questions/98651/how-to-get-the-largest-subset-of-a-set-of-sets-of-intervals-with-no-overlapping-i/98663#98663</a></p> <p>but instead of the connected components we are looking for the maximum independent set in this graph.</p>