  In evolutionary biology, networks are becoming increasingly used to represent
evolutionary histories for species that have undergone non-treelike or
reticulate evolution. Such networks are essentially directed acyclic graphs
with a leaf set that corresponds to a collection of species, and in which
non-leaf vertices with indegree 1 correspond to speciation events and vertices
with indegree greater than 1 correspond to reticulate events such as gene
transfer. Recently forest-based networks have been introduced, which are
essentially (multi-rooted) networks that can be formed by adding some arcs to a
collection of phylogenetic trees (or phylogenetic forest), where each arc is
added in such a way that its ends always lie in two different trees in the
forest. In this paper, we consider the complexity of deciding whether or not a
given network is proper forest-based, that is, whether it can be formed by
adding arcs to some underlying phylogenetic forest which contains the same
number of trees as there are roots in the network. More specifically, we show
that it can be decided in polynomial time whether or not a binary, tree-child
network with $m \ge 2$ roots is proper forest-based in case $m=2$, but that
this problem is NP-complete for $m\ge 3$. We also give a fixed parameter
tractable (FPT) algorithm for deciding whether or not a network in which every
vertex has indegree at most 2 is proper forest-based. A key element in proving
our results is a new characterization for when a network with $m$ roots is
proper forest-based which is given in terms of the existence of certain
$m$-colorings of the vertices of the network.
