Quadratic Kernelization for Convex Recoloring of Trees |
| |
| Authors: | Hans L Bodlaender Michael R Fellows Michael A Langston Mark A Ragan Frances A Rosamond Mark Weyer |
| |
| Affiliation: | 1.Department of Information and Computing Sciences,Utrecht University,Utrecht,The Netherlands;2.Parameterized Complexity Research Unit, Office of the DVC (Research),University of Newcastle,Callaghan,Australia;3.Australian Research Council Centre of Excellence in Bioinformatics,Brisbane,Australia;4.Department of Computer Science,University of Tennessee,Knoxville,USA;5.Computer Science and Mathematics Division,Oak Ridge National Laboratory,Oak Ridge,USA;6.Institute for Molecular Bioscience,University of Queensland,Brisbane,Australia;7.Institut für Informatik,Humboldt-Universit?t zu Berlin,Berlin,Germany |
| |
| Abstract: | The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input
consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem
was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k)
k
n
4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of
size O(k
2). |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
