Melvin's digital garden

2-interval Problems

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

  • relations between 2 2-intervals




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

Links to this note