Betweenness parameterized above tight lower bound

详细信息    查看全文

• 作者：Gregory Gutin ; Eun Jung Kim ; Matthias Mnich ; Anders Yeo
• 关键词：Betweenness ; Parameterized problems ; Fixed-parameter tractable ; Kernel ; Polynomial kernel ; Probabilistic method
• 刊名：Journal of Computer and System Sciences
• 出版年：2010
• 出版时间：December 2010
• 年：2010
• 卷：76
• 期：8
• 页码：872-878
• 全文大小：183 K

文摘

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the Betweenness problem parameterized above its tight lower bound, which is stated as follows. For a set V of variables and set of constraints “v_i is between v_j and v_k”, decide whether there is a bijection from V to the set {1,…,V} satisfying at least of the constraints in . Our result solves an open problem attributed to Benny Chor in Niedermeier's monograph “Invitation to Fixed-Parameter Algorithms”. The betweenness problem is of interest in molecular biology. An approach developed in this paper can be used to determine parameterized complexity of a number of other optimization problems on permutations parameterized above or below tight bounds.