2026-08-16T03:25:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7328 2024-03-06T10:40:09Z ddc:004 open_access

On the Weighted Quartet Consensus Problem Lafond, Manuel Scornavacca, Celine phylogenetic tree consensus tree quartets complexity fixed-parameter tractability In phylogenetics, the consensus problem consists in summarizing a set of phylogenetic trees that all classify the same set of species into a single tree. Several definitions of consensus exist in the literature; in this paper we focus on the Weighted Quartet Consensus problem, a problem with unknown complexity status so far. Here we prove that the Weighted Quartet Consensus problem is NP-hard and we give a 1/2-factor approximation for this problem. During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation. We also investigate the fixed-parameter tractability of this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Lafond and Celine Scornavacca 2017 Is Part Of LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2017.28 urn:nbn:de:0030-drops-73284 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.28 eng https://creativecommons.org/licenses/by/3.0/legalcode