Betweenness Parameterized Above Tight Lower Bound

Abstract

We study ordinal embedding relaxations in the realm of parameterized complexity. We prove the existence of a quadratic kernel for the {\sc Betweenness} problem parameterized above its tight lower bound, which is stated as follows. For a set $V$ of variables and set $\mathcal{C}$ of constraints "$v_i$ \mbox{is between} $v_j$ \mbox{and} $v_k$", decide whether there is a bijection from $V$ to the set $\{1,\dots ,|V|\}$ satisfying at least $|\mathcal{C}|/3+\kappa$ of the constraints in $\mathcal{C}$. 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.

References in corpus (2)

• Systems of Linear Equations over ${\mathbb{F}}_2$ and Problems Parameterized Above Average
• Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems

Cited by in corpus (1)

• A Probabilistic Approach to Problems Parameterized Above or Below Tight Bounds