A Cubic-Vertex Kernel for Flip Consensus Tree |
| |
Authors: | Christian Komusiewicz Johannes Uhlmann |
| |
Affiliation: | 1. Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, 10587, Berlin, Germany
|
| |
Abstract: | Given a bipartite graph G=(V c ,V t ,E) and a nonnegative integer k, the NP-complete Minimum-Flip Consensus Tree problem asks whether G can be transformed, using up to k edge insertions and deletions, into a graph that does not contain an induced P 5 with its first vertex in V t (a so-called M-graph or Σ-graph). This problem plays an important role in computational phylogenetics, V c standing for the characters and V t standing for taxa. Chen et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3:165–173, 2006). showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6 k ?|V t |?|V c |). Subsequently, Böcker et al. (ACM Trans. Algorithms 8:7:1–7:17, 2012) presented a refined search tree algorithm with running time O(4.42 k (|V t |+|V c |)+|V t |?|V c |). We continue the study of Minimum-Flip Consensus Tree parameterized by k. Our main contribution are polynomial-time executable data reduction rules yielding a problem kernel with O(k 3) vertices. In addition, we present an improved search tree algorithm with running time O(3.68 k ?|V c |2|V t |). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|