Fast Compatibility Testing for Rooted Phylogenetic Trees∗
Yun Deng†

David Fernández-Baca‡

arXiv:1510.07758v1 [] 27 Oct 2015

Abstract
We consider the following basic problem in phylogenetic tree construction. Let P = {T1 , . . . , Tk } be
a collection of rooted phylogenetic trees over various subsets of a set of species. The tree compatibility
problem asks whether there is a tree T with the following property: for each i ∈ {1, . . . , k}, Ti can be
obtained from the restriction of T to the species set of Ti by contracting zero or more edges. If such a
tree T exists, we say that P is compatible.
We give a Õ(MP ) algorithm for the tree compatibility problem, where MP is the total number of
nodes and edges in P. Unlike previous algorithms for this problem, the running time of our method does
not depend on the degrees of the nodes in the input trees. Thus, it is equally fast on highly resolved and
highly unresolved trees.

1

Introduction

Building a phylogenetic tree that encompasses all living species is one of the central challenges of computational biology. Two obstacles to achieving this goal are lack of data and conflict among the data that is
available. The data shortage is tied to the vast disparity in the amount of information at our disposal for
different families of species and the limited amount of comparable data across families [15]. One approach
to overcoming this obstacle begins by identifying subsets of species for which enough data is available, and
building phylogenies for each subset. The resulting trees are then synthesized into a single phylogeny —a
supertree— for the combined set of species. This approach, proposed in the early 90s [2, 14], has been used
successfully to build large-scale phylogenies (see, e.g., [3, 10]).
Any attempt at synthesizing phylogenetic information from multiple input trees must deal with the
potential for conflict among these trees. Conflict may arise due to errors, or due to phenomena such as gene
duplication and loss, and horizontal gene transfer. A fundamental question is whether conflict exists at all;
that is, does there exist a supertree that exhibits the evolutionary relationships implicit in each input tree? We
can formalize this question as follows. Let P = {T1 , . . . , Tk } be a collection of rooted phylogenetic trees,
where, for each i ∈ {1, . . . , k}, Ti is a phylogenetic tree for a set of species L(TiS
). The tree compatibility
problem asks whether there exists a phylogenetic supertree T for the set of species ki=1 L(Ti ) such that, for
each i ∈ {1, . . . , k}, Ti can be obtained from T |L(Ti ) — the minimal subtree of T spanning L(Ti ) — by
zero or more contractions of internal edges (that is, T |L(Ti ) is homeomorphic to T ). If the answer is “yes”,
then P is said to be compatible; otherwise, P is incompatible.
Here we present an algorithm that solves the compatibility problem for rooted trees in O(MP log2 MP )
time, where MP is the total number of vertices and edges in the trees in P. This running time is independent
of the degrees of the internal nodes of the input trees.
∗

Supported in part by the National Science Foundation under grants CCF-1017189 and CCF-1422134.
Department of Computer Science, Iowa State University, Ames, IA 50011, USA, yundeng@iastate.edu
‡
Department of Computer Science, Iowa State University, Ames, IA 50011, USA, fernande@iastate.edu
†

1

Previous work. Aho et al. [1] gave the first polynomial-time algorithm for the rooted tree compatibility
problem. Their motivation was not phylogenetics, but relational databases. Steel [17] was perhaps the first to
note the relevance of Aho et al.’s algorithm to supertree construction. His version of the Aho et al. algorithm,
which he called the B UILD algorithm, has been a major influence in later work, including the present paper.
Henzinger et al. [9] showed that one can check the compatibility of a collection R of rooted triples —
that is, phylogenetic trees on three species — in O(|R| log2 |R|) time. (The time bound stated in [9] is
higher, but can be improved using a faster dynamic graph connectivity data structure [11].) Any collection
of trees P can be encoded by a collection of rooted triples R(P), obtained by enumerating the restriction of
each input tree to every three-element subset of its species set (see Section 2). If n denotes the total number
of distinct species in P, then we get a trivial upper bound of |R(P )| = O(n3 k). We can improve on this by
finding a minimal set R∗ of rooted triples that define the input trees. If the trees are binary — fully resolved,
in the language of phylogenetics —, then O(n) triples suffice for each tree, giving us |R∗ | = O(nk). If
input trees admit non-binary — that is, unresolved — nodes, however, the number of triples needed per input
tree is roughly proportional to n2 (the precise bound depends on the sum of the products of the degrees of
internal nodes and the degrees of their children [8]), giving us |R∗ | = O(n2 k). Of course, the extra step of
finding R∗ adds to the complexity of the algorithm.
The tree compatibility problem is related to the incomplete directed perfect phylogeny problem (IDPP).
Indeed, any collection of k phylogenetic trees on n distinct species can be encoded as a problem of testing
the compatibility of a collection of O(MP ) “directed partial characters” on n species1 . Intuitively, each
such character encodes the species in the subtree rooted at some node in an input tree. There is a Õ(nm)
algorithm to test the compatibility of m incomplete characters [13], which can be adapted to yield a Õ(nMP )
algorithm for tree compatibility.
When the input trees are unrooted, the tree compatibility problem becomes NP-hard [17]. Nevertheless,
the decision version is polynomial-time solvable if k is fixed [4]; that is, the problem is fixed-parameter
tractable in k. The proof of fixed-parameter tractability in [4] relies on Courcelle’s Theorem [6], and thus is
an existence proof, rather than a practical algorithm.
Our contributions. At a high level, our algorithm resembles B UILD [17, 16]. There are, however, important differences. B UILD relies on the triplet graph, whose nodes are the species and where there is an edge
between two species if they are involved in a triplet (see Section 2). Our algorithm relies instead on intersection graphs of sets of species associated with certain nodes of the input trees. Our graphs allow a more
compact representation of the triplets induced by the trees in P (see Section 3). The key to the correctness
of our approach is the intimate relationship between the triplet graph and our intersection graph (see Lemma
5 of Section 3). We remark that intersection graphs have a long history of use in testing compatibility,
beginning with the work of Buneman [5].
We also take ideas from other sources. From Pe’er et al.’s IDPP algorithm [13], we adapt the idea of a
semi-universal node. Although the graphs used to solve IDPP and rooted compatibility are different, semiuniversal nodes play similar roles in each case: they capture the notion of sets of nodes in the input trees
that map to the same node in a supertree, if a supertree exists. The relationship between our algorithm and
Pe’er et al.’s goes deeper. Our approach can be viewed as an algorithm for IDPP that takes advantage of the
fact that our particular set of incomplete characters arises from a collection of trees.
Intersection graphs are a convenient tool to prove the correctness for our algorithm. They are less
convenient for an implementation, because it is hard to maintain them dynamically, in the way our algorithm
requires. The difficulty lies in recomputing set intersections whenever the graphs are updated. We avoid this
1

For a precise definition of partial characters and IDPP, we refer the reader to Pe’er et al. [13].

2

by using display graphs, an idea that we borrow from the proof of the fixed-parameter tractability of unrooted
compatibility [4]. The display graph of a collection P is obtained by identifying leaves in the input trees that
have the same label. Display graphs provide all the connectivity information we need for our intersection
graphs (see Lemma 6 of Section 4), but are easier to maintain.
Through our techniques, we achieve what, to our knowledge, is the first algorithm for rooted compatibility to achieve near-linear time under all input conditions, regardless of the degrees of the nodes in the
input trees. This is an essential quality for dealing with large datasets.
Contents. Section 2 reviews basic concepts in phylogenetics, defines compatibility formally, and introduces triplets and the triplet graph. Section 3 presents our intersection graph approach to testing tree compatibility. Section 4 describes the implementation details needed to achieve the O(MP log2 MP ) time bound.
Section 5 contains some final remarks.

2

Preliminaries

For each positive integer r, [r] denotes the set {1, . . . , r}.
Phylogenetic trees. Let T be a rooted tree. We use V (T ), E(T ), and r(T ) to denote the nodes, edges,
and the root of T , respectively. For each x ∈ V (T ), we use Ch(x) and T (x) to denote the set of children of
x and the subtree of T rooted at x, respectively. Suppose u, v ∈ V (T ). Then, u is a descendant of v if v lies
on the path from u to r(T ) in T . Note that v is a descendant of itself. T is binary, or fully resolved, if each
of its internal nodes has two children.
A (rooted) phylogenetic tree is a rooted tree T where every internal node has at least two children,
along with a bijection λ that maps each leaf of T to an element of a set of species, denoted by L(T ). For
each x ∈ V (T ), L(x) denotes the set of species mapped to the leaves of T (x); that is, L(x) = {λ(v) :
v is a leaf in T (x)}. L(x) is called the cluster at x. Note that L(r(T )) = L(T ). The set of all clusters in T
is Cl(T ) = {L(x) : x ∈ V (T )}.
The following lemma, adapted from [16, p. 52], is part of the folklore of phylogenetics.
Lemma 1. Let H be a collection of non-empty subsets of a set of species X that includes all singleton
subsets of X as well as X itself. If there exists a phylogenetic tree T such that Cl(T ) = H, then, up to
isomorphism, T is unique.
Let T be a phylogenetic tree and A be a set of species. The restriction of T to A, denoted T |A is the
phylogenetic tree with species set A where Cl(T |A) = {C ∩ A : C ∈ Cl(T ) and C ∩ A 6= ∅}. Let T 0
be a phylogenetic tree. T displays T 0 if Cl(T 0 ) ⊆ Cl(T |L(T 0 )). Equivalently, T displays T 0 if T |L(T 0 ) is
homeomorphic to T 0 .
A rooted triple is a binary phylogenetic tree on three leaves. A rooted triple with leaves a, b, and c is
denoted ab|c if the path from a to b does not intersect the path from c to the root. We treat ab|c and ba|c as
equivalent.
When restricted to the three-element subsets of its species set, a phylogenetic tree T induces a set R(T )
of rooted triples, defined as R(T ) = {T |X : X ⊆ L(T ), |X| = 3 and T |X is binary}.
Lemma 2 ([16, p. 119]). Let T and T 0 be two phylogenetic trees. Then T displays T 0 if and only if R(T 0 ) ⊆
R(T ).

3

T
T1

a

b

T2

c

b

c

T3

d

c

d

e

a

b

c

d

e

Figure 1: A profile P = {T1 , T2 , T3 } and a tree T that displays P.
Profiles and compatibility. Throughout the rest of this paper P = {T1 , . . . , Tk } denotes a set
S where, for
each i ∈ [k], Ti is a phylogenetic tree. We
S refer to P as a profile,
S and write L(P) to denote S i∈[k] L(Ti ),
the species set of P. We write V (P) for i∈[k] V (Ti ), E(P) for i∈[k] E(Ti ), and R(P) for i∈[k] R(Ti ).
Given a subset A of L(P ), P|A denotes the profile {T1 |A, . . . , Tk |A}. The size of P is MP = |V (P)| +
|E(P)|. Note that MP = O(nk).
Profile P is compatible if there exists a phylogenetic X-tree T such that, for each i ∈ [k], T displays Ti .
If such a tree T exists, we say that T displays P. See Figure 1.
The triplet graph. The triplet graph of a profile P, denoted Γ(P), is the graph whose vertex set is L(P )
and where there is an edge between species a and b if and only if there exists a c ∈ L(P ) such that
ab|c ∈ R(P). The following observation concerning singleton profiles will be useful.
Observation 1. Let T be a phylogenetic tree with |L(T )| > 2. Let u1 , . . . , up be the children of r(T ). Then,
the connected components of Γ({T }) are L(u1 ), . . . , L(up ), where p ≥ 2.

3

Testing Compatibility

Here we describe our compatibility algorithm and proveSits correctness. We begin with some definitions.
Let U be a subset of V (P) and let L(U ) denote u∈U L(u). Then, GP (U ) denotes the graph with
vertex set U and where u, v ∈ U are joined by an edge if and only if L(u) ∩ L(v) 6= ∅. That is, GP (U ) is
the intersection graph of the clusters associated with the nodes in U . For each i ∈ [k], let U (i) = U ∩ V (Ti ).
We say that U is valid if, for each i ∈ [k],
(V1) if |U (i)| ≥ 2, then there exists a node v ∈ V (Ti ) such that U (i) ⊆ Ch(v) and
(V2) L(U (i)) = L(Ti ) ∩ L(U ).
Observe that the set Uinit defined as follows is valid.
Uinit = {r(Ti ) : i ∈ [k]}

(1)

Note that L(Uinit ) = L(P). From this point forward, we assume that GP (Uinit ) is connected. No generality
is lost by doing so. To see why, observe that If GP (Uinit ) is not connected, then P can be partitioned into a
collection of species-disjoint profiles P1 , . . . , Pr such that P is compatible if and only if Pj is compatible
for all j ∈ [r].
The next observation follows from the definition of a valid set.
Observation 2. If U is a valid subset of V (P), then, for each i ∈ [k], Cl(Ti |L(U )) = {L(U (i))} ∪ {L(v) :
v is a descendant of a node in U (i)}.

4

Together with Lemma 1, Observation 2 shows that Ti |L(U ) is completely determined by the descendants
of U (i).
A valid subset U of V (P) is compatible if there exists a phylogenetic tree T with L(T ) = L(U ) that
displays Ti |L(U ) for every i ∈ [k]. If such a tree T exists, we say that T displays U .
Lemma 3. Profile P is compatible if and only if every valid subset of V (P) is compatible.
Proof. (⇐) If every valid subset of V (P) is compatible, then, in particular, so is the set Uinit of Equation (1).
Let T be a tree that displays Uinit . Then, L(T ) = L(Uinit ) = L(P). Thus, for every i ∈ [k], Ti |L(T ) = Ti ,
and thus T displays Ti . Hence, P is compatible.
(⇒) Suppose P is compatible, but there is a valid subset U of V (P) that is not compatible. Let T be a
tree that displays P. But then T |U displays U , a contradiction.
B UILD ST (Algorithm 1), which is closely related to Semple and Steel’s B UILD algorithm [16], determines whether a valid set U ⊆ V (P) is compatible. The key difference between B UILD ST and B UILD
is that the latter uses the triplet graph Γ(P), while B UILD ST uses the graph GP (U ), for different subsets
U of V (P). As we show in Lemma 5, the two graphs are closely related. Nevertheless, GP (U ) offers
some computational advantages over the triplet graph. Intuitively, this is because GP (U ) is a more compact
representation of the triplets in R(P).
B UILD ST(U ) attempts to build a tree TU for U . Step 1 initializes the root of TU . If L(U ) consists
of one or two species, then U is trivially compatible; Steps 2–5 handle these cases. The loop in lines 6–8
identifies the indices i ∈ [k] such that U (i) is a singleton. For each such i, it removes the single element v in
U (i) and replaces v by its children in Ti . As we argue in the proof of Theorem 1, when P is compatible, all
such nodes v map to the same node w in the T that displays P, in the sense that L(w) is the smallest cluster
in T such that L(v) ⊆ L(w)2 . In Theorem 1, we also show that, if GP (U ) remains connected after steps
6–8, then U is incompatible. This case is handled in Line 11. Otherwise, Lines 12–17 recursively process
each connected component of GP (U ). If the recursive calls succeed in finding trees for all the components,
these trees are assembled into a phylogeny for U by joining them to the root created in Step 1. If any of the
recursive calls determines that a component is incompatible, then U is declared to be incompatible.
The correctness of B UILD ST relies on two lemmas, the first of which can be proved using induction.
Lemma 4. If, given a valid set U ⊆ V (P), B UILD ST(U ) returns a tree TU , then TU is a phylogenetic tree
such that L(TU ) = L(U ).
The next lemma is central to the correctness proof of B UILD ST.
Lemma 5. Let W1 , . . . , Wp be the connected components of GP (U ) at step 9 of B UILD ST(U ), for some
valid set U ⊆ V (P). Then,
(i) for each j ∈ [p], Wj is a valid set, and
(ii) the connected components of Γ(P|L(U )) are precisely L(W1 ), . . . , L(Wp ).
Proof. (i) Let Ubef and Uaft denote the values of U before and after the executing steps 6–8. Each element
of Uaft is either an element of Ubef or a child of some v ∈ Ubef . Indeed, in the latter case, every
S child of v is
in Uaft . Thus, since, by assumption, Ubef is valid, and for every non-leaf node v, L(v) = w∈Ch(v) L(w),
Uaft must also be valid. Part (i) follows.
(ii) We first show that the following holds after steps 6–8.
2

Thus, v plays the role of a semi-universal node, in the sense of Pe’er et al. [13].

5

Algorithm 1: B UILD ST(U )
Input: A valid set U ⊆ V (P).
Output: A tree TU that displays U , if U is compatible; incompatible otherwise.
1 Create a node rU
2 if |L(U )| = 1 then
3
return the tree consisting of node rU , labeled by the single species in L(U )
4 if |L(U )| = 2 then
5
return the tree consisting of node rU and two children, each labeled by a different species in
L(U )
6 foreach i ∈ [k] such that |U (i)| = 1 do
7
Let v be the single element in U (i)
8
U = (U \ {v}) ∪ Ch(v)
9 Let W1 , W2 , . . . , Wp be the connected components of GP (U )
10 if p = 1 then
11
return incompatible
12 foreach j ∈ [p] do
13
Let tj = B UILD ST(Wj )
14
if tj is a tree then
15
Add tj to the set of subtrees of rU
16
else
17
return incompatible
18 return the tree with root rU

Claim 1. Let a and b be any two species in L(U ). Then, (a, b) is an edge in Γ(P|L(U )) if and
only if there exists a node v ∈ U such that a, b ∈ L(v).
Proof of claim. Observe that, after steps 6–8, |U (i)| =
6 1, for each i ∈ [k].
(⇐) Suppose that (a, b) is an edge in Γ(P|L(U )). Then, there is an i ∈ [k] such that ab|x ∈
R(Ti |L(U )). Thus, there must be a proper descendant w of r(Ti |L(U )) such that {a, b} ⊆
L(w). Observation 2 and the fact that |U (i)| > 1 imply that L(w) ⊆ L(v) for some v ∈ U (i).
(⇒) Suppose that there is an i ∈ [k] such that a, b ∈ L(v) for some v ∈ U (i). Choose a node
v 0 ∈ U (i) \ {v} — such a v 0 must exist, since |U (i)| ≥ 2 — and choose some x ∈ L(v 0 ). Then,
ab|x ∈ R(Ti |L(U )), and, hence, (a, b) is an edge of Γ(P|L(U )).
2
Observe that both Π1 = {A : A is a connected component of Γ(P|L(U ))} and Π2 = {L(W ) : W is a
connected component of GP (U )} are partitions of L(U ). We prove that Π1 = Π2 by showing that (a) for
each connected component A of Γ(P|L(U )) there exists a connected component W of GP (U ) such that
A ⊆ L(W ), and (b) for each connected component W of GP (U ) there exists a connected component A of
Γ(P|L(U )) such that L(W ) ⊆ A.
(a) Let A be any connected component of Γ(P|L(U )). We argue that any two species a, b in A must be
in the same connected component of GP (U ). Let Ua = {v ∈ U : a ∈ L(v)} and Ub = {v ∈ U : b ∈ L(v)}.
Then, each of Ua and Ub is a clique in GP (U ). It thus suffices to show that there is a path between some
node in Ua and some node in Ub .

6

By the definition of A, there exists a path between a and b in Γ(P|L(U )). Suppose this path is ρ =
ha1 , . . . , am i, where a1 = a and am = b. By Claim 1, for each l ∈ [m − 1], there exists a node wl ∈ U
such that {al , al+1 } ⊆ L(wi ). For each l ∈ [m − 2], L(wl ) ∩ L(wl+1 ) 6= ∅, so there is a edge between wi
and wi+1 in GP (U ). Hence, π = hw1 , . . . , wm−1 i is a path from w1 to wm−1 in GP (U ). By the definition
of ρ, a ∈ L(w1 ) and b ∈ L(wm−1 ), so w1 ∈ Ua and wl ∈ Ub . This completes the proof of part (a).
(b) Let W be any connected component of GP (U ). If |L(W )| = 1, the statement holds trivially, so
assume that |L(W )| > 1. We argue that any two species a, b in L(W ) are in the same connected component
of Γ(P|L(U )). Let va and vb be nodes in W such that a ∈ L(va ) and b ∈ L(vb ). If va = vb , then, by Claim
1, (a, b) is an edge of Γ(P|L(U )), and we are done. So, suppose instead that va 6= vb .
Let us call a path π from va to vb good if |L(w)| > 1 for every node w in π. We claim that there
exists a good path from va to vb . To prove this claim, we first argue that we can choose va and vb such that
|L(va )|, |L(vb )| > 1. Indeed, consider the case of species a (the case for b is analogous). If |L(v)| = 1 for
every node v ∈ W such that a ∈ L(v), then we would have |L(W )| = 1, contradicting our assumption that
|L(W )| > 1. Now, suppose the path π from va to vb has a node w ∈
/ {va , vb } such that |L(w)| = 1. Let w0
and w00 be the predecessor and successor of w in π. Then, L(w0 ) ∩ L(w00 ) = L(w) 6= ∅, so there is an edge
between w0 and w00 . Thus, we can delete w from π and the resulting sequence remains a path between va
and vb .
Let π = hw1 , . . . , wl i, where w1 = va and wl = vb , be a good path from va to vb in GP (U ). Choose
a sequence of species ρ = hc1 , . . . , cl+1 i, where c1 = a, cl+1 = b and, for each j ∈ [l], cj , cj+1 ∈ L(wj )
and cj 6= cj+1 . Note that such a choice is always possible. Then, by Claim 1, (cj , cj+1 ) is an edge of
Γ(P|L(U )). Hence, ρ is a path from a to b in Γ(P|L(U )).
We are now ready to prove the correctness of B UILD ST.
Theorem 1. Let Uinit be the set defined in Equation (1). Then, B UILD ST(Uinit ) either (i) returns a tree T
that displays P, if P is compatible, or (ii) returns incompatible otherwise.
Proof. We first argue that if B UILD ST(Uinit ) outputs incompatible, P is indeed incompatible. Assume, on
the contrary, that P is compatible. Then, there must be a call B UILD ST(U ) for some valid subset U such that
|L(U )| > 2, in which the graph G(U ) of step 9 has a single connected component, W1 = U . By Lemma 3,
U must be compatible, so there exists a phylogeny TU that displays U . By Observation 1, Γ({TU }) has at
least two connected components A and B. By Lemma 5(ii), however, Γ(P|L(U )) is connected, so there
exist species a ∈ A and b ∈ B such that ab|c ∈ R(P|U ). But ab|c ∈
/ R(T ), and, by Lemma 2, T does not
display some tree in P|L(U ), a contradiction. Thus, G(U ) has at least two components.
Now, suppose that B UILD ST(Uinit ) returns a tree T . We prove that T displays P by arguing that for each
i ∈ [k] there is a mapping φi : V (Ti ) → V (T ) that maps every node v ∈ V (Ti ) to a node φi (v) ∈ V (T )
such that L(v) ⊆ L(φi (v)).
By Lemma 4, each recursive call B UILD ST(U ) returns a phylogenetic tree TU for L(U ). Let rU denote
the root of TU . We have two cases.
Case (i): |L(U )| ≤ 2. For each i ∈ [k], we must have |U (i)| ∈ {0, 1}. We only need to consider
the case where |U (i)| = 1. Let v be the single node in U (i). Note that L(v) ⊆ L(rU ). Thus, we make
φi (v) = rU . If |L(U (i))| = 1, we are done. Otherwise, |L(U (i))| = 2. Then, v has two children, v1 and
v2 , both leaves, labeled with, say, species s1 and s2 , respectively. Node rU also has two children, r1 and
r2 . Assume, without loss of generality, that these children are labeled with species s1 and s2 , respectively.
Then, L(vj ) = L(rj ) for j ∈ {1, 2}. Therefore, we make φi (vj ) = rj for each j ∈ {1, 2}.
Case (ii): |L(U )| > 2. Let Ubef be the value of U before entering the loop of lines 6–8, and let Uaft be
the value of U at line 9, after the loop of lines 6–8 terminates. Let Urem = {v ∈ Ubef : v ∈ Ubef (i) for
7

some i ∈ [k] such that |Ubef (i)| = 1}. Then Uaft = (Ubef \ Urem ) ∪ {u ∈ Ch(v) : v ∈ Urem }. Assume
inductively that every descendant of a node in Uaft is mapped to an appropriate node in TU . It therefore
suffices to establish mappings for the nodes in Urem . Now, for every v ∈ Urem , L(v) ⊆ L(rU ). Thus, we
make φ(v) = rU for every v ∈ Urem .

4

Implementation

We now explain how to implement B UILD ST in order to solve the tree compatibility problem in O(MP log2 MP )
time. Consider a call to B UILD ST(U ). Recall that we can assume that GP (U ) is connected. B UILD ST(U )
requires the following three pieces of information.
(G1) The value of |L(U )|. This number is needed in Lines 2 and 4 of B UILD ST.
(G2) The set J(U ) of all i ∈ [k] such that |U (i)| = 1. Set J(U ) contains the indices i considered in Lines
6–8 of B UILD ST.
(G3) The set U (i) = U ∩ V (Ti ) for each i ∈ [k]. For each i ∈ J(U ), U (i) contains precisely the element
v used in Lines 7 and 8 of B UILD ST.
It is straightforward to obtain (G1), (G2), and (G3) for the valid set Uinit of Equation (1): |L(Uinit )| = n,
J(Uinit ) = [k], and, for every i ∈ [k], Uinit (i) = {r(Ti )}. Now assume that we have (G1), (G2), and (G3)
at the beginning of some call to B UILD ST(U ). Steps 6–8 modify U and, therefore, GP (U ). Suppose that,
after Line 9, GP (U ) has more than one connected component. We need to compute (G1), (G2), and (G3)
for each connected component, in order to pass this information to the recursive calls in Line 13. That is, if
p > 1, for each j ∈ [p], we need to compute |L(Wj )|, J(Wj ), and Wj (i) = Wj ∩ V (Ti ), for each i ∈ [k].
We use the dynamic graph connectivity data structure by Holm et al. [11]. We refer to this data structure
as HDT. HDT guarantees that, if we start with no edges in a graph with N vertices, the amortized cost of
each update is O(log2 N ). For efficiency, however, do not use HDT directly on GP (U ). The reason is that
the edges of GP (U ) are defined via intersections of sets of species, which could make it costly to determine
the new nodes and edges created as a result of Step 8. We avoid this problem through an indirect approach
that uses an auxiliary graph HP (U ), defined below. As we shall see, HP (U ) offers another advantage over
GP (U ): maintaining HP (U ) only requires handling deletions, but maintaining GP (U ) additionally requires
handling insertions.
We define HP (U ) as a subgraph of the graph HP constructed as follows. For each species s ∈ L(P),
create a new node xs ∈
/ V (P), and let XP = {xs : s ∈ L(P)}. Then, HP is the graph whose vertex
set is V (P) ∪ XP and whose edge set is E(P) ∪ {(u, xs ) : u is a leaf in Ti , for some i ∈ [k], such that
λ(u) = s}. Note that HP has O(MP ) nodes and edges, and can be constructed from P in O(MP ) time.
HP is essentially the display graph for P [4]. The display graph is the result of glueing together leaves in
P labeled by the same species. Contrast this with HP , which connects leaves with a common label through
nodes in XP . This minor difference with respect to the display graph serves to simplify our presentation.
Given a valid subset U of V (P), we define HP (U ) as the subgraph of HP induced by {v : v is a
descendant of some node u ∈ U } ∪ {xs ∈ XP : s ∈ L(U )}. Note that HP (Uinit ) = HP . See Figure 2.
The next result states the basic properties of HP (U ).
Lemma 6. The following statements hold for any valid subset U of V (P).
(i) Let v be a node in U . If U 0 = (U \ {v}) ∪ Ch(v), then HP (U 0 ) is obtained from HP (U ) by deleting
v and every edge (v, u) such that u ∈ Ch(v).
(ii) Any two nodes in U are in the same connected component in GP (U ) if and only if they are in the same
connected component of HP (U ).
8

a

b

c

d

e

Figure 2: The graph HP (Uinit ) for the profile P of Figure 1. The nodes of Uinit are drawn as squares. Nodes
in the set {xs : s ∈ L(P)} are labeled with the corresponding species. Species labeling the leaves of trees
in P are omitted.
Proof. The proof of part (i) is trivial, so we focus on part (ii). We argue that, for any two nodes v, w ∈ U ,
v and w are in the same connected component in GP (U ) if and only if they are in the same connected
component of HP (U ).
(⇐) Suppose v and w are in the same connected component of HP (U ). Then, there exists a path π
between v and w in HP (U ). Let π 0 = hu1 , . . . , um i be the sequence obtained by striking out from π all
nodes not in U . Note that u1 = v and um = w. For each i ∈ [m − 1], the subpath of π between ui and ui+1
contains at least one node from XP , say xs , for some s ∈ L(P). But then s ∈ L(ui ) ∩ L(ui+1 ), so there is
an edge between ui and ui+1 in GP (U ). Thus, π 0 is a path between ui and ui+1 in GP (U ). Hence, v and w
are in the same connected component in GP (U ).
(⇒) Suppose v and w are in the same connected component of GP (U ). Then, there exists a path
between v and w in GP (U ). Let hu1 , . . . , um i be one such path, where u1 = v and um = w. By definition
of GP (U ), for each i ∈ [m − 1], L(ui ) ∩ L(ui+1 ) 6= ∅. Pick any species s ∈ L(ui ) ∩ L(ui+1 ). Hence, in
HP (U ) there is a path from ui to ui+1 that goes through xs . Since this holds for each i ∈ [m − 1], there
exists a path from u1 = v to um = w in HP (U ). Thus, v and w are in the same connected component in
HP (U ).
By Lemma 6(ii), the connected components W1 , . . . , Wp of GP (U ) can be put into a one-to-one correspondence with the connected components Y1 , . . . , Yp of HP (U ) so that Wj = Yj ∩ U for each j ∈ [p].
We represent HP (U ) using the aforementioned HDT data structure. For each connected component Y
of HP (U ), we maintain three fields:
(H1) Y.count, the cardinality of Y ∩ XP ,
(H2) Y.singleton, a doubly-linked list that contains all indices i ∈ [k] such that |U (i)| = 1, and
(H3) Y.List, an array where, for each i ∈ [k], Y.List[i] is a doubly-linked list consisting of the elements
of Y ∩ U (i).
Recall that we assume that GP (U ) is connected at the beginning of a call to B UILD ST(U ). Thus, by
Lemma 6, HP (U ) has a single connected component, Y . Then, |L(U )| = Y.count, J(U ) = Y.singleton,
and Y.List[i] contains the elements of U (i), for each i ∈ [k]. Thus, the three fields of Y provide
B UILD ST(U ) with the information that it needs — that is, (G1), (G2), and (G3). In particular, they allow us to easily find each node v considered in Line 7 of B UILD ST(U ). Line 8 is then performed as a series
of edge deletions, one for each edge (v, u) such that u ∈ Ch(v), followed by the deletion of v (we provide
further details below). By Lemma 6(i), this correctly updates HP (U ). The deletions break HP (U ) down
into a collection of connected components Y1 , . . . , Yp . For each j ∈ [p], Yj corresponds to a connected
component Wj of GP (U ) that (if p > 1) is processed in a recursive call in Line 13. We need to compute
Yj .count, Yj .singleton, Yj .List for each j ∈ [p], in order to provide this information to the recursive
calls.
9

The total number of edge and node deletions executed by B UILD ST(Uinit ) — including all deletions
conducted by the recursive calls — cannot exceed the total number of edges and nodes in HP , which is
O(MP ). The HDT data structure allows us to maintain connectivity information throughout the entire
algorithm in O(MP log2 MP ). In the remainder of this section, we show that we can maintain the count,
singleton, and List fields throughout the entire algorithm in total time O(MP log2 MP ). We also argue
that all the required information for HP (Uinit ) can be initialized in O(MP ) time.
Let Yinit = V (P) ∪ XP be the vertex set of HP (Uinit ). Then, Yinit is the single connected component of
HP (Uinit ). We initialize the data fields of Yinit as follows: (1) Yinit .count = |L(P)|, (2) Yinit .singleton
is the set [k], and (3) for each i ∈ [k], Yinit .List[i] consists of r(Ti ). Thus, we can initialize all data fields
in O(MP ) time.
We assume that every node v in HP (U ) is either marked, if v ∈ U , or unmarked, if v ∈
/ U . Initially,
each node v ∈ Uinit is marked, and every node v ∈ Yinit \ Uinit is unmarked. We also assume that for each
node v in HP (U ), we maintain sufficient information to be able to determine in O(1) time whether v ∈ XP
or v ∈ V (P), and that, in the latter case, we have O(1)-time access to the index i ∈ [k] such that v ∈ V (Ti ).
For each i such that Y.List[i] contains exactly one element, we maintain a pointer from Y.List[i] to the
entry for i in Y.singleton. This allows us to update Y.singleton in O(1) time when U (i) is no longer
a singleton. For each marked node v ∈ Y (so v ∈ U ), we maintain a pointer from v to the element in
Y.List[i] that contains v. This allows us to update Y.List[i] in O(1) time when v becomes unmarked.
Consider a call to B UILD ST(U ) for some valid set U . Step 1 takes O(1) time. Since HP (U ) initially
consists of a single connected component, say Y , and we have Y.count, Steps 2–5 also take O(1) time. Let
H = HP (U ). We implement the loop in lines 6–8 as follows. First, we enumerate the indices in J = J(U )
in O(|J|) time by listing the elements of Y.singleton. For each i ∈ J, we retrieve and remove the single
element vi of U (i) from Y.List[i], and then delete i from Y.singleton. This takes O(1) time. We unmark
vi , and for every node u ∈ Ch(vi ) we mark u and add it to Y.List[i]. This takes O(1) time per edge. We
then successively delete each edge (vi , u) such that u ∈ Ch(vi ), updating (H1)–(H3) for each newly-created
component along the way. Once these edges are deleted, we delete vi itself. By Lemma 6(i), the result is the
graph HP (U ) for the new set U . Let us focus on how to handle the deletion of a single edge e = (vi , u).
Let Y 0 be the connected component of H that currently contains vi . We query the HDT data structure
to determine, in O(log2 MP ) amortized time, whether deleting (vi , u) splits Y 0 into two components. If Y 0
remains connected, no updates are needed. Otherwise, Y 0 is split into two parts Y1 and Y2 . To fill in the
count, singleton, and List fields of Y1 and Y2 , we use the well-known technique of scanning the smaller
component [7]. The HDT data structure maintains the sizes of the various components [11], so we can
determine in O(1) which of Y1 and Y2 has fewer nodes. Suppose without loss of generality that |Y1 | ≤ |Y2 |.
We initialize Y2 .count and Y2 .List to Y 0 .count and Y 0 .List, respectively. We initialize Y1 .count to 0
and Y1 .List[i] to null for each i ∈ [k]. We then scan each node v in Y1 , and do the following. If v ∈ XP ,
we decrement Y2 .count and increment Y1 .count. Otherwise v ∈ V (P); assume that v ∈ V (Ti ). If v is
marked, we remove v from Y2 .List[i] and add v to Y1 .List[i]. This operation requires at most one update
in each of Y1 .singleton and Y2 .singleton; each update takes O(1) time.
We claim that any node v is scanned O(log MP ) times over the entire execution of B UILD ST(Uinit ).
To verify this, let N (v) be the number of nodes in the connected component containing v. Suppose that,
initially, N (v) = N . Then, the rth time we scan v, N (v) ≤ N/2r . Thus, v is scanned O(log N ) times. The
claim follows, since N = O(MP ). Therefore, the total number of updates over all nodes is O(MP log MP ),
and the work per update is O(1).
To summarize, the work done by B UILD ST consists of three parts: (i) initialization, (ii) maintaining
connected components, and (iii) maintaining the count, singleton, and List fields for each connected

10

component. Part (i) takes O(MP ) time. Part (ii) involves O(MP ) edge and node deletions on the HDT data
structure, at an amortized cost of O(log2 MP ) per deletion. Part (iii) involves scanning the nodes of our
graph every time a deletion creates a new component, for a total of O(MP log MP ) scans, at O(1) cost per
scan, over the entire execution of B UILD ST. This yields our main result.
Theorem 2. Let Uinit be the set defined in Equation (1). Then, there exists and implementation of B UILD ST
such that B UILD ST(Uinit ) runs in O(MP log2 MP ) time.

5

Discussion

A trivial lower bound for the tree compatibility problem is Ω(MP ), the time to read the input. Thus, our
result leaves us a polylogarithmic factor away from an optimal algorithm for compatibility. Is it possible to
reduce or even eliminate this gap? The bottleneck is the time to maintain the information associated with
the various components of HP (U ). It is conceivable that the special structure of this graph and the way the
deletions are performed could be used to our advantage. A second question is how well our algorithm performs in practice. To investigate this, it should be possible to leverage existing knowledge on the empirical
behavior of dynamic connectivity data structures [12].

References
[1] A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from lowest common ancestors
with an application to the optimization of relational expressions. SIAM J. Comput., 10(3):405–421,
1981.
[2] B. R. Baum. Combining trees as a way of combining data sets for phylogenetic inference, and the
desirability of combining gene trees. Taxon, 41:3–10, 1992.
[3] O. R. P. Bininda-Emonds, M. Cardillo, K. E. Jones, R. D. E. MacPhee, R. M. D. Beck, R. Grenyer,
S. A. Price, R. A. Vos, J. L. Gittleman, and A. Purvis. The delayed rise of present-day mammals.
Nature, 446:507–512, 2007.
[4] D. Bryant and J. Lagergren. Compatibility of unrooted phylogenetic trees is FPT. Theoretical Computer Science, 351:296–302, 2006.
[5] P. Buneman. A characterisation of rigid circuit graphs. Discrete Math., 9:205–212, 1974.
[6] B. Courcelle. The monadic second-order logic of graphs I. Recognizable sets of finite graphs. Inf.
Comput., 85(1):12–75, 1990.
[7] S. Even and Y. Shiloach. An on-line edge-deletion problem. J. ACM, 28(1):1–4, Jan. 1981.
[8] S. Grünewald, M. Steel, and M. S. Swenson. Closure operations in phylogenetics. Mathematical
Biosciences, 208:521—537, 2007.
[9] M. R. Henzinger, V. King, and T. Warnow. Constructing a tree from homeomorphic subtrees, with
applications to computational evolutionary biology. Algorithmica, 24:1–13, 1999.

11

[10] C. E. Hinchliff, S. A. Smith, J. F. Allman, J. G. Burleigh, R. Chaudhary, L. M. Coghill, K. A. Crandall,
J. Deng, B. T. Drew, R. Gazis, K. Gude, D. S. Hibbett, L. A. Katz, H. D. Laughinghouse IV, E. J.
McTavish, P. E. Midford, C. L. Owen, R. H. Reed, J. A. Reesk, D. E. Soltis, T. Williams, and K. A.
Cranston. Synthesis of phylogeny and taxonomy into a comprehensive tree of life. Proceedings of the
National Academy of Sciences, 2015. In press.
[11] J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms
for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723–760, July
2001.
[12] R. Iyer, D. Karger, H. Rahul, and M. Thorup. An experimental study of polylogarithmic, fully dynamic,
connectivity algorithms. J. Exp. Algorithmics, 6, Dec. 2001.
[13] I. Pe’er, T. Pupko, R. Shamir, and R. Sharan. Incomplete directed perfect phylogeny. SIAM J. Comput.,
33(3):590–607, 2004.
[14] M. A. Ragan. Phylogenetic inference based on matrix representation of trees. Molecular Phylogenetics
and Evolution, 1:53–58, 1992.
[15] M. J. Sanderson. Phylogenetic signal in the eukaryotic tree of life. Science, 321(5885):121–123, 2008.
[16] C. Semple and M. Steel. Phylogenetics. Oxford Lecture Series in Mathematics. Oxford University
Press, Oxford, 2003.
[17] M. A. Steel. The complexity of reconstructing trees from qualitative characters and subtrees. J.
Classification, 9:91–116, 1992.

12

