Deciding the existence of a cherry-picking sequence is hard on
two trees
Janosch Döcker1 , Leo van Iersel2 , Steven Kelk3 , Simone Linz4

arXiv:1712.02965v1 [q-bio.PE] 8 Dec 2017

1

Department of Computer Science, University of Tübingen, Germany
janosch.doecker@uni-tuebingen.de
2
Delft Institute of Applied Mathematics, Delft University of Technology
PO-box 5031, 2600 GA Delft, The Netherlands
L.J.J.vanIersel@tudelft.nl
3
Department of Data Science and Knowledge Engineering (DKE),
Maastricht University, The Netherlands,
steven.kelk@maastrichtuniversity.nl
4
Department of Computer Science, University of Auckland, New Zealand,
s.linz@auckland.ac.nz

Abstract. Here we show that deciding whether two rooted binary phylogenetic trees on the
same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa,
is NP-complete. This improves on an earlier result which proved hardness for eight or more trees.
Via a known equivalence between cherry-picking sequences and temporal phylogenetic networks,
our result proves that it is NP-complete to determine the existence of a temporal phylogenetic
network that contains topological embeddings of both trees. The hardness result also greatly
strengthens previous inapproximability results for the minimum temporal-hybridization number
problem. This is the optimization version of the problem where we wish to construct a temporal
phylogenetic network that topologically embeds two given rooted binary phylogenetic trees and
that has a minimum number of indegree-2 nodes, which represent events such as hybridization
and horizontal gene transfer. We end on a positive note, pointing out that fixed parameter
tractability results in this area are likely to ensure the continued relevance of the temporal
phylogenetic network model.

Keywords: phylogenetics, NP-hardness, satisfiability, phylogenetic networks, elimination
orders.

1

Introduction

In the field of phylogenetics it is common to represent the evolution of a set of species X by
a rooted phylogenetic tree; essentially a rooted, bifurcating tree whose leaves are bijectively
labeled by X [19]. Driven by the realization that evolution is not always treelike there has
been growing attention for the construction of phylogenetic networks, which generalize phylogenetic trees to directed acyclic graphs [1,11,14,20]. One well known optimization problem
for phylogenetic networks is as follows: given a set of rooted phylogenetic trees T on the same
set of taxa X, compute a phylogenetic network N = (V, E) which displays (i.e. contains topological embeddings of) all the trees in T , such that the reticulation number |E| − (|V | − 1) is
minimized. When N is restricted to being binary this is equivalent to minimizing the number
of nodes of N with indegree-2. This optimization model is known as minimum hybridization
and it has been extensively studied in the last decade (see e.g. [2,6,16,22,24]). More recently
variations of minimum hybridization have been proposed which constrain the topology of N
to be more biologically relevant. One such constraint is to demand that N is temporal [17].
Informally, a phylogenetic network N is temporal if (i) the nodes of N can be labeled with

times, such that nodes of indegree-2 have contemporaneous parents, and time moves strictly
forwards along treelike parts of the network; and (ii) each non-leaf vertex has a child whose
indegree is 1. Property (ii) by itself is referred to as tree-child in the literature [5]. It has been
shown that when |T | = 2 it is NP-hard to solve the minimum temporal-hybridization number
problem to optimality [13]. To establish the result, the authors proved that the problem is in
fact APX-hard, which implies that for some constant c > 1 it is not possible in polynomial
time to approximate the optimum within a factor of c, unless P=NP [18].
A more fundamental question remained, however, open: is it possible in polynomial time to
determine if any temporal phylogenetic network exists that displays the input trees, regardless
of how large |E| − (|V | − 1) is [12,21]? Here we settle this question by showing that, even
for |T | = 2, it is NP-complete to determine whether such a network exists. We prove this
by using the cherry-picking characterization of temporal phylogenetic networks introduced in
[12]. There it was shown that, given an arbitrarily large set T of rooted binary phylogenetic
trees on X, there exists a temporal phylogenetic network that displays each tree in T precisely
if T has a so-called cherry-picking sequence. Informally, a cherry-picking sequence on T is
an elimination order on X that deletes one element of X at a time, where at each step only
elements can be deleted which are in a cherry of every tree in T [12]. We show here that the
seminal NP-hard problem 3-SAT [15] can be reduced to the question of whether two trees
permit a cherry-picking sequence. This improves upon a recent result by two of the present
authors which shows that, for |T | ≥ 8, it is NP-complete to determine whether T has a
cherry-picking sequence [8]. Our hardness result is highly non-trivial and requires extensive
gadgetry; to clarify we include an explicit example of the construction after the main proof.
As we discuss in the final section of the paper, this result has quite significant negative consequences: given that the decision problem is already hard, the minimum temporalhybridization number problem is in some sense “effectively inapproximable”, even for two
trees. This greatly strengthens the earlier APX-hard inapproximability result. Nevertheless, as
we subsequently point out, positive fixed parameter tractability (FPT) [7] results for the minimum temporal-hybridization number problem do already exist [12] and our results emphasize
the importance of further developing such algorithms, since fixed parameter tractability forms
the most promising remaining avenue towards practical exact methods.

2

Preliminaries

A rooted binary phylogenetic tree on a set of taxa X, where |X| ≥ 2, is a rooted, connected,
directed tree with a unique root (a vertex of indegree-0 and outdegree-2), where the leaves
(vertices with indegree-1 and outdegree-0) are bijectively labeled by X, and where all interior
vertices of the tree are indegree-1 and outdegree-2. If |X| = 1, we consider the single isolated
node labeled by the unique element of X, to also be a rooted binary phylogenetic tree. Since
all phylogenetic trees considered in this paper are rooted and binary, we henceforth write tree
for brevity, and draw no distinction between the elements of X and the leaves they label. Let
T be a tree, and let T = {T1 , T2 , . . . , Tm } be a set of trees. We use X(T ) to denote the taxa
set of T and, similarly, we use X(T ) to denote the union of taxa sets over all elements in T ,
i.e. X(T ) = X(T1 ) ∪ X(T2 ) ∪ . . . ∪ X(Tm ). Lastly, for two distinct elements x and y in X, we
call {x, y} a cherry of T if they have the same parent. A tree with a single cherry is referred
to as a caterpillar.
Now, let T be a tree on X, and let X 0 = {x1 , x2 , . . . , xk } be an arbitrary set. We write T |X 0
to denote the tree obtained from T by taking the minimum subtree spanning the elements of

a

b c

d

e

a

b c

d

e

a

b c

d

f

g

c

a f

b

g

d

e

g

c

a

b

g

d

e

e

c

a

b

d

e

Fig. 1. A cherry-picking sequence for the two trees T and T 0 at the top is (f, g, d, b, a, c, e). The two trees in
the middle have been obtained from T and T 0 , respectively, by pruning f , and the two trees at the bottom
have been obtained from T and T 0 by first pruning f and, subsequently, pruning g. While we can alternatively
prune a and, subsequently, b, from T and T 0 , note that no cherry-picking sequence exists for T and T 0 whose
first two elements are a and b.

X 0 and repeatedly suppressing all vertices with indegree-1 and outdegree-1. Furthermore, we
also write T [−x1 , x2 , . . . , xk ] or T [−X 0 ] for short to denote T |(X − X 0 ). If X ∩ X 0 = ∅, then
T |X 0 is the null tree and T [−X 0 ] is T itself. For a set T = {T1 , T2 , . . . , Tm } of trees on subsets
of X, we write T |X 0 (resp. T [−X 0 ]) when referring to the set {T1 |X 0 , T2 |X 0 , . . . , Tm |X 0 }
(resp. {T1 [−X 0 ], T2 [−X 0 ], . . . , Tm [−X 0 ]}). Lastly, a rooted binary phylogenetic tree is pendant
in T if it can be detached from T by deleting a single edge.
2.1

Cherry-picking sequence problem on trees with the same set of taxa

We say that a taxon x ∈ X is in a cherry of T if there exists some y 6= x such that {x, y} is
a cherry of T or T consists of a single leaf x. If x is in a cherry of T , we say that x is picked
(or pruned ) from T to denote the operation of replacing T with T [−x]. Given a set of trees
T , all on the same set of taxa X, we say that a taxon x ∈ X is available (for picking) in T if
x is in a cherry in each tree in T . When this is the case, we say that x is picked (or pruned )
from T to denote the operation of replacing T with T [−x].
Let T be a set of trees on the same set of taxa X. A cherry-picking sequence is an
order on X, say (x1 , x2 , . . . , x|X| ), such that each xi with i ∈ {1, 2, . . . , |X|} is available in
T [−x1 , x2 , . . . , xi−1 ]. Such a sequence is not guaranteed to exist; if it does, we say that T
permits a cherry-picking sequence. It was shown in [8] that deciding whether such a sequence
exists is NP-complete if |T | ≥ 8. Note that, if |T | = 1, then T always has a cherry-picking
sequence. To illustrate, a cherry-picking sequence for the two trees that are shown at the top
of Figure 1 is (f, g, d, b, a, c, e).
2.2

A more general cherry-picking sequence problem

Let T be a set of trees, and let X = X(T ). Suppose we consider the variant of the problem
described in Section 2.1 in which the trees in T do not necessarily have the same set of taxa.

In this case, some taxa may be missing from some trees. This requires us to generalize the
concept of being in a cherry of a tree. We say that a taxon x is in a cherry of a tree T , if
exactly one of the following conditions holds:
1. x 6∈ X(T ) or
2. x ∈ X(T ) and x is in a cherry of T ,
(Note that, once again, this means that if x is the only taxon in T , then x is vacuously
considered to be in a cherry of T .) It initially seems counter-intuitive to say, when condition
1 applies, that x is “in” a cherry of T . However, the idea behind this is that such trees do not
constrain whether x can be picked; they “do not care”. More formally, we say that a taxon x is
available in T if it is in a cherry in each tree in T . Similar to Section 2.1, we say that an order
on X, say (x1 , x2 . . . , x|X| ) is a cherry-picking sequence of T if each xi with i ∈ {1, 2, . . . , |X|}
is available in T [−x1 , x2 , . . . , xi−1 ]. If a tree becomes the null tree due to all its taxa being
pruned away then this tree plays no further role. Moreover we note that, if all trees in T have
the same set of taxa, then the more general definition of a cherry-picking sequence given in
this subsection and that will be used throughout the rest of this paper coincides with that
given in Section 2.1.

3

Main results

In this section, we establish the main result of this paper. We start with two lemmas.
Lemma 1. Let T be a set of m trees on not necessarily the same set of taxa. Then we can
construct in polynomial time a set T 0 of m trees all on the same set of taxa, such that T has
a cherry-picking sequence if and only if T 0 does.
Proof. Let X = X(T ), and let Y = {y1 , y2 , . . .} be the set of taxa that are missing from at
least one input tree. Let Y 0 = {y10 , y20 , ...} be a disjoint copy of this set. Every modified tree
will have taxon set X ∪ Y 0 ∪ {ρ}. The idea is as follows. Let TY 0 be an arbitary rooted binary
tree on Y 0 . For each input tree Ti , we start by joining Ti and ρ beneath a root, and then join
this new tree and TY 0 together beneath a root. Next, for each yj ∈ Y that is missing from
Ti , we add yj by subdividing the edge that feeds into yj0 and attaching yj there (so yj and yj0
become siblings). For an example, see Figure 2. We call the set of trees constructed in this
way T 0 . The high-level idea is that if a tree Ti does not contain some taxon x, we attach x
just above x0 and thus ensure that, trivially, x is in a cherry in that tree (i.e. together with
x0 ). So Ti does “not care” about x and will not obstruct it from being pruned.
First, assume that T has a cherry-picking sequence σ. (We show that T 0 has a cherrypicking sequence). We start by applying exactly the same sequence of pruning operations to
T 0 . These picking operations will always be possible because, if a taxon y ∈ Y is missing from
a tree Ti ∈ T , it will be in a cherry together with y 0 in the corresponding tree of T 0 . After
doing this, all the trees will be isomorphic and have the same set of taxa: Y 0 ∪ {ρ}. At this
point these remaining taxa can be pruned in bottom-up fashion (since two isomorphic trees
always have a cherry-picking sequence). Hence T 0 has a cherry-picking sequence. Note that
the taxon ρ is included to ensure that if, during σ, a tree Ti has been pruned down to a single
taxon, this taxon can still be pruned in the corresponding tree of T 0 (because it is sibling to
ρ).

a0
ρ
a

b

d

c and f are missing

e0
a

b

d

ρ

d

c0

f

c

d

a and e are missing

b

a0

a

c

e

ρ

d

a, c and f are missing

f0

e0

e

a0

a

b

f0

f

e

f
b

c0

c

e

c

c0
e0

b

e

d

f

f0

Fig. 2. The construction described in Lemma 1. Here Y , the set of taxa missing from at least one tree, is
{a, c, e, f }. In each modified tree the artificially added members of Y are circled; note that they are always
in cherries. A cherry-picking sequence for the original trees is e, b, c, d, a, f . A corresponding sequence for the
modified trees is e, b, c, d, a, f, f 0 , e0 , c0 , a0 , ρ.

In the other direction, let σ 0 be a cherry-picking sequence for T 0 . Let σ be the sequence
obtained by deleting all taxa from σ 0 that are not in X. Let x be an arbitrary element of
X and let i be the position of x in σ 0 . Let `01 , `02 , . . . , `0i−1 be the prefix of σ 0 that has been
pruned from T 0 prior to x, and let `1 , `2 , . . . , `j (where j ≤ i − 1) be the prefix of σ that has
been pruned prior to x. We claim that, if x is available in T 0 [−`01 , `02 , . . . , `0i−1 ], then it is also
available in T [−`1 , `2 , . . . , `j ]. To see this, let T be an arbitrary tree in T [−`1 , `2 , . . . , `j ]. If
x 6∈ X(T ), then (by definition) x is in a cherry of T . If x is the only taxon in T , then it is (also
by definition) in a cherry. So the only case remaining is that x ∈ X(T ) and |X(T )| ≥ 2. Let
T 0 be the tree from T 0 [−`01 , `02 , . . . , `0i−1 ] that corresponds to T . The critical observation here
is that, by construction, T occurs as a pendant subtree of T 0 . So if x was not in a cherry of
T , it would not be in a cherry of T 0 (which violates the assumption). Hence, x is in a cherry
of T . Due to the arbitrary choice of x and T , it follows that σ is a cherry-picking sequence
for T .
It remains to show that the reduction is polynomial time. Observe that, depending on the
instance, the size of T can be dominated by |X| or m. Each of the m trees in T 0 contains
|X| + |Y | + 1 taxa, where |Y | ≤ |X|, and the transformation itself involves straightforward
operations, so overall the reduction takes poly(|X|, m) time.
t
u
Let T be a set of rooted binary trees, and let Ti and Tj be two trees in T such that
X(Ti ) ∩ X(Tj ) = ∅. Furthermore, let ρi and ρj be the root vertex of Ti and Tj , respectively.
Obtain a new tree from Ti and Tj in the following way.
1. Create a new vertex ρ and add new edges e = (ρ, ρi ) and e0 = (ρ, ρj ).
2. Subdivide e (resp. e0 ) with a new vertex v (resp. v 0 ) and add a new edge (v, x) (resp.
(v, y)), where x and y are two new taxa such that {x, y} ∩ X(T ) = ∅.
We call the resulting rooted binary tree the compound tree of Ti and Tj . To illustrate, Figure 3
depicts the compound tree of Ti and Tj .

x

Ti

y

Tj

Fig. 3. The compound tree of two rooted binary trees Ti and Tj . The taxon x (respectively, y) simply ensures
that the last taxon pruned away in the Ti (respectively, Tj ) part is in a cherry.

The next lemma shows that, for a set T of rooted binary trees, the replacement of two trees
in T with their compound tree preserves the existence and non-existence of a cherry-picking
sequences for T .

Lemma 2. Let T be a set of rooted binary trees, and let Ti and Tj be two trees in T such that
X(Ti ) ∩ X(Tj ) = ∅. Let Ti,j be the compound tree of Ti and Tj . Then T has a cherry-picking
sequence if and only if (T − {Ti , Tj }) ∪ {Ti,j } has a cherry-picking sequence.
Proof. To ease reading, let T 0 = (T − {Ti , Tj }) ∪ {Ti,j }. Furthermore, let |X(T )| = n, and let
x and y be the unique two taxa in X(Ti,j ) that do not label a leaf in Ti or Tj .
Suppose that σ = (`1 , `2 , . . . , `n ) is a cherry-picking sequence for T . Let i0 be the maximum
index of an element in σ such that `i0 ∈ X(Ti ) and, similarly, let j 0 be the maximum index of
an element in σ such that `j 0 ∈ X(Tj ). Then T [−`1 , `2 , . . . `i0 −1 ] contains a tree that is a single
vertex labeled `i0 and T [−`1 , `2 , . . . `j 0 −1 ] contains a tree that is a single vertex labeled `j 0 .
Moreover, by the construction of Ti,j , the set T 0 [−`1 , `2 , . . . `i0 −1 ] contains a tree with cherry
{`i0 , x} and the set T 0 [−`1 , `2 , . . . `j 0 −1 ] contains a tree with cherry {`j 0 , y}. Since Ti and Tj
are pendant subtrees in Ti,j and σ is a cherry-picking sequence for T , it now follows that
(`1 , `2 , . . . , `n , x, y)
is a cherry-picking sequence for T 0 .
Conversely, suppose that σ 0 = (`1 , `2 , . . . , `n+2 ) is a cherry-picking sequence for T 0 . Let
{`i0 , `j 0 } = {x, y}. Without loss of generality, we may assume that i0 < j 0 . Then, as x and y
are only contained in the leaf set of Ti,j , it is straightforward to check that
(`1 , `2 , . . . , `i0 −1 , `i0 +1 , `i0 +2 , . . . , `j 0 −1 , `j 0 +1 , `j 0 +2 , . . . , `n+2 )
is a cherry-picking sequence for T .

t
u

Now we establish the main result of this paper.
Theorem 1. It is NP-complete to decide if two rooted binary phylogenetic trees T and T 0 on
X have a cherry-picking sequence.
Proof. Given an order σ = (x1 , x2 , . . . , x|X| ) on X, we can decide in polynomial time if, for
each i ∈ {1, 2, . . . , |X|}, xi is in a cherry in T [−x1 , x2 , . . . , xi−1 ] and T 0 [−x1 , x2 , . . . , xi−1 ].
Hence, the problem of deciding if T and T 0 have a cherry-picking sequence is in NP. To
establish the theorem, we use a reduction from 3-Sat. This is the variant of Satisfiability
where each clause contains exactly three literals, and the logical expression is in conjunctive
normal form, i.e.,
m
m
^
^
Ci =
(li,1 ∨ li,2 ∨ li,3 ),
i=1

where li,j ∈

{v (k) , ¬v (k)

i=1

| 1 ≤ k ≤ n}. The corresponding set of variables is denoted with
V := {v (1) , v (2) , . . . , v (n) }.

We reduce from the NP-complete version of 3-Sat in which no variable occurs more than once
in a given clause. Such restricted instances can easily be obtained by a standard transformation
as described in [10]. In the remainder of this proof, n and m refer to the number of variables
and clauses in a restricted 3-Sat instance, respectively.
Now, given an instance I of 3-Sat, we first construct a set T of 3n + 5m + 2 trees with
overlapping taxa sets and show that I has a satisfying truth assignment if and only if T has a

Tv0

Tv
(k)

vT

(k)

vF

b2k−1 b2k

(k)

vT

(k)

b2(n+k)−1 vp1

(k)

(k)

vp|φk | vF

b2(n+k)

(k)

¬vq1

(k)

¬vq|νk |

Fig. 4. Each variable v (k) , is represented by a single tree in Tv and two trees in Tv0 .

cherry-picking sequence. We then repeatedly apply Lemma 2 in order to replace T with two
trees and, finally, apply Lemma 1 to complete the proof of this theorem.
We start by describing the construction of T that makes use of the introduction of a set
{b1 , b2 , . . . , b4n+3m , bX , bY , bZ } of blocking taxa. As we will see later, each such taxon can only
be pruned from T after certain other taxa have been pruned first and so the main function
of the blocking taxa is to be unavailable for pruning which in turn constraints the number
of possibilities to construct a cherry-picking sequence from T . An explicit example of the
construction of T is given subsequently to this proof.
Variable gadget. We construct two sets Tv and Tv0 of trees. Each variable v (k) with k ∈
{1, 2, . . . , n} adds one tree on four taxa to Tv which is the tree shown in the solid box of
Figure 4. Each such tree has two blocking taxa and, intuitively, encodes whether v (k) is set
(k)
(k)
to be true or false, depending on whether vT or vF is pruned first. Moreover, each variable
v (k) adds two caterpillars to Tv0 . Relative to a fixed v (k) , the precise construction of these
caterpillars is based on the definition of two particular tuples. Let φk := (p1 , p2 , . . . , p|φk | )
(resp. νk := (q1 , q2 , . . . , q|νk | )) be the tuple of all indices in ascending order that are elements
in {1, 2, . . . , m} and that index clauses in which v (k) appears unnegated (resp. negated). Since
no clause contains any variable more than once, the elements in φk (resp. νk ) are pairwise
distinct.
(k)
Now the taxon set of one caterpillar contains vT , a new blocking taxon and, for each
(k)
element pj in φk , a new taxon vpj , while the taxon set of the other caterpillar contains
(k)

(k)

vF , a new blocking taxon and, for each element qj in νk , a new taxon ¬vqj . The precise
ordering of the leaves in both caterpillars is shown in the dashed box of Figure 4. It is easily
checked that |X(Tv )| = 4n and, since each clause contains precisely three distinct variables,
|X(Tv0 )| = 4n + 3m. Noting that the taxa sets of the trees in X(Tv ) and X(Tv0 ) only overlap
(k)
(k)
in vT and vF , we have
|X(Tv ∪ Tv0 )| = 4n + 4n + 3m − 2n = 6n + 3m

(1)

distinct taxa over all trees in Tv and Tv0 .
Clause gadget. We construct two sets Tc and Tc0 of trees. For each i ∈ {1, 2, . . . , m},
consider the clause Ci = `(p) ∨ `(q) ∨ `(r) , where each k ∈ {p, q, r} is an element in {1, 2, . . . , n}
with `(k) ∈ {v (k) , ¬v (k) }. Relative to Ci , we add three three-taxon trees to Tc which are shown
(p)
(p)
in the solid box of Figure 5. The first such tree has taxon set {`i , ci1 , ∪ia } where `i is an

Tc
(p)

ci1

`i

(q)

∪ia

`i

ci2

(r)

∪ib

∪ic

ci3

`i

Tc0
ci1

ci2

ci3 b4n+3i−2 b4n+3i−1

b4n+3i

∪ia

∪ib

∪ic

∪i

Fig. 5. Each clause Ci is represented by three trees in Tc and two trees in Tc0 .
(p)

(p)

(p)

element in {vi , ¬vi }. Note that `i labels a leaf of a tree in Tv0 while the other two taxa do
not label a leaf of a tree in Tv or Tv0 . The other two trees in Tc are constructed in an analogous
way. Furthermore, for each Ci , we add two five-taxon trees to Tc0 which are shown in the
dashed box of Figure 5. The taxa set of the first tree contains two new blocking taxa and
the three previously encountered elements {ci1 , ci2 , ci3 }, while the second tree contains one new
blocking taxon, the new taxon ∪i , and the three previously encountered elements {∪ia , ∪ib ∪ic }.
Similar to the variable gadgets, we now count the number of taxa in trees in Tc and Tc0 . As
no two trees in Tc or Tc0 share a taxon, we have |X(Tc )| = 9m and |X(Tc0 )| = 10m. Moreover,
since all taxa of trees in Tc0 , except for the blocking taxa and elements in {∪1 , ∪2 , . . . , ∪m },
are also taxa of trees in Tc , we have
|X(Tc ∪ Tc0 )| = 9m + 10m − 6m = 13m.

(2)

Formula gadget. We complete the construction of T by constructing two caterpillars Tf
and Tf0 which are shown in the solid and dashed box of Figure 6, and define
T = Tv ∪ Tv0 ∪ Tc ∪ Tc0 ∪ {Tf , Tf0 }.
Summarizing the construction, we have |T | = 3n + 5m + 2. Moreover, by construction and
Equations (1)-(2), it follows that |X((Tv ∪ Tv0 ) ∩ (Tc ∪ Tc0 ))| = 3m. Now, since the three taxa
bX , bY , and bZ , which are common to Tf and Tf0 , are the only taxa of these two trees that
are not contained in the taxa set of any other constructed tree, we have
|X(T )| = 6n + 3m + 13m − 3m + 3 = 6n + 13m + 3.

(3)

We next prove the following claim:
Claim 1. I is satisfiable if and only if T has a cherry-picking sequence.
First, suppose that I is satisfiable. Let β : V → {T, F } be a truth assignment for V such
that each clause is satisfied. We next describe a sequence of pruning operation. Noting that

n := number of variables, m := number of clauses

Tf
Tf0

bZ

∪1

∪m

b4n+3m b4n+3m−1

b2n+1

bX

bY

bX

bY

b2n

b2n−1

b1

Fig. 6. The two trees Tf and Tf0 in the construction of T from I.

each taxon in X(T ) is contained in the taxa sets of exactly two trees in T (a fact that we
freely use throughout the rest of this proof), it is straightforward to verify that this sequence
implies a cherry-picking sequence for T .
Part 1: Variable gadgets. For each variable v (k) with k ∈ {1, 2, . . . , n} do the following. If
(k)
(k)
β(v (k) ) = T prune taxon vT from the two trees in Tv ∪ Tv0 whose taxa sets contain vT . On
(k)
the other hand, if β(v (k) ) = F prune taxon vF from the two trees in Tv ∪ Tv0 whose taxa sets
(k)
contain vF . Taken together, these pruning steps delete a single leaf of each tree in Tv and a
single leaf of half of the trees in Tv0 .
Part 2: Clause gadgets. Consider the set of trees resulting from the pruning described in Part
1. For each Ci = `(p) ∨ `(q) ∨ `(r) with i ∈ {1, 2, . . . , m}, let Li be a subset of {p, q, r} such
(k)
that |Li | = 2 and, if `i is not satisfied by β, then k ∈ Li . Setting i = 1, process the three
literals in Ci from left to right in the following way.
(k)

(k)

(k)

1. If `i is satisfied by β, prune `i from the tree in Tc whose taxa set contains `i and,
(k)
(k)
(k)
(k)
(k)
noting that `i ∈ {vi , ¬vi }, prune `i from the tree in Tv0 whose taxa set contains `i .
i
2. If k ∈ Li , prune cs , where s = 1 if k = p, s = 2 if k = q, and s = 3 if k = r, from the two
trees in Tc ∪ Tc0 whose taxa sets contain cis .
3. Prune ∪it , where t = a if k = p, t = b if k = q, and t = c if k = r, from the two trees in
Tc ∪ Tc0 whose taxa sets contain ∪it .
Now prune ∪i from the tree in Tc0 whose taxa set contains ∪i , and prune ∪i from Tf . If i < m,
increment i by one and repeat this process with the next clause. Intuitively, by definition of
Li , the above process prunes exactly two elements in {ci1 , ci2 , ci3 }. Since each clause is satisfied
by β, this guarantees that we can prune each element in {∪ia , ∪ib , ∪ic } and, subsequently ∪i .
Part 3: Formula gadget and remaining taxa. Consider the set of trees resulting from the
pruning described in Part 2. We prune the remaining taxa as follows.
1. In order, prune each of
b4n+3m , b4n+3m−1 , b4n+3m−2 , . . . , b4n+3i , b4n+3i−1 , b4n+3i−2 , . . . , b4n+3 , b4n+2 , b4n+1

bZ

from a tree Tc0 whose taxa set contains the respective blocking taxa and from Tf . After all
taxa have been pruned, each tree in Tc0 is either the null tree or consists of a single vertex
labeled cis for some s ∈ {1, 2, 3}.
2. For each i ∈ {1, 2, . . . , m}, prune the unique taxon cis with s ∈ {1, 2, 3} that has not been
pruned in Part 2 from two trees in Tc ∪ Tc0 . Now, each tree in Tc ∪ Tc0 that is not the null
(k)
tree consists of a single vertex labeled `i for some i ∈ {1, 2, . . . , m} and k ∈ {1, 2, . . . , n}.
3. For each k ∈ {1, 2, . . . , n}, note that one of {b2(n+k)−1 , b2(n+k) } labels a leaf of a cherry in
a tree in Tv0 while the other labels the leaf of a tree in Tv0 that consists of a single vertex.
In order, prune each of
b4n , b4n−1 , . . . , b2(n+k) , b2(n+k)−1 , . . . , b2n+2 , b2n+1
from the tree in Tv0 whose taxa set contains the respective blocking taxa and from Tf .
4. In order, prune bX and bY from Tf and Tf0 .
5. Consider the remaining trees in Tv and observe that each such tree consists of exactly
three leaves, two of which are blocking taxa that form a cherry. In order, prune each of
b2n , b2n−1 , . . . , b2k , b2k−1 , . . . , b2 , b1
from Tf0 and the tree in Tv whose taxa set contains the respective blocking taxon.
(k)

(k)

(k)

6. For each k ∈ {1, 2, . . . , n}, let vX be the unique element in {vT , vF } that has not been
(k)
(k)
pruned in Part 1. Prune vX from the two trees in Tv ∪ Tv0 whose taxa sets contain vX .
(k)
7. For each i ∈ {1, 2, . . . , m} in increasing order, consider each literal `i in Ci = `(p) ∨ `(q) ∨
(r)
` with k ∈ {p, q, r} that is not satisfied by β. By processing such literals from left to
(k)
(k)
right in Ci , prune `i from the two trees in Tv0 ∪ Tc whose taxa sets contain `i . It is
easily seen that the corresponding tree in Tv0 either consists of a single vertex or contains
(k)
a cherry with a leaf labeled `i .
8. Prune bZ from Tf and Tf0 .
Now, relative to the elements in X(T ), we prune 2n elements in Parts 1 and 3.6, all 4m
elements in
m
m
{∪1 , ∪ia , ∪ib , ∪ic , . . . , ∪m , ∪m
a , ∪b , ∪c }

in Part 2, and all 4n + 3m + 3 blocking taxa in Parts 3.1, 3.3, 3.4, 3.5, and 3.8. Additionally,
in Parts 2.1 and 3.7 we prune 3m taxa, and in Parts 2.2 and 3.2, we prune again 3m taxa.
Summing up, we prune
6n + 13m + 3

taxa, which is equal to the number of elements in X(T ).
Second, suppose that T has a cherry-picking sequence σ = (x1 , x2 , . . . , x|σ| ). We write
xi ≺ xj if and only if i < j and xi  xj if and only if i > j. Further, let
M := {1, 2, . . . , m}, N := {1, 2, . . . , n}, B := {b1 , b2 , . . . , b4n+3m , bX , bY , bZ }.
We define a truth assignment β : V → {T, F } as follows
(
(k)


T if ∃i ∈ M : vT ≺ ∪i ,
β v (k) =
F else.
In order to show that β satisifies each clause of I, we establish four necessary conditions that
σ fulfills by construction.

1. All taxa in {∪1 , ∪2 , . . . , ∪m } are pruned earlier than any blocking taxon:
∀i ∈ M ∀b ∈ B : ∪i ≺ b.

(4)

Argument: Observe that the arrangement of bX, bY , bZ in Tf and Tf0 implies that all
taxa in {∪1 , ∪2 , . . . , ∪m } are pruned prior to any blocking taxon. Furthermore, we cannot
prune any taxon in Tf0 until we have pruned all taxa from Tf except for bX , bY , and bZ .
We will freely use Condition 1 throughout the remainder of this proof.
(p) (q) (r)
2. Let Ci = `(p) ∧ `(q) ∧ `(r) be a clause of I. At least one taxon in {`i , `i , `i } is pruned
earlier than ∪i . Stated more formally:
n
o
(s )
(p ) (q ) (r )
(s )
∀i ∈ M ∃`i i ∈ `i i , `i i , `i i : `i i ≺ ∪i .
(5)
Argument: Consider the five trees in Tc ∪Tc0 representing Ci (see Figure 5). In order to prune
∪i , we have to prune all taxa in {∪ia , ∪ib , ∪ic } first. Since we can prune at most two taxa
in {ci1 , ci2 , ci3 } prior to an element in {b4n+3i−2 , b4n+3i−1 }, pruning all taxa in {∪ia , ∪ib , ∪ic }
(p) (q) (r)
is only possible if at least one taxon in {`i , `i , `i } has been pruned previously.
3. Let v (k) ∈ V be any variable of I. Recall the definition of the tuples φk and νk that is
(k)
(k)
used in the construction of the variable gadget. If there exists a vi with vi ≺ ∪i for
(k)
some i ∈ φk , then vT is also pruned earlier than ∪i . Stated formally:


(k)
(k)
∀k ∈ N ∀i ∈ φk : vi ≺ ∪i =⇒ vT ≺ ∪i .
(6)
(k)

Argument: Consider a variable v (k) ∈ V such that vi ≺ ∪i for some i ∈ φk . Since there
(k)
is no blocking taxon b ∈ B with b ≺ ∪i , we have ∪i ≺ b2(n+k)−1 . Thus, vT is pruned
(k)

(k)

(k)

from the associated caterpillar in Tv0 that contains vi such that vT ≺ vi ≺ ∪i (see
Figure 4).
(k)
The following can be shown analogously. If there exists a ¬vi ≺ ∪i for some i ∈ νk , then
(k)
vF is also pruned earlier than ∪i . Stated formally:


(k)
(k)
∀k ∈ N ∀i ∈ νk : ¬vi ≺ ∪i =⇒ vF ≺ ∪i .
(7)
(k)

4. Let v (k) ∈ V be any variable of I. If vT is pruned earlier than some taxon in {∪1 , ∪2 , . . . , ∪m },
(k)
then vF is pruned later than all taxa in {∪1 , ∪2 , . . . , ∪m }, i.e.,




(k)
(k)
∀k ∈ N :
∃i ∈ M : vT ≺ ∪i =⇒ ∀i ∈ M : vF  ∪i .
(8)
(k)

Argument: Consider a variable v (k) ∈ V such that vT ≺ ∪i for some i ∈ M . Assume
(k)
towards a contradiction that there is some j ∈ M such that vF ≺ ∪j . Then, one of the
(k)
two blocking taxa b2k−1 and b2k is pruned prior to vF (see Figure 4). But this is not
possible since there is no blocking taxon b ∈ B with b ≺ ∪j .
(k)
As an immediate consequence of statement (8), we get the analogous statement for vF ,
i.e.,




(k)
(k)
∀k ∈ N :
∃i ∈ M : vF ≺ ∪i =⇒ ∀i ∈ M : vT  ∪i .
(9)

Now, we show that β indeed satisfies
each clause
of I. For each clause Ci =n `(p) ∧ `(q) ∧o`(r) ,
n
o
(s)
(s)
(p) (q) (r)
(s )
(k)
(k)
we have `i ≺ ∪i for some `i ∈ `i , `i , `i
(Condition 2). Since `i i ∈ vi , ¬vi
for
(k)

(s )

(k)

(k)

(s )

(k)

some k ∈ N , we have vT ≺ ∪i if `i i = vi and vF ≺ ∪i if `i i = ¬vi (Condition 3).
(k)
(k)
Hence, by setting β(v (k) ) = T if vT ≺ ∪i and β(v (k) ) = F if vF ≺ ∪i , we satisfy at least one
literal of each clause. Note that we can assign arbitrary truth values to variables v (k) with
(k)
(k)
vT  ∪i and vF  ∪i for all i ∈ M . Here, we choose to set
n all these
o variables to F . The
(k)

(k)

truth assignment β is consistent, since at least one taxon in vT , vF
is pruned later than
all taxa in {∪1 , ∪2 , . . . , ∪m } (Condition 4). Hence, the truth assignment β is consistent and
satisfies each clause of I.

Folding into two trees on the same set of taxa. The trees in Tv ∪ Tc ∪ {Tf } and, similarly,
the trees in Tv0 ∪ Tc0 ∪ {Tf0 } (see Figures 4, 5, and 6) have mutually disjoint taxa sets. Hence,
by n + 3m applications of Lemma 2, we can construct a compound tree S for all trees in
Tv ∪ Tc ∪ {Tf } and, by 2n + 2m applications of Lemma 2, we can construct a compound tree
S 0 for all trees in Tv0 ∪ Tc0 ∪ {Tf0 } such that T has a cherry-picking sequence if and only if S and
S 0 have a cherry-picking sequence. Lastly, by appying Lemma 1, we obtain two trees T and
T 0 from S and S 0 , respectively, such that X(T ) = X(T 0 ), and S and S 0 have a cherry-picking
sequence if and only if T and T 0 have such a sequence. It now follows that I is satisfiable if
and only if T and T 0 have a cherry-picking sequence.
Number of taxa in the final instance. It remains to show that T and T 0 can be constructed
in polynomial time. By Equation 3, recall that |X(T )| = 6n + 13m + 3. Now, since we apply
Lemma 2 a total of 3n + 5m times and each application introduces two new taxa, we have
|X({S, S 0 })| = 6n + 13m + 3 + 2(3n + 5m) = 12n + 23m + 3.
Observe that each taxon in X(T ) labels a leaf of a unique tree in Tv ∪ Tc ∪ {Tf } and a leaf of a
unique tree in Tv0 ∪ Tc0 ∪ {Tf0 }. It therefore follows that each taxon that is contained in exactly
one of X(S) and X(S 0 ) has been introduced by an application of Lemma 2. Conversely, each
application of this lemma, introduces two taxa that are both contained in exactly one of X(S)
and X(S 0 ). Hence,
|X(T )| = |X(T 0 )| = 12n + 23m + 3 + 2(3n + 5m) + 1 = 18n + 33m + 4,
and so it follows, that the size of T and T 0 as well as the time it takes to construct these two
trees are polynomial. This completes the proof of the theorem.
t
u
To illustrate the proof of Theorem 1, we now give an explicit example of a 3-Sat instance
and show how it is reduced to a set of trees by following the construction that is described in
the aforementioned proof. Let I be the following instance of 3-Sat
(x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) .
|
{z
} |
{z
} |
{z
}
C1

C2

C3

For the purpose of ordering the blocking taxa in the same way as described in the proof, we
regard variable x as v (1) , variable y as v (2) , and variable z as v (3) . Let n = 3 (resp. m = 3)
be the number of variables (resp. clauses) in I. We construct a set T of 3n + 5m + 2 = 26

Tv0

Tv

For x:

xT

xF

b1

b2

xT

b7

x1

yT

yF

b3

b4

yT

b9

y2

zT

zF

b5

b6

zT

b11

z1

x3

xF

b8

¬x2

yF

b10

¬y1

zF

b12

¬z3

For y:

¬y3

For z:

z2

Fig. 7. The variable gadget for (x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ ¬z).

trees. The 9 trees that represent the variable gadget Tv and Tv0 are shown in Figure 7, the
15 trees that represent the clause gadget Tc and Tc0 are shown in Figure 8 and the two trees
that represent the formula gadget Tf and Tf0 are shown in Figure 9. Note that |X(T )| =
3n + 13m + 3 = 60. Clearly, I is satisfied for the truth assignment β : {x, y, z} → {T, F } with
β(x) = β(z) = T, β(y) = F . To see that T also has a cherry-picking sequence of length 60, we
follow the sequence of pruning operations that is described in Parts 1-3 in the first direction
of the proof of Claim 1
(xT , yF , zT ,
x1 , c11 , ∪1a , ¬y1 , c12 , ∪1b , z1 , ∪1c , ∪1 , c21 , ∪2a , c22 , ∪2b , z2 , ∪2c , ∪2 , x3 , ∪3a , ¬y3 , c32 , ∪3b , c33 , ∪3c , ∪3 ,

b21 , b20 , . . . , b13 , c13 , c23 , c31 , b12 , b11 , . . . , b7 , bX, bY, b6 , b5 , . . . , b1 , xF , yT , zF , ¬x2 , y2 , ¬z3 , bZ),

where line 1 corresponds to Part 1, line 2 corresponds to Part 2, and line 3 corresponds to
Part 3.

4

Discussion

Given any set of input trees, there always exists some phylogenetic network displaying them.
Roughly speaking, one can simply merge the input trees at the leaves. However, what happens
when you restrict the network to have some additional, biologically motivated, properties?
Then there might not always exist a network displaying the input trees. Moreover, deciding
whether or not there exists such a network may be a difficult problem. Indeed, in this paper we
have shown that even if the input consists of only two binary trees, it is already NP-complete
to decide whether there exists any temporal phylogenetic network displaying them.
One could be tempted to look for approximation algorithms for the associated optimization
problem: given a set of phylogenetic trees, find a temporal network that displays them and
has smallest possible reticulation number, if such a network exists. Note, however, that an
approximation algorithm is required to always output a valid solution, for any valid input.

The problem formulation above (based on [13]) does not specify what a valid solution is when
there does not exist a temporal network displaying the input trees. Nevertheless, whatever
the output in that case is, it can be checked in polynomial time whether the output of the
algorithm is a temporal network displaying the input trees. This is because temporal networks
are tree-child, and checking whether a tree-child network displays a tree can be achieved in
polynomial time [23]. Hence, any approximation algorithm for the problem could be used to
decide in polynomial time whether there exists a temporal network displaying the input trees,
which is not possible, unless P=NP, given the NP-completeness shown in this paper.
Therefore, a more promising direction is to consider fixed-parameter algorithms for the
associated parameterized version of the problem. Given a set of phylogenetic trees and a
parameter k, decide whether there exists a temporal network that displays the input trees
and has reticulation number at most k. One then aims at algorithms solving this problem
in O(|X|O(1) f (k)) time, with f some function of k, preferably of the form ck with c a small
constant. Intuitively, such an FPT algorithm is only exponential in the reticulation number
and not in the number of leaves. Indeed, even though it is NP-complete to decide whether
there exists a temporal network with unlimited reticulation number, for small reticulation
numbers this problem might be much easier. In fact, for instances of two binary trees a fixedparameter algorithm is already known [12]. Important open problems include the question
whether such algorithms exist for instances of more than two trees and whether algorithms
can be developed that work well in practice.
It would also be interesting to consider other biologically motivated network classes. For
example, binary tree-child (e.g. [5]) or tree-sibling networks (e.g. [3]). Could it be that one of
the associated decision problems is nontrivial (for more than two input trees) but polynomialtime solvable? For other network classes, such as tree-based (e.g. [9]) or time-consistent
(e.g. [4]) networks, it is known that there always exists a solution [25]. For such classes,
it would be interesting to study the optimization version of the problem.

5

Acknowledgements

We thank Matúš Mihalák for useful discussions. Leo van Iersel was partly supported by the
Netherlands Organization for Scientific Research (NWO), including Vidi grant 639.072.602,
and partly by the 4TU Applied Mathematics Institute. Simone Linz was supported by the
New Zealand Marsden Fund.

References
1. E. Bapteste, L. van Iersel, A. Janke, S. Kelchner, S. Kelk, J. McInerney, D. Morrison, L. Nakhleh, M. Steel,
L. Stougie, and J. Whitfield. Networks: expanding evolutionary thinking. Trends in Genetics, 29(8):439–
441, 2013.
2. M. Bordewich and C. Semple. Computing the hybridization number of two phylogenetic trees is fixedparameter tractable. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(3):458–
466, 2007.
3. G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente. A distance metric for a class of tree-sibling phylogenetic networks. Bioinformatics, 24(13):1481–1488, 2008.
4. G. Cardona, M. Llabrés, F. Rosselló, and G. Valiente. Path lengths in tree-child time consistent hybridization networks. Information Sciences, 180(3):366–383, 2010.
5. G. Cardona, F. Rosselló, and G. Valiente. Comparison of tree-child phylogenetic networks. IEEE/ACM
Transactions on Computational Biology and Bioinformatics, 6(4):552–569, 2009.

6. Z-Z. Chen and L. Wang. Hybridnet: a tool for constructing hybridization networks. Bioinformatics,
26(22):2912–2913, 2010.
7. M. Cygan, F. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.
Parameterized algorithms, volume 3. Springer, 2015.
8. J. Döcker and S Linz. On the existence of a cherry-picking sequence. 2017. To appear in Theoretical
Computer Science.
9. A. Francis and M. Steel. Which phylogenetic networks are merely trees with additional arcs? Systematic
biology, 64(5):768–777, 2015.
10. M. Garey and D. Johnson. Computers and intractability:a guide to the theory of NP-completeness. 1979.
11. D. Gusfield. ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic
networks. The MIT Press, 2014.
12. P. Humphries, S. Linz, and C. Semple. Cherry picking: a characterization of the temporal hybridization
number for a set of phylogenies. Bulletin of mathematical biology, 75(10):1879–1890, 2013.
13. P. Humphries, S. Linz, and C. Semple. On the complexity of computing the temporal hybridization number
for two phylogenies. Discrete Applied Mathematics, 161(7):871–880, 2013.
14. D. Huson, R. Rupp, and C. Scornavacca. Phylogenetic Networks: Concepts, Algorithms and Applications.
Cambridge University Press, 2011.
15. R. Karp. Reducibility among combinatorial problems. In Complexity of computer computations (Proc.
Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pages 85–103. Plenum,
1972.
16. S. Kelk, L. van Iersel, S. Linz, N. Lekić, C. Scornavacca, and L. Stougie. Cycle killer... Qu’est-ce que c’est?
On the comparative approximability of hybridization number and directed feedback vertex set. SIAM
Journal on Discrete Mathematics, 26(4):1635–1656, 2012.
17. B. Moret, L. Nakhleh, T. Warnow, C. Linder, A. Tholse, A. Padolina, J. Sun, and R. Timme. Phylogenetic
networks: modeling, reconstructibility, and accuracy. IEEE/ACM Transactions on Computational Biology
and Bioinformatics, 1(1):13–23, 2004.
18. C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of
Computer and System Sciences, 43:425–440, 1991.
19. C. Semple and M. Steel. Phylogenetics. Oxford University Press, 2003.
20. S. Soucy, J. Huang, and J. Gogarten. Horizontal gene transfer: building the web of life. Nature Reviews
Genetics, 16(8):472–482, July 2015.
21. M. Steel. Phylogeny: Discrete and random processes in evolution. SIAM, 2016.
22. L. van Iersel, S. Kelk, and C. Scornavacca. Kernelizations for the hybridization number problem on
multiple nonbinary trees. Journal of Computer and System Sciences, 82(6):1075–1089, 2016.
23. L. van Iersel, C. Semple, and M. Steel. Locating a tree in a phylogenetic network. Information Processing
Letters, 110(23):1037–1043, 2010.
24. C. Whidden, R. Beiko, and N. Zeh. Fixed-parameter algorithms for maximum agreement forests. SIAM
Journal on Computing, 42(4):1431–1466, 2013.
25. L. Zhang. On tree-based phylogenetic networks. Journal of Computational Biology, 23(7):553–565, 2016.

For C1 :

Tc
x1

c11

∪1a

c12

¬y1

∪1b

z1

c13

∪1c

Tc0
c11

c12

c13

b13

b14

∪1a

b15

∪1b

∪1c

For C2 :

∪1

Tc
¬x2

c21

∪2a

c22

y2

∪2b

z2

c23

∪2c

Tc0
c21

c22

c23

b16

b17

∪2a

b18

∪2b

∪2c

For C3 :

∪2

Tc
x3

c31

∪3a

c32

¬y3

∪3b

¬z3

∪33

∪3c

Tc0
c31

c32

c33

b19

b20

b21

∪3a

∪3b

∪3c

∪3

Fig. 8. The clause gadget for (x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ ¬z)

Tf
Tf0

bZ

∪1

∪2

∪3

b21

b20

b7

bX

bY

bX

bY

b6

Fig. 9. The formula gadget for (x ∨ ¬y ∨ z) ∧ (¬x ∨ y ∨ z) ∧ (x ∨ ¬y ∨ ¬z)

b5

b1

bZ

