Iersel, Leo vanSemple, CharlesSteel, M. A.2016-07-282016-07-2820101172-8531http://hdl.handle.net/10092/12530Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The TREE CONTAINMENT problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the CLUSTER CONTAINMENT problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that TREE CONTAINMENT is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both TREE CONTAINMENT and CLUSTER CONTAINMENT remain NP-complete.enAll Rights Reservedalgorithmscomputational complexityphylogenetic treesphylogenetic networksDiscussion / Working PapersFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics