Rooted Triplet Inconsistency: Hardness and Algorithms

The Minimum Rooted Triplet Inconsistency (MinRTI) problem represents a key computational task in the construction of phylogenetic trees, whose goal is the reconstruction of a large tree that incorporates the information contained in a given set of triplets. Inspired by Aho et al's seminal paper and Bryant's thesis, we consider an edge-labelled multigraph problem, called Minimum Dissolving Graph (MinDG), and we show that is equivalent to MinRTI. We prove that on an n-vertex graph, for every x > 0, MinDG is hard to approximate within a factor in O(2^{\og^{1-x}n}), even on trees formed by multi-edges. Then, via a further reduction, this inapproximability result extends to MinRTI. In addition, we provide polynomial-time algorithms that return optimal solutions when the input multigraph is restricted to a multi-edge path or a simple tree. Finally, we investigate the complexity of MinRTI (and of MinDG) when the number of occurrences of every label is bounded, and we show that the problem is APX-hard when this bound is equal to five.