2009/07/30 by Gregory Gutin, Eun Jung Kim, Gutin, Gregory +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.0907.5427
openalex publication_date 2009/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 "vi is between vj and vk", decide whether there is a bijection from V to the set \1,…,|V|\ satisfying at least |\mathcal C|/3 + κ 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.