10.4230/LIPICS.FSTTCS.2008.1760
Komusiewicz, Christian
Christian
Komusiewicz
Uhlmann, Johannes
Johannes
Uhlmann
A Cubic-Vertex Kernel for Flip Consensus Tree
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Fixed-parameter algorithm
problem kernel
NP-hard problem
graph modification problem
computational phylogenetics
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
2008
2008-12-05
2008-12-05
2008-12-05
en
urn:nbn:de:0030-drops-17600
10.4230/LIPIcs.FSTTCS.2008
978-3-939897-08-8
1868-8969
10.4230/LIPIcs.FSTTCS.2008
LIPIcs, Volume 2, FSTTCS 2008
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
2013
2
3
280
291
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hariharan, Ramesh
Ramesh
Hariharan
Mukund, Madhavan
Madhavan
Mukund
Vinay, V
V
Vinay
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
2
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
453254 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
Given a bipartite graph G=(V_c,V_t,E) and a non-negative 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 Sigma-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 TCBB 2006] showed that Minimum-Flip Consensus Tree is NP-complete and presented a parameterized algorithm with running time O(6^k\cdot |V_t|\cdot |V_c|).
Recently, Boecker et al. [IWPEC'08] presented a refined search tree algorithm
with running time O(4.83^k(|V_t|+|V_c|) + |V_t|\cdot |V_c|).
We complement these results by polynomial-time executable data reduction rules yielding a problem kernel with O(k^3) vertices.
LIPIcs, Vol. 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, pages 280-291