Leo van Iersel (Eindhoven): Constructing evolutionary networks from triplets

Given evolutionary relationships for each set of three species our goal is find a network that displays the evolution of all species. We give a polynomial time algorithm that finds a level-2 network consistent with a dense triplet set if such a network exists. We also prove that for non-dense input sets the problem becomes NP-hard.