  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.
