Noname manuscript No.
(will be inserted by the editor)

Binets: fundamental building blocks for phylogenetic networks

arXiv:1701.08995v1 [q-bio.PE] 31 Jan 2017

Leo van Iersel · Vincent Moulton · Eveline de Swart ·
Taoyang Wu

the date of receipt and acceptance should be inserted later

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.
Part of this work was conducted while Vincent Moulton was visiting Leo van Iersel on a visitors grant funded by the Netherlands
Organization for Scientific Research (NWO). Leo van Iersel was partially supported by NWO, including Vidi grant 639.072.602, and
partially by the 4TU Applied Mathematics Institute. We thank the editor and the two anonymous referees for their constructive
comments.
Leo van Iersel
Delft Institute of Applied Mathematics
Delft University of Technology
The Netherlands
E-mail: l.j.j.v.iersel@gmail.com
Vincent Moulton and Taoyang Wu
School of Computing Sciences
University of East Anglia
Norwich
United Kingdom
E-mail: v.moulton@uea.ac.uk
Eveline de Swart
Delft Institute of Applied Mathematics
Delft University of Technology
The Netherlands
E-mail: Eveline_de_Swart@hotmail.com
Taoyang Wu
School of Computing Sciences
University of East Anglia
Norwich
United Kingdom
E-mail: Taoyang.Wu@uea.ac.uk

2

Leo van Iersel et al.

x

y

z

x

y

z

x

y

y

z

x

z

Fig. 1: An example of two level-1 trinets (left) that display the same set of three binets (right). All arcs are
directed downwards.
Keywords reticulate evolution · phylogenetic network · subnetwork · binet · algorithm
1 Introduction
Phylogenetic networks are a generalization of evolutionary trees which biologists use to represent the evolution
of species that have undergone reticulate evolution. Such networks are essentially directed acyclic graphs having
a unique root in which the leaves are labelled by a set X of species [14]. In contrast to evolutionary trees,
which can only represent speciation events, phylogenetic networks permit the representation of evolutionary
events such as gene transfer and hybridization which are known to occur in organisms such as bacteria and
plants, respectively. Although theoretical properties of evolutionary trees have been studied since at least the
1970’s, phylogenetic networks have been considered from this perspective only more recently, especially the
rooted variants which we will focus on in this paper.
One of the most important open questions concerning phylogenetic networks is how to construct them for
biological datasets [3]. It is now common practice for biologists to construct evolutionary trees from molecular
data, and several computer programs are available for this purpose [7]. However, the problem of constructing
networks from such data is an active area of research, and there are only a limited number of programs
available for biologists to perform this task. A survey of some of these methods and the theory underpinning
phylogenetic networks may be found in [9, 14, 15].
One approach that has been recently developed for constructing phylogenetic networks involves building
them up from smaller networks, using what can be thought of as a divide-and-conquer approach [16]. In
particular, for a set X of species, a network is constructed for every subset of X size 3 (called a trinet), and
then the trinets are puzzled together to build a network (see Figure 1 for an example of a trinet). This approach
constructs and is based on level-1 networks, networks that are slightly more general than evolutionary trees
(see Section 2 for the definition of such networks).
At first sight, it might appear that trinets are the simplest possible networks that could be considered for
building up networks from smaller ones. However, trinets contain even simpler networks called binets, networks
with 2 leaves (see e.g. Figure 1 for a level-1 trinet and the binets that it displays). Note that whereas binets
are the smallest informative building blocks for phylogenetic networks, for rooted phylogenetic trees, these
are 3-leaf trees (see e.g. [5]). Interestingly, even though binets are in themselves very simple, the collection of
binets displayed by a network can still contain some useful information concerning the network. Indeed, in the
aforementioned approach for building level-1 networks from trinets, binets are used in the process of puzzling
together the trinets.
In light of these considerations some obvious questions immediately arise concerning binets. For example, when is a collection of binets displayed by some phylogenetic network (the compatibility problem), and
how much information might we expect to extract concerning a phylogenetic network by just looking at the
collection of binets that it displays? In this paper, we shall address these and related algorithmic questions
concerning binets. It is hoped that these results will be useful in future for developing improved methods for
constructing phylogenetic networks from smaller networks.
We now present a summary of the rest of the paper. After introducing some preliminaries concerning
phylogenetic networks in the next section, we derive a key structural result for networks (Corollary 1) which
is useful in identifying which of the two possible types of binet is displayed on two leaves within a binary
phylogenetic network (that is a network in which all internal vertices have degree 3). Using this theorem, in
Section 4 we show that the collection of level-1 binets displayed by any binary phylogenetic network can always
be displayed by some binary level-1 network (Theorem 3). This reduces the problem of understanding binets
displayed by arbitrary binary networks to level-1 networks. To prove this result, we develop a framework which
also implies that there is a polynomial-time algorithm in |X| for deciding whether or not a collection of level-1
binets with combined leaf-set X can be displayed by some network with leaf-set X, and, if it is, gives a level-1
network that does this (see Section 6). Note that this is related to an algorithm presented in [11].

Binets: fundamental building blocks for phylogenetic networks

3

In Section 5, we turn to the question as to what can be deduced about the features of a phylogenetic
network just by considering the collection of binets that it displays. Note that, as might be expected, there
are networks - even trinets - that display the same set of binets but that are not equivalent. For example, the
two trinets in Figure 1 both display the same set of binets, but they are not equivalent. Even so, we will show
in Theorem 4 that if two level-1 networks both display exactly the same collection of binets, then they must
have the same number of reticulation vertices (indegree-2 vertices). Note that the number of such vertices
corresponds to the number of reticulate evolutionary events, such as hybridization, that took place in the
evolutionary history of the species labelling the leaves of the network. Consequently, the binets displayed by
a network can at least capture a useful course-grained feature of the network in question.
In Sections 6 and 7, we consider some algorithmic questions concerning binets. As we have mentioned
above, it can be decided in polynomial time in |X| as to when a collection of binets with combined leaf-set
X is displayed by some level-1 network on X. However, we show that if we consider arbitrary binets (i.e. not
necessarily binary or level-1) then this decision problem becomes at least as hard as the graph-isomorphism
problem (see Theorem 5), one of the most famous problems whose complexity is still unknown. In addition,
in Section 7 we consider a related problem which, for a given collection of binary level-1 binets, asks for
a network which displays the maximum number of binets in this collection. This is closely related to the
maximum rooted triplet consistency problem for evolutionary trees [5]. We show that the binet problem is
NP-complete (Theorem 6), by giving a reduction from the feedback-arc set problem. However, we also show
that the problem is 1/3-approximable. In fact, given any collection of binary level-1 binets we can always
find some network that displays at least 1/3 of the binets (see Theorem 7). We conclude in Section 8 with
discussion of some possible future research directions, and a brief discussion of a potential application of our
results.

2 Preliminaries
Throughout this paper, X is a non-empty finite set (which usually represents a set of species or organisms).

2.1 Digraphs
A directed graph, or digraph for short, G = (V, E) consists of a finite set V = V (G) of vertices and a set
E = E(G) of arcs, where each arc is an ordered pair (u, v) of vertices in V in which u is said to be a parent
of v, denoted by u = p(v), and v a child of u. All digraphs studied here contain no loops, that is, vertices
that are children of themselves. The in-degree of vertex u is the number of vertices v in V such that (v, u) is
an arc, and the out-degree of u is the number of vertices w with (u, w) being an arc. A root is a vertex with
in-degree 0. A leaf is a vertex of out-degree 0 and the set of leaves is denoted by L(G). Any vertex in G that
is neither a root nor a leaf is referred to as an interior vertex. In addition, an interior vertex is a tree vertex if
it has in-degree 1, and a reticulation vertex if it has in-degree greater than 1.
A directed path or dipath in a digraph is a sequence u0 , u1 , . . . , uk (k ≥ 1) of vertices such that (ui−1 , ui )
is an arc for 1 ≤ i ≤ k. An acyclic digraph is a digraph that does not contain any directed path starting and
ending at the same vertex. If an acyclic digraph G contains a unique root, which is usually designated by
ρ = ρ(G), then it will be referred to as a rooted acyclic digraph.
An acyclic digraph G induces a canonical partial order ≺G on its vertex set V , that is, v ≺G u if there
exists a directed path from u to v. In this case, we shall say that v is below u. When the digraph G is clear
from the context, ≺G will be written as ≺. In addition, we write v  u if u = v or u ≺ v. Given a subset U of
the vertex set of an acyclic digraph, we say that u ∈ U is a lowest vertex in U if there is no v ∈ U with v ≺ u.
Let G be the undirected graph obtained from digraph G by ignoring the direction of the arcs in G. Then G
is connected if G is connected, that is, there exists an undirected path between every pair of distinct vertices in
G. Note that a rooted acyclic digraph is necessarily connected (since each connected component of an acyclic
digraph has at least one root). A cut vertex is a vertex of G whose removal disconnects G. Similarly, a cut arc
is an arc of G whose removal disconnects G. A directed graph is biconnected if it contains no cut vertex, and a
biconnected component of G is a maximal biconnected subgraph, which is called trivial if it contains precisely
one arc (which is necessarily a cut arc), and non-trivial otherwise.

4

Leo van Iersel et al.

2.2 Phylogenetic networks
A phylogenetic network N on X is a rooted acyclic digraph whose leaves are bijectively labeled by the elements
in X and which does not contain any vertex with in-degree one and out-degree one. For simplicity, we will
just write L(N ) = X in case there is no confusion about the labeling. To simplify the argument, throughout
this paper we will also assume that all leaves in a phylogenetic network have in-degree one. In addition, a
phylogenetic network is binary if each tree vertex, as well as the root, has out-degree 2, and each reticulation
vertex has in-degree 2 and out-degree 1. Finally, we say a binary phylogenetic network is level -k (k ≥ 0) if
each of its biconnected components contains at most k reticulation vertices. To some extent, the concept of
the level of a phylogenetic network can be regarded as a measure of its ‘distance’ to being a phylogenetic tree.
In particular, a binary phylogenetic network is a phylogenetic tree if and only if it is level-0. A phylogenetic
network is called simple if it contains precisely one non-trivial biconnected component H and no cut arcs other
than the ones leaving H.
Two networks N1 = (V1 , E1 ) and N2 = (V2 , E2 ) on X are said to be isomorphic if there exists a bijection
f : V1 → V2 such that f (x) = x for all x ∈ X, and (u, v) is an arc in N1 if and only if (f (u), f (v)) is an arc
in N2 .
Finally, the cluster of a vertex u, denoted by CN (u) = C(u), is defined as the subset of X consisting of the
leaves below u. Here we will use the convention that C(u) = {u} if u is a leaf.

2.3 Stable ancestors and binets
Given a phylogenetic network N on X and a subset U ⊆ V (N ), a stable ancestor of U in N is a vertex v
in V (N ) \ U such that every path in N from the root to a vertex in U contains v. Note that for two stable
ancestors u and u0 of U , we have either u  v or v  u. Therefore, there exists a unique lowest vertex in the
set of stable ancestors of U , which will be referred to as the lowest stable ancestor of U in N and denoted by
lsaN (U ) = lsa(U ). Note that for a subset Y of X with |Y | ≥ 2, there exist two elements x and y in Y such
that lsa(Y ) = lsa({x, y}). For simplicity, we also write lsa({x, y}) as lsa(x, y).
The following property of lowest stable ancestors will be useful.
Lemma 1 Suppose that u and v are two vertices in a phylogenetic network such that u ≺ v ≺ lsa(u), then
we have lsa(v)  lsa(u).
Proof Since u ≺ v, we know that there exists a dipath P from ρ to u that contains v. By the definition of
lowest stable ancestor, we know that lsa(u) and lsa(v) are contained in P . Hence, either lsa(v)  lsa(u) or
lsa(u) ≺ lsa(v). If lsa(u) ≺ lsa(v), then we have v ≺ lsa(u) ≺ lsa(v). Then there exists a dipath P 0 from
ρ to v that does not contain lsa(u) (otherwise lsa(u) would be a stable ancestor of v that is below lsa(v)).
Using that u ≺ v ≺ lsa(u), it follows that there exists a dipath from ρ to u that does not contain lsa(u), a
contradiction. Therefore, lsa(v)  lsa(u).
t
u
For Y ⊆ X, the subnet of N on Y , denoted by N |Y , is defined as the subgraph obtained from N by deleting
all vertices that are not on any path from lsa(Y ) to elements in Y and subsequently suppressing all in-degree
1 and out-degree 1 vertices and parallel arcs until no such vertices or arcs exist. A network N 0 is said to be
displayed by network N if N 0 = N |Y for some Y ⊆ X.
Note that, by definition, N |X = N if and only if lsa(X) = ρ(N ). In this case, N is referred to as a
recoverable network. Note that every subnet of N is necessarily recoverable. Moreover, a collection of subnets
is displayed by some network if and only if it is displayed by some recoverable network. Therefore, we assume
all networks in this paper to be recoverable.
A binet is a phylogenetic network with precisely two leaves, while a trinet is a phylogenetic network with
precisely three leaves. Let
B(N ) = {N |Y : Y ⊆ X and |Y | = 2}
be the collection of binets displayed by N . Note that there are precisely three binary level-1 binets on a set
{x, y}, and they can be grouped into two types: the “tree type”, T (x, y), and the “reticulate type” R(x; y)
and R(y; x) (see Figure 2). A collection of binets B on X is a collection of binets such that the union of the
leaf-sets of the binets is equal to X.

Binets: fundamental building blocks for phylogenetic networks

x

y

T (x, y)

x

y

y

R(x; y)

5

x
y

R(y; x)

x
level-2

Fig. 2: The three binary level-1 binets on {x, y} and an example of a level-2 binet.
ρ
lsa(v)
x
r

v
y

p

q

Fig. 3: Example for the proof of Theorem 1. The lowest stable ancestor of v is not equal to the root ρ. An
undirected path Pu between ρ and lsa(v) that does not contain the incoming arc of lsa(v) is indicated in
bold. Path Pu contains one alternating vertex r, for which the lowest stable ancestor is indeed equal to ρ.
3 A structure theorem
In this section we present a key result (Corollary 1) concerning the structure of the non-trivial biconnected
component of a simple network. Note that a similar result has been obtained for a special collection of (nonbinary) phylogenetic networks in [13].
Let G be a directed acyclic graph and let P = v0 , v1 , . . . , vt be an undirected path in the underlying
undirected graph G, then a vertex vi (with 1 ≤ i ≤ t − 1) is called alternating (with respect to P ) if we have
either {(vi−1 , vi ), (vi+1 , vi )} ⊆ E(G) or {(vi , vi−1 ), (vi , vi+1 )} ⊆ E(G). The number of alternating vertices
contained in P is denoted by alt(P ). Using this concept, we now prove the following theorem. See Figure 3
for an example.
Theorem 1 Let N be a binary phylogenetic network on X whose root ρ is in some non-trivial biconnected
component H. Then there exists a lowest vertex in H with lsa(v) = ρ.
Proof Let Γ0 (H) be the set of reticulation vertices v in H for which the distance (length of a shortest directed
path) between ρ and lsa(v) is minimum over all reticulation vertices in H. Note that Γ0 (H) 6= ∅.
We first show that lsa(v) = ρ for all v ∈ Γ0 (H). Suppose this were not the case. Then there exists a vertex
v ∈ Γ0 (H) such that lsa(v) ≺ ρ. Note that lsa(v) necessarily has outdegree 2 and therefore has indegree 1
since N is binary and lsa(v) 6= ρ. Denote the parent of lsa(v) by v ∗ . Since H is biconnected, there exists
some undirected path from ρ to lsa(v) that does not contain the edge e = {lsa(v), v ∗ }. Let Pu = v0 , . . . , vt ,
where v0 = ρ and vt = lsa(v), be such an undirected path for which alt(Pu ) is minimum.
We claim that alt(Pu ) = 1. To see this, note first that since v0 = ρ, vt = lsa(v) and vt−1 6= v ∗ , we know
that (v0 , v1 ) and (vt , vt−1 ) are arcs of N . Hence, alt(Pu ) is odd and strictly positive. Assume for the sake
of contradiction that alt(Pu ) 6= 1, then we have alt(Pu ) ≥ 3. Let vk (1 < k < t) be the second alternating
vertex contained in Pu (when travelling from v0 to vt ).
Now fix a directed path Pd in N from ρ to vk .
If the arc (v ∗ , lsa(v)) is not contained in Pd , then, we can find an undirected path from ρ to lsa(v)
that does not contain e and has fewer alternating vertices than Pu by following Pd until we reach a vertex
in {vk , . . . , vt } and then following Pu to lsa(v). This gives a contradiction.
Now assume that the arc (v ∗ , lsa(v)) is contained in Pd . Then we can find an undirected path from ρ
to lsa(v) that does not contain e and has only one alternating vertex as follows. Follow Pu up to vk and then
follow Pd backward from vk to lsa(v). Since this path has fewer alternating vertices than Pu , we again obtain
a contradiction.
We have thus shown that alt(Pu ) = 1. Denoting this alternating vertex in Pu by r, then r is necessarily
a reticulation by the choice of Pu . Hence, Pu consists of two directed paths: a directed path from ρ to r that
does not contain lsa(v) and a directed path from lsa(v) to r. However, this means that lsa(v) ≺ lsa(r), a
contradiction to the assumption that v ∈ Γ0 (H).

6

Leo van Iersel et al.

Hence, we know that Γ0 (H) is the set of reticulation vertices v of H such that lsa(v) = ρ and that Γ0 (H)
is not empty.
Now fix a vertex v in Γ0 (H) that is lowest over all vertices of Γ0 (H), that is, there does not exist a vertex
u in Γ0 (H) such that v ≺ u. It remains to show that v is lowest over all vertices of H. Assume that this is
not the case. Then the child c of v is also in H. If c were a reticulation then, by Lemma 1, lsa(v)  lsa(c).
However, this would imply that lsa(c) = ρ, contradicting the choice of v. Hence, c is a tree vertex.
Since H is biconnected, there exists some undirected path from ρ to c that does not contain v. Let Pu =
w0 , . . . , wt be such a path such that alt(Pu ) is minimum. Note that we have w0 = ρ and wt = c.
Since c is a tree vertex and Pu does not contain its parent v, (wt , wt−1 ) is an arc of N . Together with
(w0 , w1 ) being an arc in N , we know that alt(Pu ) is odd and strictly positive. We now show, using a similar
proof as above, that alt(Pu ) = 1. If this were not the case, then we would have alt(Pu ) ≥ 3. Let wk
(1 < k < t) be the second alternating vertex contained in Pu . We know that (wk , wk−1 ) and (wk , wk+1 ) are
two arcs contained in N . Now fix a directed path Pd in N from ρ to wk .
If the vertex v is not contained in Pd , then we can find an undirected path from ρ to c that does not contain
v and has fewer alternating vertices than Pu by following Pd from ρ it reaches a vertex from {wk , . . . , wt } and
then following Pu up to c. If v is contained in Pd , then we follow Pu from ρ to wk and then follow Pd from wk
to c and obtain an undirected path from ρ to c that does not contain v and has one alternating vertices, which
is less than the number of alternating vertices in Pu . In either case, we obtain a contradiction.
We have thus shown that alt(Pu ) = 1. Denoting this alternating vertex in Pu by r, then r is necessarily
a reticulation by the choice of Pu . Hence, Pu consists of two directed paths: a directed path from ρ to r
that does not contain v and a directed path from c to r. However, this means that v ≺ lsa(r), and hence
lsa(v)  lsa(r) in view of Lemma 1. This implies that r ∈ Γ0 (H), a contradiction to the assumption that v
is lowest among Γ0 (H).
t
u
The following is a direct consequence of the above theorem.
Corollary 1 Suppose that N is a simple binary phylogenetic network. Let H be the unique non-trivial biconnected component of N . Then there exists a lowest vertex v of H such that there exist two arc-disjoint directed
paths from the root of N to v.
4 Displaying binets by binary networks
A collection of binary level-1 binets is compatible if there exists some binary network that displays all binets
from the collection. In this section, we study the compatibility of binets. Our main result in this section
(Theorem 3) shows that when studying the compatibility of binets, we can restrict to binary level-1 networks.
We will restrict ourselves throughout this section to thin collections of binets, i.e. collections containing at
most one binet on x and y for all distinct x, y ∈ X. Clearly, any collection of binets that is not thin is not
compatible.
First, we need some new definitions. Given a digraph G, a sink set of G is a proper subset U ⊂ V (G) such
that there is no arc leaving U , that is, there exists no arc (x, y) with x ∈ U and y ∈ V (G) \ U . A bipartition
(or split) of V (G) into nonempty sets A and B, denoted A|B, is called
– Type I if both A and B are sink sets (i.e. there is no arc from any element in A to any element in B or
vice versa);
– Type II if either A or B (but not both) is a sink set; and
– Type III if for all x ∈ A, y ∈ B (x, y) is an arc in G if and only if (y, x) is an arc in G.

We say that A|B is a typed split of G if it is a split of Type I, II or III.
For a collection B of binary level-1 binets on X, we introduce the digraph D(B) with vertex set X and
(x, y) being an arc in D(B) if T (x, y) ∈ B or R(x; y) ∈ B. See Figure 4 for an example.
The following two lemmas show important properties of typed splits that will be used to establish Theorems 2 and 3.
Lemma 2 Suppose that B and B 0 are two thin collections of binary level-1 binets on X with B ⊆ B 0 . Then
each typed split of D(B 0 ) is a typed split of D(B).
Proof Suppose that A|B is a typed split of D(B 0 ). If A|B is of Type I in D(B 0 ), then it is of Type I in D(B)
since D(B) is a subgraph of D(B 0 ). Similarly, if A|B is of Type II in D(B 0 ), then it is of Type I or II in D(B).
If A|B is of Type III in D(B 0 ) then (since B 0 is thin) any binet on x and y with x ∈ A and y ∈ B is T (x, y).
Therefore, A|B is of Type I or III in D(B).
t
u

Binets: fundamental building blocks for phylogenetic networks
Binets: fundamental building blocks for phylogenetic networks

x4

x4

x1

x2

7
7

x6

x3

x1
x5

x5

x2

x3

x6
D(B)

N

Fig.
Fig. 4:
4: A
A digraph
digraph D(B)
D(B) representing
representing the
the set
set of
of binets
binets B
B=
= {T
{T(x
(x44,, xx33),
), R(x
R(x44;; xx11),
), R(x
R(x44;; xx22),
), TT(x
(x55,, xx11),
), R(x
R(x55;; xx22),
),
R(x
R(x55;; xx33),
), TT(x
(x66,, xx22),
), R(x
R(x66;; xx11),
), R(x
R(x66;; xx33)}
)} and
and aa network
network N
N displaying
displaying B.
B. The
The direction
direction of
of the
the arcs
arcs in
in N
N is
is
downward,
downward, and
and omitted.
omitted.
Lemma
Lemma 33 Suppose
Suppose that
that B
B is
is aa thin
thin collection
collection of
of binary
binary level-1
level-1 binets
binets on
on X.
X. If
If B
B is
is displayed
displayed by
by aa binary
binary
network,
then
D(B)
has
a
typed
split.
network, then D(B) has a typed split.
Proof
Proof Suppose
Suppose that
that B
B is
is displayed
displayed by
by aa binary
binary network.
network. Then
Then B
B is
is displayed
displayed by
by aa binary
binary recoverable
recoverable network
network N
N..
Let
Let B
B00 be
be the
the set
set of
of binary
binary level-1
level-1 binets
binets contained
contained in
in B(N
B(N).
). Then
Then we
we have
have B
B✓
⊆B
B00 ✓
⊆ B(N
B(N).
). By
By Lemma
Lemma 2,
2, it
it
suffices
suffices to
to show
show that
that D(B
D(B00)) has
has aa typed
typed split.
split.
Consider
Consider the
the root
root ⇢ρ of
of N
N,, which
which is
is equal
equal to
to lsa(X)
lsa(X) since
since N
N is
is recoverable.
recoverable. Denote
Denote the
the two
two children
children of
of ⇢ρ
by
by uu11 and
and uu22.. We
We consider
consider two
two cases.
cases.
The
The first
first case
case is
is that
that at
at least
least one
one arc
arc incident
incident with
with ⇢ρ is
is aa cut
cut arc.
arc. Then
Then the
the other
other arc
arc incident
incident with
with ⇢ρ is
is
also
also aa cut
cut arc.
arc. Then
Then let
let A
A=
= C(u
C(u11)) and
and B
B=
= C(u
C(u22).
). Note
Note that
that A|B
A|B is
is aa split
split because
because neither
neither A
A nor
nor B
B is
is empty.
empty.
In
In addition,
addition, for
for all
all xx 2
∈ A,
A, yy 2
∈B
B we
we have
have N
N||{x,y}
= TT(x,
(x, y)
y) and
and hence
hence A|B
A|B is
is aa Type
Type III
III split
split with
with respect
respect to
to
{x,y} =
D(B
D(B00).
).
In
In the
the second
second case,
case, both
both arcs
arcs incident
incident with
with ⇢ρ are
are not
not cut
cut arcs.
arcs. Hence,
Hence, the
the root
root ⇢ρ is
is contained
contained in
in aa non-trivial
non-trivial
biconnected
component
H
containing
u
and
u
.
By
Corollary
1,
there
exists
a
lowest
vertex
v
biconnected component H containing u11 and u22 . By Corollary 1, there exists a lowest vertex v in
in H
H with
with two
two
arc-disjoint
paths
P
,
P
from
⇢
to
v.
Since
v
is
a
lowest
vertex
in
H,
we
know
that
v
is
a
reticulation
arc-disjoint paths P11 , P22 from ρ to v. Since v is a lowest vertex in H, we know that v is a reticulation vertex
vertex
and
and the
the arc
arc leaving
leaving vv is
is aa cut
cut arc.
arc. Let
Let B
B=
= C(v)
C(v) and
and A
A=
=X
X \\ B.
B. Then
Then B
B is
is clearly
clearly nonempty.
nonempty. In
In addition,
addition,
A
A is
is nonempty,
nonempty, as
as otherwise
otherwise lsa(X)
lsa(X)  v,
v, aa contradiction
contradiction to
to the
the fact
fact that
that lsa(X)
lsa(X) =
= ⇢ρ (as
(as N
N is
is recoverable).
recoverable).
Therefore,
Therefore, A|B
A|B is
is aa split.
split.
Consider xx 2
∈A
A and
and yy 2
∈B
B and
and the
the subnetwork
subnetwork N
N||{x,y}
There is
is at
at least
least one
one directed
directed path
path from
from ⇢ρ to
to x,
x,
Consider
{x,y}.. There
and each
each such
such path
path contains
contains at
at least
least one
one arc
arc of
of P
P11 or
or P
P22.. Hence,
Hence, in
in the
the process
process of
of obtaining
obtaining N
N||{x,y}
from N
N,,
and
{x,y} from
the paths
paths P
P11,, P
P22 do
do not
not become
become parallel
parallel arcs.
arcs. Therefore,
Therefore, N
N||{x,y}
contains two
two arc-disjoint
arc-disjoint paths
paths from
from ⇢ρ to
to vv
the
{x,y} contains
and we
we can
can conclude
conclude that
that N
N||{x,y}
6= TT(x,
(x, y).
y). Therefore,
Therefore, ifif N
N||{x,y}
∈B
B⇤∗,, that
that is,
is, N
N||{x,y}
is level-1,
level-1, then
then
and
{x,y} is
{x,y} 6=
{x,y} 2
N||{x,y}
= R(x;
R(x; y).
y). This
This implies
implies that
that there
there is
is no
no arc
arc (y,
(y, x).
x). Therefore,
Therefore, A|B
A|B is
is aa Type
Type II or
or Type
Type II
II split
split of
of
N
{x,y} =
D(B⇤∗).
).
t
u
D(B
t
u
Note that
that the
the condition
condition that
that B
B is
is displayed
displayed by
by aa binary
binary network
network in
in the
the above
above lemma
lemma can
can not
not be
be weakened
weakened
Note
to that
that B
B is
is displayed
displayed by
by aa network.
network. For
For example,
example, consider
consider the
the binet
binet collection
collection B
B and
and network
network N
N in
in Figure
Figure 4.
4.
to
Although network
network N
N displays
displays B,
B, digraph
digraph D(B)
D(B) has
has no
no typed
typed split
split (as
(as can
can be
be easily
easily checked).
checked).
Although
We now
now introduce
introduce two
two operations,
operations, which
which can
can be
be used
used to
to combine
combine two
two phylogenetic
phylogenetic networks
networks into
into aa new
new
We
one.
Suppose
that
N
and
N
are
two
phylogenetic
networks
with
disjoint
leaf
sets.
Let
T
(N
,
N
)
be
the
one. Suppose that N11 and N22 are two phylogenetic networks with disjoint leaf sets. Let T (N11, N22) be the
phylogenetic
network
obtained
from
N
and
N
by
adding
a
new
vertex
v
and
two
arcs
from
v
to
the
roots
of
N11
phylogenetic network obtained from N11 and N22 by adding a new vertex v and two arcs from v to the roots of N
and
N
.
In
addition,
the
network
R(N
;
N
)
is
obtained
by
taking
a
binet
R(y
;
y
),
with
y
,
y
∈
/
L(N
)∪L(N
),
and N22. In addition, the network R(N11; N22) is obtained by taking a binet R(y11; y22), with y11, y22 2
/ L(N11)[L(N22),
and
replacing
y
by
the
root
of
N
,
for
i
=
1,
2.
See
Figure
5
for
examples.
and replacing yii by the root of Nii, for i = 1, 2. See Figure 5 for examples.
For aa binet
binet set
set B
B on
on X
X and
and aa subset
subset A
A✓
⊆ X,
X, we
we define
define
For
B|AA =
= {S
{S 2
∈B
B :: L(S)
L(S) ✓
⊆ A}.
A}.
B|
The next
next theorem
theorem can
can be
be used
used to
to determine
determine in
in polynomial
polynomial time
time whether
whether aa collection
collection of
of binary
binary level-1
level-1 binets
binets
The
is
displayed
by
some
binary
level-1
network.
See
Section
6
for
more
details.
is displayed by some binary level-1 network. See Section 6 for more details.

8

Leo van Iersel et al.

x
x
p

p
y

q

y
q

R(R(x; y); R(p; q))

T (R(x; y), R(p; q))

Fig. 5: Examples of two networks built recursively by using the operations introduced in the text.
Theorem 2 Suppose that B is a thin collection of binary level-1 binets on X. If there exists a typed split A|B
of D(B) such that B|A and B|B are both displayed by some binary level-1 network, then B is displayed by a
binary level-1 network. Moreover, if B is displayed by a binary level-1 network, then there exists at least one
typed split of D(B) and, for each typed split A|B of D(B), B|A and B|B are both displayed by some binary
level-1 network.
Proof First suppose that there exists a typed split A|B of D(B) such that B|A and B|B are displayed by binary
level-1 networks NA and NB , respectively.
If A|B is a Type I or Type III split of D(B), then consider the network N = T (NA , NB ). Then N is a
binary level-1 phylogenetic network on X and
B ⊆ {T (x, y) : x ∈ A, y ∈ B} ∪ B(NA ) ∪ B(NB ) = B(N ),
and so B is displayed by N .
If A|B is a Type II split of D(B), then without loss of generality we may assume that B is a sink set in
D(B). Now consider the network N = R(NA ; NB ). Then N is a binary level-1 phylogenetic network on X and
B ⊆ {R(x; y) : x ∈ A, y ∈ B} ∪ B(NA ) ∪ B(NB ) = B(N ),
and so B is displayed by N .
Now suppose that B is displayed by a binary level-1 network N . By Lemma 3, there exists a typed split
A|B of D(B). Then B|A ⊆ B(N |A ) and B|B ⊆ B(N |B ).
t
u
We now prove the main result of this section.
Theorem 3 Suppose that B is a thin collection of binary level-1 binets on X. Then B is displayed by a binary
level-1 network if and only if it is displayed by a binary network.
Proof Suppose that B is displayed by a binary network. We claim that B is also displayed by a binary level-1
network. We shall establish this claim by induction on |X|.
If |X| = 2, then B contains at most one binet, which has leaf set X. Therefore we know that B is displayed
by a binary level-1 network.
Now assume that |X| > 2, and the claim holds for all sets X 0 with 2 ≤ |X 0 | < |X|. Let N be a binary
network on X with B ⊆ B(N ). By Lemma 3, there exists a typed split A|B of D(B). Note that B|A ⊆ B(N |A )
and B|B ⊆ B(N |B ). Therefore, by induction, each of B|A and B|B is displayed by a binary level-1 network. By
Theorem 2, it follows that B is displayed by a binary level-1 network.
t
u
5 Binets determine the number of reticulations of a binary level-1 network
In this section we show that, that although the collection of binets displayed by a level-1 network does not
necessarily determine the network (see Figure 1), it does in fact determine the number of reticulations in the
network. We begin by showing that it suffices to consider level-1 networks in which all cycles (in the underlying
undirected graph) have length 3.
First, we introduce some further notation. A semi-cycle C of an acyclic directed graph is the union of two
non-identical, internally-vertex-disjoint, directed paths from s to t, with s = s(C) and t = t(C) two distinct
vertices that are referred to as the source and terminal of C, respectively. The length of a semi-cycle is the
number of distinct vertices that it contains.
We now show that we may restrict to networks in which all semi-cycles have length 3.

Binets: fundamental building blocks for phylogenetic networks

9

Ai

Ai

vi

Bi

Ai

vi
x

Bi

(a) The parent of x is not in a semicycle.

vi
x

Bi

(b) The parent of x is the terminal of
a semi-cycle.

x

(c) The parent of x is a non-terminal
non-source vertex of a semi-cycle.

Fig. 6: The three cases for the location of x in each of the networks N1 and N2 in the proof of Theorem 4.
A1
v1

v2
x

B1
N1

A2
v1
x

B2

A1

N2

(a) Case 1: the parent of x is not in
a semi-cycle in N1 but is the terminal of a semi-cycle in N2 .

v2
x

B1
N1

A2

x

B2
N2

(b) Case 2: the parent of x is not
in a semi-cycle in N1 but is the
non-terminal non-source vertex of
a semi-cycle in N2 .

Fig. 7: The two possible ways to add leaf x to N10 and N20 in the proof of Theorem 4 such that the obtained
networks N1 and N2 have different numbers of reticulation vertices.
Lemma 4 If N is a binary level-1 network, then there exists a binary level-1 network N 0 in which every semicycle has length 3, such that B(N 0 ) = B(N ) and N and N 0 have the same number of reticulation vertices.
Proof Consider a semi-cycle of N with source s and terminal t and length at least 4. Let (u1 , v1 ), . . . ,(uk , vk ),
(t, w) be the arcs leaving the semi-cycle. Then k ≥ 2. Let N ∗ be a network obtained from a binary tree
on {v1 , . . . , vk } by replacing vi by the subgraph of N rooted at vi , for i = 1, . . . , k. Let Nw be the subgraph
of N rooted at w. Then we construct N 0 from N by replacing the subgraph of N rooted at s by the network R(N ∗ ; Nw ). It is straightforward to see that N 0 is a binary level-1 network with the required properties.
t
u
We now establish the main result of this section.
Theorem 4 If N1 and N2 are rooted binary level-1 phylogenetic networks on X with B(N1 ) = B(N2 ) then N1
and N2 have the same number of reticulation vertices.
Proof The proof is by induction on the number of leaves |X|. The induction basis for |X| = 2 is clear. Now
suppose that N1 and N2 are two non-isomorphic rooted binary level-1 phylogenetic networks on |X| ≥ 3 with
B(N1 ) = B(N2 ) but with different numbers of reticulation vertices. We add an outdegree-1 root to each of N1
and N2 with an arc to the original root. By Lemma 4, we may assume that all semi-cycles in N1 and N2 have
length 3.
Choose an arbitrary leaf x ∈ X and let X 0 = X \ {x}. Let N10 and N20 be the networks obtained from N1 |X 0
and N2 |X 0 , respectively, by adding an outdegree-1 root with an arc to the original root. Then N10 and N20 have
the same number of reticulation vertices by induction.
Since all semi-cycles in N1 and N2 are assumed to have length 3, there are three cases for the location of x
in each of the networks N1 , N2 , illustrated in Figure 6.
If the parent of x is in a semi-cycle in Ni , let vi be the source of this semi-cycle, and let vi be the parent
of x otherwise. Let Bi := C(vi ) \ {x} and Ai := X 0 \ Bi (recall that C(vi ) denotes the cluster of vi ).
We now consider the different ways in which we could add x to both networks. Since N1 and N2 have
different numbers of reticulation vertices, there are two cases to consider (after eliminating symmetric cases),
as illustrated in Figure 7.
The first case is that the parent of x is not in a semi-cycle in N1 but is the terminal of a semi-cycle in N2 .
First suppose that B1 ∩ B2 6= ∅. Then choose an arbitrary vertex y ∈ B1 ∩ B2 . Then N1 |{x,y} = T (x, y)

10

Leo van Iersel et al.

while N2 |{x,y} = R(y; x), a contradiction. Hence, we may assume that B1 ∩ B2 = ∅. Then B1 = A2 and
B2 = A1 . Clearly, B1 , B2 6= ∅. Take y ∈ B1 = A2 and z ∈ B2 = A1 . Then N1 |{x,y} = T (x, y) and hence
N2 |{x,y} = T (x, y), from which we can deduce that N2 |{z,y} = T (z, y). In addition, N2 |{z,x} = R(z; x) and
hence N1 |{z,x} = R(z; x), from which we can deduce that N1 |{z,y} = R(z; y). This leads to a contradiction
since N2 |{z,y} = T (z, y).
The second case is that the parent of x is not in a semi-cycle in N1 but is the non-terminal non-source
vertex of a semi-cycle in N2 . First suppose that B1 ∩ B2 6= ∅. Then choose an arbitrary vertex y ∈ B1 ∩ B2 .
Then N1 |{x,y} = T (x, y) while N2 |{x,y} = R(x; y), a contradiction. Hence, we may assume that B1 ∩ B2 = ∅.
Then, as in the previous case, B1 = A2 6= ∅ and A1 = B2 6= ∅. Take y ∈ B1 = A2 and z ∈ B2 = A1 . Then,
similar to the previous case, N1 |{x,y} = T (x, y) and hence N2 |{x,y} = T (x, y), from which we can deduce that
N2 |{z,y} = T (z, y). In addition, N2 |{z,x} = R(x; z) and hence N1 |{z,x} = R(x; z), from which we can deduce
that N1 |{z,y} = R(y; z). This again leads to a contradiction since N2 |{z,y} = T (z, y).
t
u
6 Complexity of Binet Compatibility
A direct consequence of Theorem 2 is that there exists a simple polynomial-time algorithm to decide whether
there exists a binary level-1 network displaying a given collection B of binary level-1 binets (see [11] for
a related algorithm). In particular, a sink set of D(B) can be found in polynomial-time by computing the
strongly connected components of D(B) [17] and checking for each of them whether it is a sink set. This can
be used to find a typed split, if it exists. If such a split does not exist, then B is not compatible. Otherwise,
we can try to construct networks for B|A and B|B recursively, and combine them as described in the proof of
Theorem 2. This algorithm is similar to the Aho algorithm for deciding whether a set of rooted trees can be
displayed by some rooted tree [1].
From Theorem 3, it now follows that the following problem can also be solved in polynomial time.
Binet Compatibility (BC)
Input: a set B of binary level-1 binets.
Question: is B compatible, i.e., does there exist a binary network N with B ⊆ B(N )?
We show now that the assumption that all binets in B are binary and level-1 is essential. Indeed, for general
binets, the compatibility problem is at least as hard as the well-known graph isomorphism problem (GI) [8,
18], which is not known to be solvable in polynomial time. This is even true when the given binet set is thin
(contains at most one binet for each pair of leaves).
Theorem 5 Deciding whether there exists a phylogenetic network displaying a given thin set B of binets is
GI-hard.
Proof We reduce from DAG-isomorphism, which is known to be GI-complete [18]. Let G1 , G2 be two directed acyclic graphs, which form an instance of the DAG-isomorphism problem. For i = 1, 2, we add vertices ρi , ui , vi , wi , ri , a new leaf labelled x, an arc from wi to each indegree-0 vertex of Gi and from each
outdegree-0 vertex of Gi to ri and arcs (ρi , ui ), (ui , vi ), (ρi , vi ), (vi , wi ) and (ri , x). In G1 , we add a new leaf
labelled y and an arc (u1 , y). In G2 , we add a new leaf labelled z and an arc (u2 , z). We have thus transformed G1 into a binet B1 and G2 into a binet B2 . The third binet is B3 = T (y, z). See Figure 8 for an
illustration.
We claim that G1 and G2 are isomorphic if and only if there exists a network displaying B1 , B2 and B3 .
First assume that G1 and G2 are isomorphic. Then we can construct a network displaying B1 , B2 and B3
as follows. Take B1 and subdivide the arc (u1 , y) by a new vertex u01 and add leaf z with an arc (u01 , z). The
obtained network clearly displays B1 and B3 and it also displays B2 since G1 and G2 are isomorphic.
Now assume that there exists some network N displaying B1 , B2 and B3 . Then N |{x,y} = B1 . Hence, N
contains a cycle (in the underlying undirected graph) containing a reticulation v, such that x and the image
of G1 are below the arc leaving v, while y is below some other arc leaving the cycle. Since N |{y,z} = T (y, z),
leaf z is not below v in N . Therefore, deleting v, x and the parent of x from the subgraph of N rooted at v
gives G1 .
Similarly, N contains a cycle containing a reticulation v 0 , such that x and the image of G2 are below the
arc leaving v 0 , while z is below some other arc leaving the cycle. Since N |{y,z} = T (y, z), leaf y is not below v 0
in N . Therefore, deleting v 0 , x and the parent of x from the subgraph of N rooted at v 0 gives G2 .
Moreover, v = v 0 since N |{y,z} = T (y, z). Hence, G1 and G2 are isomorphic.
t
u

Binets: fundamental building blocks for phylogenetic networks

y

11

z
z

G1

y

z

y

G1

G2
B3

x

x

x

B1

B2

N

Fig. 8: The three binets constructed in the proof of Theorem 5, and a network N that displays all three binets
if the digraphs G1 and G2 are isomorphic.
7 Maximum Binet Compatibility
If a collection of binets is not compatible, the question arises whether it is possible to find a largest compatible
subset of the binets, in polynomial time. Here we show that this is unlikely to be the case. The decision version
of this problem is defined as follows.
Maximum Binet Compatibility (MBC)
Input: a set B of binary level-1 binets and an integer k.
Question: does there exist a compatible subset B 0 of B with |B 0 | ≥ k?
We now establish the complexity of this problem (see Theorem 6). Recall from Section 5 that s(C) and t(C)
denote the source and terminal of a semi-cycle C, respectively.
Lemma 5 If the binet R(x; y) is displayed by a binary level-1 network N , then lsa(x, y) is the source of a
semi-cycle C in N . In addition, y is below t(C) and x is not below t(C).
Proof Let u = lsa(x, y). Note that u is not a reticulation vertex, as otherwise the child of u would be a stable
ancestor of x and y that is below u. Hence, u has two children, denoted by u1 and u2 .
Observe that neither (u, u1 ) nor (u, u2 ) is a cut arc, since otherwise we would have N |{x,y} = T (x, y), while
by the assumption of the lemma N |{x,y} = R(x; y). Hence, u is the source of a semi-cycle C. Let v := t(C) be
the terminal of C. If neither x nor y is below v, then N |{x,y} = T (x, y), a contradiction. If both x and y are
below v, then v is a stable ancestor of x and y, a contradiction to lsa(x, y) = u. Therefore, precisely one of x
and y is below v. If x is below v and y is not, then N |{x,y} = R(y; x), a contradiction. Therefore, y is below v
and x is not.
t
u
In view of the last lemma, for each binet R(x; y) = N |{x,y} , there exists a unique semi-cycle CN (x; y)
containing lsa(x, y).
Lemma 6 If the two binets R(x; y) and R(y; z) are both displayed by a binary level-1 network N , then
s(CN (y; z)) ≺ t(CN (x; y)).
Proof Let C1 = CN (x; y) and C2 = CN (y; z). By Lemma 5, y ≺ t(C1 ) but y is not below t(C2 ), from which
we know that C1 6= C2 . Since s(C1 ) and s(C2 ) are stable ancestors of y in view of Lemma 5, we have either
s(C1 ) ≺ s(C2 ) or s(C2 ) ≺ s(C1 ) but not both.
Note that if s(C1 ) ≺ s(C2 ), then s(C1 ) ≺ t(C2 ) and hence y ≺ s(C1 ) ≺ t(C2 ), a contradiction. Thus
s(C2 ) ≺ s(C1 ), from which it follows that s(C2 ) ≺ t(C1 ).
t
u
Given a digraph G, let R(G) be the collection of binets {R(x; y) | (x, y) ∈ E(G)} induced by G. Note that
R(G) is a binet set on V (G), i.e., the leaves of the binets in R(G) correspond to the vertices of G.
Proposition 1 Let G be a digraph. Then G is acyclic if and only if R(G) is compatible.

12

Leo van Iersel et al.

xn

xn−1

xn−2

x1

Fig. 9: A level-1 network N∗ on X = {x1 , . . . , xn }.
Proof Let n = |X|, with X the vertex set of G. Suppose first that G is acyclic, then there exists a topological
sorting of G, that is, the vertices of G can be ordered as x1 , . . . , xn so that (xi , xj ) ∈ E(G) implies i < j.
Hence, the network N∗ in Figure 9 displays R(G) since N∗ displays each binet R(xi ; xj ) with i < j.
Conversely, suppose that R(G) is compatible. By Theorem 3, there exists a binary level-1 network N with
R(G) ⊆ B(N ). It remains to show that G is acyclic. If not, then there exists a directed cycle (x1 , x2 , . . . , xm )
for some m ≥ 3. Denote xm+1 = x1 . In view of Lemma 5, let Ci = CN (xi ; xi+1 ) be the semi-cycle in N
containing lsa(xi , xi+1 ) for 1 ≤ i ≤ m. Then Lemma 5 implies x1 ≺ s(Cm ) and that x1 is not below t(C1 ).
On the other hand, by Lemma 6 we have
s(Cm ) ≺ t(Cm−1 ) ≺ s(Cm−1 ) ≺ . . . ≺ s(C2 ) ≺ t(C1 ).
Together with x1 ≺ s(Cm ), it follows that x1 ≺ t(C1 ), a contradiction.

t
u

A set of binets B on X is said to be dense if for each pair of distinct elements x and y in X, there exists
precisely one binet on {x, y} in B. Hence, a dense set of binets is always thin.
Theorem 6 The problem MBC is NP-complete, even if the given set of binets is dense.
Proof We reduce from the NP-hard problem Feedback Arc Set in Tournaments (FAST) [2, 6], which is defined
as follows. Given a tournament, i.e. a digraph G = (V, E) with either (a, b) ∈ E or (b, a) ∈ E (but not both)
for each pair of distinct elements a and b in V , and given a positive integer k 0 , does there exist a subset F ⊆ E
of at most k 0 arcs whose removal makes G acyclic. If such an arc set exists, then we call it a feedback arc set
of G.
The reduction is as follows. For each instance (G, k 0 ) of FAST, consider the corresponding instance (R(G), k)
of MBC with k = |R(G)| − k 0 . Since the set R(G) of binets induced by G can be constructed in polynomial
time, it suffices to show that G contains a feedback arc set with size at most k 0 if and only if there exists a
compatible subset of R(G) of size at least k.
First assume that there exists a feedback arc set E 0 of G with size at most k 0 . That is, |E 0 | ≤ k 0 , and the
digraph G∗ obtained from G by deleting the arcs in E 0 is acyclic. Consider the set of binets B 0 = {R(x; y) :
(x, y) ∈ E \ E 0 }. This set contains at least k binets. In addition, since B 0 = R(G∗ ), it follows by Proposition 1
that B 0 is compatible.
Now assume that there exists a compatible binet set B 0 ⊆ R(G) with |B 0 | ≥ k. Consider the set E 0 =
{(x, y) : R(x, y) ∈ R(G) \ B 0 } of arcs of G. Then by Proposition 1, it follows that E 0 is a feedback arc set.
Moreover, |E 0 | ≤ k 0 , which completes the proof.
t
u
We complete the section by showing that there exists a polynomial time 1/3-approximation algorithm for
the MBC problem, which follows directly from the next theorem and its proof.
Theorem 7 Suppose that B is a set of binary level-1 binets on X. Then there exists a binary level-1 network
N such that |B(N ) ∩ B| ≥ |B|/3.
Proof If at least a third of the binets in B are tree type, then take N to be any binary tree on X and we are
done. Hence we may assume that at least two thirds of the binets are reticulate type.
Impose an arbitrary ordering on the elements in X, that is, write X = {x1 , . . . , xn }. Let B1 = B ∩
{R(xi ; xj ) : 1 ≤ i < j ≤ n} and B2 = B ∩ {R(xj ; xi ) : 1 ≤ i < j ≤ n}. Without loss of generality, we may

Binets: fundamental building blocks for phylogenetic networks

13

assume that |B1 | ≥ |B2 | (as the other case can be established in a similar way). Since at least two thirds of
the binets are reticulate type, and each of those is contained in either B1 or B2 (but not both), we know that
|B1 | ≥ |B|/3. Now consider the network N∗ in Figure 9, then clearly we have B1 ⊆ B(N∗ ). Thus we have
|B(N∗ ) ∩ B| ≥ |B1 | ≥ |B|/3, from which the theorem follows.
t
u
8 Discussion
In this paper we have developed some combinatorial results concerning collections of level-1 binets. Several
interesting questions arise from these results. For example, we have shown that the collection of level-1 binets
displayed by a binary phylogenetic network can be displayed by some level-1 network, but is there some
canonical level-1 network that could be used to display such a collection? In addition, can we count the
number of binary level-1 networks that display a dense compatible collection of binets? We have also seen that
the collection of binets displayed by a binary level-1 network determine its reticulation number. Therefore it
is natural to ask which properties of a phylogenetic network in general are determined by its binets?
We have also studied some algorithmic questions concerning binets. Concerning the maximum binet compatibilty problem, note that the constant 1/3 is sharp in Theorem 7. For example, consider the binet collection
{R(x; y), T (x, y), R(y; x)}. However, can a better bound be achieved by restricting to thin collections of binets,
and can improved approximation algorithms also be found?
In another direction, it would be interesting to know whether similar results to those proven in this paper
might hold for higher level networks. For example, what can be said about properties of collections of level-2
binets, and does Theorem 4 hold also for higher level networks? Also, we could try to generalize some of our
results to k-nets, i.e. networks on k leaves, k ≥ 2. For example, does Theorem 3 hold for trinets? In general,
it would be interesting to know what additional information the collection of k-nets displayed by a network
might contain for k ≥ 3. Note that it has been shown that trinets do not completely determine rooted networks
in general [12]. However, do they determine properties of networks such as the number of reticulations?
Similarly, it would be interesting to extend some of our algorithmic results to higher-level networks and
k-nets. For example, it is known that the compatibility problem is NP-complete for collections of level-1 trinets
[11]. However, to date the maximum trinet compatibility problem has not been studied.
Eventually, it is hoped that new results in these directions could be useful for developing novel methods
to construct phylogenetic networks from higher-level networks and k-nets. For example, using our results it
may be possible to develop approaches to build a consensus network for a collection of phylogenetic trees
or networks. Note that consensus networks have already proven themselves useful in the unrooted setting,
where they are used to summarize key features displayed by a collection of trees or networks (see e.g. [10]). A
consensus method based on binets could work by breaking each of the given networks down into a collection of
binets, and then developing methods to pool together the information contained in the resulting binets so as
to construct some consensus network, or at least some constraints that any such network should satisfy. Note
that similar approaches have been developed to build consensus trees for a collection of phylogenetic trees by
breaking each of the trees down into a collection of triplets (see e.g. [4, Section 2]). Probably it would be of
some interest to first consider how to construct a level-1 consensus network for a collection of level-1 networks
by breaking each of them down into level-1 binets. This is already likely to be quite challenging in view of our
result concerning NP-completeness of Maximum Binet Compatibility.
References
1. Aho, A.V., Sagiv, Y., Szymanski, T.G., Ullman, J.D.: Inferring a tree from lowest common ancestors with an application to
the optimization of relational expressions. SIAM Journal on Computing 10(3), 405–421 (1981)
2. Alon, N.: Ranking tournaments. SIAM Journal on Discrete Mathematics 20(1), 137–142 (2006)
3. Bapteste, E., van Iersel, L.J.J., Janke, A., Kelchner, S., Kelk, S., McInerney, J.O., Morrison, D.A., Nakhleh, L., Steel, M.,
Stougie, L., Whitfield, J.: Networks: expanding evolutionary thinking. Trends in Genetics 29(8), 439–441 (2013)
4. Bryant, D.: A classification of consensus methods for phylogenetics. DIMACS series in discrete mathematics and theoretical
computer science 61, 163–184 (2003)
5. Byrka, J., Guillemot, S., Jansson, J.: New results on optimizing rooted triplets consistency. Discrete Applied Mathematics
158(11), 1136–1147 (2010)
6. Charbit, P., Thomassé, S., Yeo, A.: The minimum feedback arc set problem is NP-hard for tournaments. Combinatorics,
Probability and Computing 16(01), 1–4 (2007)
7. Felsenstein, J.: Inferring phylogenies. Sinauer Associates Sunderland (2004)
8. Goldberg, M.: The graph isomorphism problem. In: J.L. Gross, J. Yellen (eds.) Handbook of Graph Theory, pp. 68–78. CRC
Press (2003)
9. Gusfield, D.: ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks.
MIT Press (2014)

14

Leo van Iersel et al.

10. Holland, B., Huber, K., Moulton, V., Lockhart, P.: Using consensus networks to visualize contradictory evidence for species
phylogeny. Molecular Biology and Evolution 21(7), 1459–1461 (2004)
11. Huber, K., van Iersel, L.J.J., Moulton, V., Scornavacca, C., Wu, T.: Reconstructing phylogenetic level-1 networks from
nondense binet and trinet sets. Algorithmica (2015). DOI 10.1007/s00453-015-0069-8
12. Huber, K., van Iersel, L.J.J., Moulton, V., Wu, T.: How much information is needed to infer reticulate evolutionary histories?
Systematic biology 64, 102–111 (2015)
13. Huber, K., Moulton, V., Wu, T.: Closed sets in phylogenetic networks. Preprint (2016)
14. Huson, D., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University
Press (2010)
15. Morrison, D.: An introduction to phylogenetic networks. RJR Productions (2011)
16. Oldman, J., Wu, T., van Iersel, L.J.J., Moulton, V.: Trilonet: Piecing together small networks to reconstruct reticulate
evolutionary histories. Molecular biology and evolution 33(8), 2151–2162 (2016)
17. Tarjan, R.: Depth-first search and linear graph algorithms. SIAM journal on computing 1(2), 146–160 (1972)
18. Zemlyachenko, V.N., Korneenko, N.M., Tyshkevich, R.I.: Graph isomorphism problem. Journal of Soviet Mathematics 29(4),
1426–1481 (1985)

