Title: Binets: fundamental building blocks for phylogenetic networks,
Abstract: Phylogenetic networks are a generalization of evolutionary trees that are
used by biologists to represent the evolution of organisms which have undergone
reticulate evolution. Essentially, a phylogenetic network is a directed acyclic
graph having a unique root in which the leaves are labelled by a given set of
species. Recently, some approaches have been developed to construct
phylogenetic networks from collections of networks on 2- and 3-leaved networks,
which are known as binets and trinets, respectively. Here we study in more
depth properties of collections of binets, one of the simplest possible types
of networks into which a phylogenetic network can be decomposed. More
specifically, we show that if a collection of level-1 binets is compatible with
some binary network, then it is also compatible with a binary level-1 network.
Our proofs are based on useful structural results concerning lowest stable
ancestors in networks. In addition, we show that, although the binets do not
determine the topology of the network, they do determine the number of
reticulations in the network, which is one of its most important parameters. We
also consider algorithmic questions concerning binets. We show that deciding
whether an arbitrary set of binets is compatible with some network is at least
as hard as the well-known Graph Isomorphism problem. However, if we restrict to
level-1 binets, it is possible to decide in polynomial time whether there
exists a binary network that displays all the binets. We also show that to find
a network that displays a maximum number of the binets is NP-hard, but that
there exists a simple polynomial-time 1/3-approximation algorithm for this
problem. It is hoped that these results will eventually assist in the
development of new methods for constructing phylogenetic networks from
collections of smaller networks.