  Phylogenetic networks provide a way to describe and visualize evolutionary
histories that have undergone so-called reticulate evolutionary events such as
recombination, hybridization or horizontal gene transfer. The level k of a
network determines how non-treelike the evolution can be, with level-0 networks
being trees. We study the problem of constructing level-k phylogenetic networks
from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for
each k, a level-k network that is uniquely defined by its triplets. We
demonstrate the applicability of this result by using it to prove that (1) for
all k of at least one it is NP-hard to construct a level-k network consistent
with all input triplets, and (2) for all k it is NP-hard to construct a level-k
network consistent with a maximum number of input triplets, even when the input
is dense. As a response to this intractability we give an exact algorithm for
constructing level-1 networks consistent with a maximum number of input
triplets.
