A Cubic-Vertex Kernel for Flip Consensus Tree

Komusiewicz, Christian; Uhlmann, Johannes

doi:10.4230/LIPIcs.FSTTCS.2008.1760

Document

A Cubic-Vertex Kernel for Flip Consensus Tree

Authors Christian Komusiewicz, Johannes Uhlmann

Part of: Volume: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2008-12-05

PDF

File

PDF

LIPIcs.FSTTCS.2008.1760.pdf

Filesize: 442 kB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSTTCS.2008.1760
URN: urn:nbn:de:0030-drops-17600

Subject Classification

Keywords

Fixed-parameter algorithm
problem kernel
NP-hard problem
graph modification problem
computational phylogenetics

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

Abstract

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.

Cite As Get BibTex

Christian Komusiewicz and Johannes Uhlmann. A Cubic-Vertex Kernel for Flip Consensus Tree. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 280-291, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008) https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1760

Author Details

Christian Komusiewicz

Johannes Uhlmann

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail