2-interval Problems

CREATED: 200802140146 ** 2-intervals A pair of intervals

• relations between 2 2-intervals

Crossing

Nested

Before/After

Overlap (the intervals overlap)

** Max independent set (MaxSet)

• given a set of 2-intervals, find a max set of intervals where the relation between any pair of 2-intervals is {BA,C,N}
• NP-hard (reduction from 3SAT)
• Applications: RNA folding
• In P if restricted to integral coordinates such as in the RNA application, where the coordinate is the position of the RNA molecule.

** Matching (Match)

• given a database of 2-intervals and a set of 2-intervals which is the query pattern, find all subsets of the database which is isomorphic to the pattern (exhibits the same relations)

** Results

• each problem MaxSet and Match can be parameterized by the set of relations allowed
• MaxSet{BA} can be solved in O(n)
• MaxSet{N} can be solved in O(n lg n) by mapping each interval to a tuple (x,y) and finding the longest decreasing subsequence as x increases
• Conjecture: MaxSet{BA, C} cannot be solved by LIS, MaxSet{BA, C} is NP-Hard