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 $R\in\{ <,\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}\neq\emptyset$, if every pair of 2-intervals in $\mathcal{ R}$ are $R$-comparable for some $R\in\mathcal{ 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].
Categories: cs.CG