文章基本信息

标题：On the Weighted Quartet Consensus Problem
本地全文：下载
作者：Manuel Lafond ; Celine Scornavacca
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：78
页码：28:1-28:18
DOI：10.4230/LIPIcs.CPM.2017.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：phylogenetic tree; consensus tree; quartets; complexity; fixed-parameter tractability