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 tight lower bound, which is stated as follows. For a set V of variables and set C of constraints "vi is between vj and vk", decide whether there is a bijection from V to the set {1, . . . , |V |} satisfying at least |C|/3 + k of the constraints in C. Our result solves an open problem attributed to Benny Chor in Niedermeier’s monograph "Invitation to Fixed-Parameter Algorithms."
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.

Original language | English |
---|

Publisher | s.n. |
---|

Number of pages | 12 |
---|

Publication status | Published - 2009 |
---|

Name | arXiv.org [cs.DS] |
---|

Volume | 0907.5427 |
---|