Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound.

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".

back to EIDMA Seminar Combinatorial Theory announcements