Rooted Triplet Inconsistency: Hardness and Algorithms
Andrew Chester, Riccardo Bondi, and Anthony Wirth
Info
|
Date
|
4th July 2014
|
|
Time
|
16:00
|
|
Place
|
Room 051, Wolfson Building, Parks Road
|
Abstract
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.
Further info
