Betweenness parameterized above tight lower bound

G. Gutin, E.J. Kim, M. Mnich, A. Yeo

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)

Abstract

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 "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". 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.
Original languageEnglish
Pages (from-to)872-878
JournalJournal of Computer and System Sciences
Volume76
Issue number8
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Betweenness parameterized above tight lower bound'. Together they form a unique fingerprint.

Cite this