Matthias Mnich, Technische Universiteit Eindhoven
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 "u is between v and w", 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". |