Constructing a Minimum-Level Phylogenetic Network from a Dense Triplet Set in Polynomial Time

For a given set L of species and a set T of triplets on L, we want to construct a phylogenetic network which is consistent with T, i.e which represents all triplets of T. The level of a network is defined as the maximum number of hybrid vertices in its biconnected components. When T is dense, there exist polynomial time algorithms to construct level-0, 1, 2 networks [1, 9, 10, 17]. For higher levels, partial answers were obtained in [18] with a polynomial time algorithm for simple networks. In this paper, we detail the first complete answer for the general case, solving a problem proposed in [10] and [17]: for any k fixed, it is possible to construct a minimum level-k network consistent with T, if there is any, in time O(|T |k+1nb 4k3 c+1) 1