Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs

Abstract

The MINIMUM ROOTED TRIPLET INCONSISTENCY (MINRTI) problem represents a key computational task in the construction of phylogenetic trees. Inspired by Aho et al's seminal paper and Bryant's thesis, we describe an edge-labelled multigraph problem, Minimum Dissolving GRAPH (MINDG) and show that it is equivalent to MinRTI. We prove that on an n-vertex graph, for every ε > 0, MINDG is hard to approximate within a factor in O(2log1-ε n), even on trees formed by multiedges. Via a further reduction, this result applies to MINRTI, resolving the open question of whether there is a sub-linear approximation factor for MINRTI. In addition, we provide polynomial-time algorithms that return optimal solution..