title: Which Phylogenetic Networks are Merely Trees with Additional Arcs?
abstract: A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on "2-SAT") that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.
authors.affiliation: Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, University of Western Sydney, Australia;
authors.forename: Andrew R
authors.initials: AR
authors.lastname: Francis
authors.affiliation: Biomathematics Research Centre, University of Canterbury, New Zealand mike.steel@canterbury.ac.nz.
authors.forename: Mike
authors.initials: M
authors.lastname: Steel
mesh_terms: D000465:Algorithms; D002965:Classification; D003198:Computer Simulation / Q000592:standards; D010802:Phylogeny
keywords: 2-SAT; Algorithm; Antichain; Phylogenetic network; phylogenetic tree; reticulate evolution