摘要：A 2-interval is the union of two disjoint intervals on the real line. Two 2-intervals Dâ, and Dâ,, are disjoint if their intersection is empty (i.e., no interval of Dâ, intersects any interval of Dâ,,). There can be three different relations between two disjoint 2-intervals; namely, preceding (<), nested (âS) and crossing (â¬). Two 2-intervals Dâ, and Dâ,, are called R-comparable for some Râ^^{<,âS,â¬}, if either Dâ,RDâ,, or Dâ,,RDâ,. A set ð'Y of disjoint 2-intervals is â">-comparable, for some â">âS{<,âS,â¬} and â">â â^., if every pair of 2-intervals in â"> are R-comparable for some Râ^^â">. Given a set of 2-intervals and some â">âS{<,âS,â¬}, the objective of the {2-interval pattern problem} is to find a largest subset of 2-intervals that is â">-comparable. The 2-interval pattern problem is known to be W[1]-hard when â"> =3 and NP-hard when â"> =2 (except for â">={<,âS}, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing that it is W[1]-hard for both â">={âS,â¬} and â">={<,â¬} (when parameterized by the size of an optimal solution). This answers the open question posed by Vialette [Encyclopedia of Algorithms, 2008].
