论文标题
两个间隔模式问题的参数化复杂性
Parameterized Complexity of Two-Interval Pattern Problem
论文作者
论文摘要
一个\ emph {2 interval}是真实行上两个不相交间隔的联合。如果它们的交叉点为空，则两个2个2间值$ d_1 $和$ d_2 $是\ emph {dissph {disshoint}（即，$ d_1 $的间隔不超过$ d_2 $的任何间隔）。两个不同的2个间体之间可以存在三种不同的关系。也就是说，嵌套（$ \ sqsubset $）和交叉（$ \之间的$ \）之前（$ \ sqsubset $）。对于某些$ r \ in \ {<，\ sqsubset，\} $之间的两个2个2间值$ d_1 $和$ d_2 $称为\ emph {$ r $ -comparable}，如果\ {<，\ sqsubset，\ n之间一个不相关的2英寸的$ \ natervals的$ \ MATHCAL {D} $是$ \ Mathcal {r} $ - 可比较，对于某些$ \ Mathcal {r} \ subseteq \ subseteq \ {<，\ sqsubset，\ \ sqsubset，\之间$ \ MATHCAL {R} $是$ r $ - 在\ Mathcal {r} $中的$ r \。给定一组2个间隙和一些$ \ MATHCAL {R} \ subseteq \ {<，\ sqsubset，\之间\} $之间的目标，\ emph {2-Interval pattern pattern问题}的目的是找到2个intervals的2个intervals，该子集的最大子集是$ \ nathcal calcal {r} $ {r} $ - r} $ - 可比性。 当$ | \ mathcal {r} | = 3 $和$ np $ -hard当$ | \ Mathcal {r} | = 2 $时，已知2个间隙模式问题是$ W [1] $ - 很难。在本文中，我们通过表明$ W [1] $的参数复杂性（对于两个$ \ nathcal {r} = \ {\ sqsubset，\ \} $和$ \ nathcal {r} = \} = \ {<，\ {<，\ wementer parame parame and optim and optim and optim and optim and optim and optim）这回答了Vialette [算法百科全书，2008年]提出的一个公开问题。
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].
