A emph{2-interval} is the union of two disjoint intervals on the real line. Two 2-intervals $D_1$ and $D_2$ are emph{disjoint} if their intersection is empty (i.e., no interval of $D_1$ intersects any interval of $D_2$). There can be three different relations between two disjoint 2-intervals; namely, preceding ($<$), nested ($sqsubset$) and crossing ($between$). Two 2-intervals $D_1$ and $D_2$ are called emph{$R$-comparable} for some $Rin{<,sqsubset,between}$, if either $D_1RD_2$ or $D_2RD_1$. A set $mathcal{D}$ of disjoint 2-intervals is $mathcal{R}$-comparable, for some $mathcal{R}subseteq{<,sqsubset,between}$ and $mathcal{R} eqemptyset$, if every pair of 2-intervals in $mathcal{R}$ are $R$-comparable for some $Rinmathcal{R}$. Given a set of 2-intervals and some $mathcal{R}subseteq{<,sqsubset,between}$, the objective of the emph{2-interval pattern problem} is to find a largest subset of 2-intervals that is $mathcal{R}$-comparable. The 2-interval pattern problem is known to be $W[1]$-hard when $|mathcal{R}|=3$ and $NP$-hard when $|mathcal{R}|=2$ (except for $mathcal{R}={<,sqsubset}$, which is solvable in quadratic time). In this paper, we fully settle the parameterized complexity of the problem by showing it to be $W[1]$-hard for both $mathcal{R}={sqsubset,between}$ and $mathcal{R}={<,between}$ (when parameterized by the size of an optimal solution); this answers an open question posed by Vialette [Encyclopedia of Algorithms, 2008].
Download