  Jansson and Sung showed that, given a dense set of input triplets T
(representing hypotheses about the local evolutionary relationships of triplets
of species), it is possible to determine in polynomial time whether there
exists a level-1 network consistent with T, and if so to construct such a
network. They also showed that, unlike in the case of trees (i.e. level-0
networks), the problem becomes NP-hard when the input is non-dense. Here we
further extend this work by showing that, when the set of input triplets is
dense, the problem is even polynomial-time solvable for the construction of
level-2 networks. This shows that, assuming density, it is tractable to
construct plausible evolutionary histories from input triplets even when such
histories are heavily non-tree like. This further strengthens the case for the
use of triplet-based methods in the construction of phylogenetic networks. We
also show that, in the non-dense case, the level-2 problem remains NP-hard.
