2026-08-15T09:01:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1760 2024-03-06T10:33:03Z ddc:004 open_access

A Cubic-Vertex Kernel for Flip Consensus Tree Komusiewicz, Christian Uhlmann, Johannes Fixed-parameter algorithm problem kernel NP-hard problem graph modification problem computational phylogenetics 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Johannes Uhlmann 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1760 urn:nbn:de:0030-drops-17600 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1760 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode