Abstract
In phylogenetics, the consensus problem consists in summarizing a set of phylo-genetic 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, whose complexity status has remained open since it was posed in 2008. Here we show that the Weighted Quartet Consensus problem is NP-hard, and provide several results on the approximability of the problem. Namely, we show that Weighted Quartet Consensus admits a polynomial-time approximation scheme (PTAS) based on prior work of Jiang, Kearney and Li. The algorithm is unfortunately impractical, and so we also present an implementable 1/2-factor approximation algorithm. During the process, we propose a derandomization procedure of a previously known randomized 1/3-factor approximation , which guarantees that a tree that contains a third of any given multi-set of quartets can be found deterministically. We also investigate the fixed-parameter tractability of this problem.