Computing the Local Consensus of Trees.
The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for inferring this consensus have been proposed. In this paper we present a model for deriving what we call a local consensus tree T  from a set of trees ${\cal T}$. The model we propose presumes a function f, called a  total local consensus function, which determines for every triple A of species, the form that the local consensus tree should take on A. We show that all local consensus trees, when they exist, can be constructed in polynomial time and that many fundamental problems can be solved in linear time. We also consider partial local consensus functions and study optimization problems under this model. We present linear time algorithms for several variations. Finally we point out that the local consensus approach ties together many previous approaches to constructing consensus trees.
Introduction
An evolutionary tree (also called a phylogeny or phylogenetic tree) for a species set S is a rooted
tree with leaves labeled by distinct elements in S. Because evolutionary history is difficult
to determine (it is both computationally difficult as most optimization problems in this area are
NP-hard, and scientifically difficult as well since a range of approaches appropriate to different
types of data exist), a common approach to solving this problem is to apply many different
algorithms to a given data set, or to different data sets representing the same species set, and
then look for common elements from the set of trees which are returned.
Several methods are described in the literature for deriving one tree from a set of trees.
In this paper, we propose a new model, called the local consensus. This model is based upon
functions, called local consensus rules, for inferring the rooted topology of the homeomorphic
subtree induced by triples of species. We will show that any local consensus function can be
Supported in part by NSF grant CCR-9108969.
y Supported in part by ARO grant DAAL03-89-0031PRI
z Supported in part by ARO grant DAAL03-89-0031PRI
computed in polynomial time, and that many of the natural forms of the local consensus can
be computed in linear time. We also analyze optimization problems based upon partial local
consensus rules and show that many of these can also be solved in polynomial time.
Preliminaries
2.1 Definitions Let be a set of species. An evolutionary tree for S (also
known as a phylogenetic tree or, more simply, a phylogeny) is a rooted tree T with n leaves
each labeled by a distinct element from S. The internal nodes denote ancestors of the species in
S. For an arbitrary subset S 0 ae S we denote by TjS 0 the homeomorphic subtree of T induced
by the leaves in S 0 . In particular, for a specified triple fa; b; cg ae S we denote by Tjfa; b; cg
the homeomorphic subtree of T induced by the leaves labeled by a; b; and c. This topology is
completely determined by specifying the pair of species among a; b and c whose least common
ancestor (lca) lies furthest away from the root. If (a; b) is this pair then we denote this by
((a; b); c), and T is said to be resolved on the triple a; b; c. If T is not binary it may happen
that all three pairs of species have the same least common ancestor. In this case we will say that
is unresolved in T and denote this topology by (a; b; c).
Given a tree T containing nodes u; v; w, we let lca T (u; v; w) denote the least common ancestor
of u; v and w in T . Also, we let u - T v denote that v is on the path from u to the root of T .
The set of input trees fT to a consensus problem is sometimes referred to as the
profile.
Let T (a; b; c) represent the set of rooted subtrees on the leaf set fa; b; cg. A local consensus
rule is a function Given a local consensus rule f and a set R of
evolutionary trees for S, the f-local consensus (if it exists) is a tree R f such that for all triples
A ' S, R f
When is said to be a total local consensus, and otherwise f is said
to be a partial local consensus. The problem of determining if the f-local consensus exists and
constructing it if it does is called the f-local consensus problem.
We will also consider optimization versions of the local consensus problem which will be
discussed in subsequent sections. Having set up this general machinery, we will look at the
special case where we need to build a consensus of two trees and describe specific local consensus
functions f for which we produce efficient algorithms.
2.2 Particular Local Consensus Rules We define the Binary Local Consensus, Optimistic
Local Consensus and Pessimistic Local Consensus problems below. The Binary Local Consensus
problem takes as input two binary trees, whereas the Optimistic Local Consensus and Pessimistic
Local Consensus problems take as input two trees which are not necessarily binary. All of these
are examples of total local consensus rules.
Definition 2.1. A local consensus rule f is conservative if for every triple fa; b; cg for
which T jfa; b; cg is required to be resolved for a particular profile, then no tree in the profile
resolves fa; b; cg differently from T .
When the trees are not necessarily binary, the local consensus rule has to interpret an
unresolved triple in one of two distinct ways: supposing that any resolution of the three way split is
possible or supposing that the unresolved node represents a three-way speciation event. Depending
upon the interpretation, therefore, the local consensus rule may decide if T 1 is resolved and T 2
is unresolved on some triple, the output should be resolved identically to T 1 or unresolved. We
call the first type of local consensus rule optimistic and the second type pessimistic.
We now define these three consensus rules.
Definition 2.2. Let T 1 and T 2 be two rooted binary trees on the same leaf set S. A rooted
tree T (which is not necessarily binary) is called the binary local consensus of T 1 and T 2 iff
for all triples a; b; c, T jfa; b;
Definition 2.3. Let T 1 and T 2 be two rooted trees on the same leaf set S. A rooted
tree T is called the optimistic local consensus of T 1 and T 2 iff for each triple a; b; c,
c) or (a; b; c) for
Definition 2.4. Let T 1 and T 2 be two rooted trees on the same leaf set S. A rooted
tree T is called the pessimistic local consensus of T 1 and T 2 iff for each triple a; b; c,
These differences are each appropriate for particular types of data.
Given the above definitions of the three models, the local consensus tree may not exist. In
Sections 3, 4, and 5, we will give linear time algorithms that either construct the tree we are
looking for if it exists or conclude that no such tree exists. However, practicing biologists and
linguists need to build some kind of consensus tree, and we therefore have considered variants
of the local consensus tree problem which always have solutions. To this end, we will define the
notion of relaxed-accord local consensus and relaxed-discord local consensus as follows.
Definition 2.5. Let T 1 and T 2 be two rooted binary trees on the same leaf set S. A rooted
tree T (which is not necessarily binary) is called a relaxed-accord local consensus of T 1 and
whenever a triple a; b; c has differing topologies on T 1 and T 2 , that triple is unresolved in T
and T preserves the topology of a maximal set of triples on which T 1 and T 2 agree.
To prove the existence of a relaxed-accord local consensus tree it is sufficient to show that
there exists a tree where every triple on which T 1 and T 2 disagree is unresolved. The set of trees
with this property can be partially ordered based on the set of triples (on which T 1 and T 2 agree)
whose topology they preserve. Once this partial order is known to be non-empty, we have proved
the existence of a relaxed-accord local consensus since any maximal element in this partial order
is such a consensus tree.
We note that if T has the star topology it leaves unresolved all triples on which T 1 and T 2
disagree. Hence the partial order is non-empty and the relaxed-accord local consensus tree always
exists. In Section 6 we show that this tree is unique.
Definition 2.6. Let T 1 and T 2 be two rooted trees (not necessarily binary) on the same leaf
set S. A rooted tree T is called a relaxed-discord local consensus of T 1 and T 2 if T preserves
the topology of all triples on which T 1 and T 2 agree. In addition, T should leave unresolved a
maximal set of triples on which T 1 and T 2 disagree.
Using an argument similar to the one used to prove the existence of a relaxed-accord local
consensus and noting that T 1 (or preserves the topology of all triples on which T 1 and
agree, we conclude that the relaxed-discord local consensus always exists. In Section 6 we
show that the relaxed-discord local consensus is also unique.
Before we look further into the problems, we give some standard definitions available in the
literature.
Definition 2.7. Let T be a rooted tree with leaf set S. Given a node v 2 V (T ), we denote
by L(T v ) the set of leaves in the subtree T v of T rooted at v. This is also called the cluster at v,
and is represented by ff v . The set C(T is called the cluster encoding of T .
Every rooted tree in which the leaves are labeled by S contains all singletons and the entire set
S in C(T ); these clusters are called the trivial clusters. We define a maximal cluster to be
the cluster defined by the child of the root. (Here we allow for a maximal cluster to be defined
by a leaf also.)
We also define the notion of compatibility of a set of clusters.
Definition 2.8. A set A of clusters is said to be compatible iff there exists a tree T such
that C(T
The following proposition can be found in [12].
Proposition 2.1. A set A of clusters is compatible iff 8ff ;g.
We now state a theorem which will be used in the later sections.
Theorem 2.1. Let T 1 and T 2 be two rooted trees on the same leaf set S and let f be a
conservative local consensus rule. If the f-local consensus tree T exists, then C(T
are compatible sets.
Proof. Suppose not and suppose without loss of generality that C(T ) [ not a
compatible set. Then by Proposition 2.1, 9ff 2 C(T ) and fi 2 C(T 1 ) such that ff "
;g.
Pick a ff. The topology of the triple a; b; c in T 1 is ((a; c); b)
while in T it is ((a; b); c). Since f is a conservative local consensus rule, this is impossible. 2
3 Binary Local Consensus
In this section, we will look at the Binary Local Consensus problem. We start by restating
the definition of the binary local consensus tree : Let T 1 and T 2 be two rooted binary trees
on the same leaf set S. A rooted tree T (which is not necessarily binary) is called the
binary local consensus of T 1 and T 2 iff for all triples a; b; c, T jfa; b;
3.1 Characterization and construction We will show that althought the binary local
consensus of two trees may not exist, when it does exist it has a nice characterization.
Proposition 3.1. Given a binary tree T and a cluster ff, ff is compatible with C(T ) iff
Proof. If ff 62 C(T ) but ff is compatible with C(T ), then there exists a proper refinement T 0
of T such that C(T 0 binary tree has a proper refinement. 2
Lemma 3.1. Let T 1 and T 2 be rooted binary trees on the same leaf set S. If f is
a conservative local consensus function such that the f-local consensus tree T exists, then
Proof. By the previous lemmas, C(T since f is conservative, and
Corollary 3.1. If the binary local consensus tree T of T 1 and T 2 exists (T 1 and T 2 are both
binary), then C(T
Proof. All we need to show is that ff 2 C(T ) for all ff 2 C(T 1 For any such ff, pick
identically, so that T also resolves
The tree T such that C(T called the strict consensus tree. This particular
consensus tree always exists and can be constructed in O(n) time [6]. The construction part of the
algorithm for binary local consensus trees is therefore simple, and what remains is the verification
that the strict consensus tree is also the binary local consensus tree (i.e. that the tree we have
constructed using the algorithm in [6] satisfies the constraints imposed upon it by the binary
local consensus rule).
3.2 Verifying that a Consensus Tree is a Binary Local Consensus Tree We now prove
some structural lemmas to help determine whether the consensus tree is in fact the binary local
consensus.
Lemma 3.2. Let T 1 and T 2 be rooted binary trees on the same leaf set and let ff be a cluster
in their intersection. Let T be the strict consensus tree of T 1 and T 2 . Let e 1 e be the
edges in T respectively that are above the respective internal nodes which define the
cluster ff. Let a be a species in ff. Then T is a binary local consensus for T 1 and T 2 if and only
if
1. the subtree below e is a binary local consensus for the subtrees below e 1 and e 2 , and
2. upon replacing the subtrees below by a in T; respectively, T is a
binary local consensus for T 1 and T 2 .
Proof. Clearly, if T is the binary local consensus tree for T 1 and T 2 then conditions (1) and
(2) will hold. Conversely, if (1) and (2) holds, but T is not the binary local consensus tree for T 1
and T 2 , then there is some triple a; b; c such that T incorrectly handles this triple. If all of a; b; c
are below e then by condition (1), T handles a; b; c correctly. Similarly if at least two are above
e, then by condition (2), T handles this triple correctly. It remains to show that T handles all
triples where exactly two of a; b; c are below and one is above the edge e. But then, since the
cluster in each of T
this triple properly. Thus T is a binary local consensus for T 1 and T 2 . 2
This lemma yields an obvious divide-and-conquer strategy to determine whether a binary
local consensus exists.
Next we explore for what pairs of binary trees it is possible for the binary local consensus to
be a star, i.e., a tree with none but the trivial clusters.
Definition 3.1. A caterpillar is a rooted binary tree with only one pair of sibling leaves.
Given a leaf labeled caterpillar T with root r and height h, there is a natural ordering induced
by T on its leaves. Let hg be a function where g(s) is the distance of s from r.
Then the species in S can be ordered in the increasing order as a 1 ; a
such that g(a 1 (Note that the pair of sibling leaves have been
arbitrarily ordered)
Definition 3.2. Two caterpillars X and Y on the same leaf set are said to be oppositely
oriented iff for all k, the k smallest elements of X are contained among the k+1 largest elements
of Y and vice versa.
Proposition 3.2. Let T 1 and T 2 be two rooted binary trees on the same leaf set whose binary
local consensus is a star. If a; b is a sibling pair of leaves in T 1 , then the lca of a and b in T 2
must be the root of T 2 .
Proof. Suppose not. Then there is a species c such that the least common ancestor of (a; c)
is above the least common ancestor of (a; b) in T 2 . Then T 1 jfa; b; hence the
binary local consensus of T 1 and T 2 cannot be a star. 2
Lemma 3.3. Suppose T 1 and T 2 are binary trees on the same leaf set and suppose that they
each have at least 5 leaves. If their binary local consensus tree is a star, then T 1 and T 2 must be
caterpillars.
Proof. Suppose for contradiction that T 1 is not a caterpillar. Then it has two pairs of sibling
leaves, (a; b) and (c; d). By the previous proposition each of these pairs must have the root as
their least common ancestor in T 2 . Thus without loss of generality, a and c lie in the left subtree
of the root of T 2 and b and d lie in the right subtree of the root of T 2 . Thus it follows that T 2
itself must have two sibling pairs (p; q) and (r; s) one in each subtree of the root. Note that in
1 the least common ancestor of p and q and the least common ancestor of r and s is the root
of T 1 . Again without loss of generality let p and r lie in the left subtree of the root of T 1 and q
and s lie in the right subtree of the root.
x can be in either of the subtrees of T 1

Figure

1: Topologies of T 1 and T 2 with respect to p; q;
Let x be any other species besides p; q; Figure 1). Suppose without loss of
generality that x lies in the left subtree of the root of T 2 . We will consider the following two
triples: In T 2 the topology of these triples will be ((x; p); s) and ((x; q); r)
respectively.
We will show that T 1 agrees on at least one of these triples. There are two cases. If x lies in
the left subtree of the root of T 1 , then the topology of the triple x; p; s in T 1 is clearly ((x; p); s)
and if x lies in the right subtree of the root of T 1 , then the topology of the triple x; q; r in T 1
is ((x; q); r). Thus in either case there is a triple in T 1 which agrees with a triple in T 2 and the
binary local consensus cannot be a star. 2
Lemma 3.4. Let T 1 and T 2 be two caterpillars on the same leaf set. Then the binary local
consensus of T 1 and T 2 is a star if and only T 1 and T 2 are oppositely oriented caterpillars.
Proof. Suppose the two caterpillars are oppositely oriented, i.e., they satisfy the two
intersection conditions. Let x; z be any three leaves and let their indices in the ordering
of the leaves of T 1 be respectively. Then the topology of x; and z in T 1 is (x; (y; z)).
Looking at the smallest elements in T 2 , this set must contain y or z but cannot contain x.
Consequently, the topology of the triple in T 2 is not (x; (y; z)) and the star is a valid binary local
consensus.
Conversely, suppose that the two caterpillars do not satisfy the intersection conditions.
Without loss of generality, suppose that there exists at least one k such that the k smallest
elements of T 2 are not contained within the largest elements of T 1 . Pick the smallest such
k. Say, x is the leaf in T 2 with rank k and x does not belong to the set of k largest elements
of T 1 . From the pigeonhole principle, there will exist at least two leaves of T 2 which have ranks
greater than k but which are contained in the set of k largest elements of T 1 . Suppose the
two leaves are y and z. Then T 1 jfx; This implies that the binary
local consensus cannot be a star. 2
a b
c
d
e
f
d
c
a

Figure

2: Example of oppositely oriented caterpillars
Corollary 3.2. The binary local consensus for two trees can be verified to be a star in
linear time.
3.3 Binary Local Consensus Tree Algorithm
1. Use Day's algorithm to produce the strict consensus tree T and for each non-trivial cluster
in T , maintain a pointer to the edges in T 1 and T 2 that give rise to this cluster.
2. Traverse T in postorder. For each non-trivial cluster found, check that the subtrees below
its edge in T 1 and T 2 are caterpillars that satisfy the conditions of the above lemma. If so
replace the entire subtree by a single node belonging to the subtree in each of T 1 and T 2 .
If not, declare that T is not the binary local consensus tree.
Theorem 3.1. Construction and verification for the binary local consensus can be done in
linear time.
Proof. Day's algorithm [6] runs in linear time. Also, step 2 of the above algorithm takes linear
time since at most a linear number of species are reintroduced by replacement above. Also, the
checking of the caterpillars can be done in time linear in the number of leaves in the caterpillar.4 Optimistic Local Consensus
In this section we look at the problem of finding the Optimistic Local Consensus (OLC) tree of
two trees defined in the previous section. Note that the Optimistic Local Consensus of two trees
may not exist.
Recall the definition of the OLC tree : Let T 1 and T 2 be two rooted trees on the same leaf
set S. A rooted tree T is called the optimistic local consensus of T 1 and T 2 iff for each triple
c) or (a; b; c) for
4.1 Characterization of the OLC tree The following lemma characterizes the optimistic
local consensus tree when it exists:
Theorem 4.1. Let T 1 and T 2 be two rooted trees on the same species set S. If the optimistic
local consensus tree T olc exists, then C(T olc
and ff 2 2 C(T 2 ), and ff   is compatible with both C(T 1 ) and C(T 2 )g.
Proof. Pick any cluster ff 2 A. If we look at any triple x;
then this triple will be resolved as ((x; y); z) in one tree and will be either resolved the same or
unresolved in the other tree. In either case, ff 2 C(T olc ).
Conversely, pick any cluster
A. There are two cases here, namely, the case when ff is not
compatible with at least one of C(T 1 ) and C(T 2 ) and the case when ff is compatible with both
when ff is not compatible with at least one of C(T 1 ) and C(T 2 ), using Theorem 2.1, we
observe that
For the second case, pick those smallest clusters ff 1
. (Note that the nodes v and u defining the clusters ff 1 and ff 2 respectively,
are the lcas in T 1 and T 2 respectively, of the species in ff.) Then 9fi ' ;, such that
are the smallest clusters in T 1 and T 2 respectively containing
ff and since ff is compatible with both C(T 1 ) and C(T 2 ), this implies that ff is the union of
clusters of at least two children of v and also the union of clusters of at least two children of u.
Moreover, 9a; b 2 ff such that
(a; b) and
(a; b). Thus we can pick a c 2 fi and
we have that T 1 jfa; b; c). But the topology given by T olc is ((a; b); c).
Thus
4.2 Construction phase Since the optimistic local consensus rule is conservative, if the tree
set of clusters, and hence there exists a tree T
satisfying C(T   If we can construct T   by refining T 1 , we can then reduce
T   by contracting all the unnecessary edges, and thus obtain T olc . This is the approach we will
take.
Note that this approach breaks the construction into two stages: refinement and contraction.
Refining
The main objective is to refine T 1 so as to include all the clusters from T olc . Before we explain
how we do this precisely, we will introduce some notation and lemmas from previous works which
enable us to do this efficiently.
Definition 4.1. Let v be an arbitrary node in a tree T with children
representative set of v is any set fx 1 such that x
. We denote by rep(v)
one such representative set.
Lemma 4.1. If the optimistic local consensus tree T olc of trees T 1 and T 2 exists and
then T olc jrep(v) is isomorphic to T 2 jrep(v).
Proof. Follows from the fact that T 1 jrep(v) is a star. 2
Definition 4.2. Let v be a node in a tree T with children is the
subtree induced by fv; g.
We will do the refinement as follows. We will modify the tree T
1 is initialised to
In a postorder fashion, for every
It can be seen that v   also has the same number of children as v (since the
processing is done in a postorder fashion). Say these are . Replace the subtree
(v   ), rooted at v   in the following manner : We replace N(v   ) by an isomorphic copy of
Next, we replace x i by the subtree of T
1 rooted at u i .
Let T   be the tree that is produced after considering all the nodes in T 1 .
Theorem 4.2. Let T be given and suppose T olc exists. Then the tree T   that is produced
from the algorithm described in the previous paragraph satisfies C(T
Proof. Since C(T olc all we need to show is that T olc jrep(v) cannot be a
proper refinement of T 2 jrep(v). If it were, then for some fa; b; cg ' rep(v), T olc jfa; b; cg would be
resolved while T 2 jfa; b; cg is unresolved. Since fa; b; cg ' rep(u), T 1 jfa; b; cg is also unresolved,
forcing T olc to be also unresolved. 2
Note that we have reduced the problem of constructing T   to the problem of discovering
To have a linear time algorithm, however, we need to be able to compute T 2 jrep(v) quickly.
We cite the following result from [13] which will be useful to us in this case.
Lemma 4.2. [13] Given a left-to-right ordering of the leaves of a tree and the ability to
determine the topology of any triple of leaves a; b; c in constant time, we can construct the tree
in linear time.
To use this lemma we need two things:
1. that we be able to determine the topology of any triple in T 2 in O(1) time, and
2. that we have for each node in T 1 , an ordered representative set, where the ordering is
consistent with the left-to-right ordering of the leaves in T 2 .
To accomplish (1), we first preprocess T 2 for lca queries. Then, to determine the topology for
the triple a; b; c, we simply compare the lca's of (a; b), (b; c) and (a; c). The second requirement
is more challenging, but can also be handled, as we now show.
Computing all ordered representative sets in O(n) time:
ffl Initially all nodes in T 1 have empty labelings.
ffl For each s 2 S, taken in the left-to-right ordering of the leaves in T 2 , do
1. Trace a path in T 1 from the leaf for s towards the root, until encountering either the
root or a node which has already been labeled.
2. Append s to the ordered set for each such node in the path traced (including the first
node encountered which has already been labeled).

Figure

3 shows an example of the computation just described.
a b c d
e
a b c d
e
a b c d
e
c is added to rep sets of w and v
Left-to-right ordering
a c d b e
a c
d
r
a is added to rep sets of u, v and r
(iv) After completion

Figure

3: Example showing the computation of the representative sets of nodes in T 1 based on
the left-to-right ordering of species in T 2
Note that this computation takes O(n) time since each node v is visited O(deg(v)) times, and
that the order produced is exactly as required. Thus, for each node v 2 V (T 1 ), we have defined
a set of leaves such that each leaf is in a different subtree of v, every subtree of v is represented,
and the order in which these leaves appear is the same as the left-to-right ordering in T 2 .
We have thus proved:
Lemma 4.3. We can compute T 2 jrep(u) in O(jrep(u)j) time.
We therefore have the following:
Theorem 4.3. Given then we can construct a tree T   such that C(T
exists in O(n) time.
The rest of the task of constructing T olc is in the contraction of unneeded edges.
Contracting simply go through each
edge in T   and check if it needs to be kept or must be deleted. Note that edges that were added
during the refinement phase are required and do not need to be checked. Therefore we need
only check the original tree edges. Let (u; v) be such an edge with From our
representative sets for u and v we can easily choose three species a; b; c such that lca(a;
and lca(b; c) = v. If the topology of this triple in T 2 is differently resolved than ((a; b); c) then
we know that edge (u; v) will have to be contracted; if on the other hand T 2 jfa; b; cg is either
(a; b; c) or ((a; b); c) then (u; v) will have to be retained in any optimistic local consensus tree.
OLC Construction Algorithm
Phase 0: Preprocessing:
Make copies T 0
2 of T 1 and T 2 respectively. For each node v in each tree T 0
compute ordered representative sets ordered by the left-to-right ordering in the other tree.
Preprocess each tree T 0
i to answer lca queries for leaves as well as internal nodes.
Phase I: Refine T 0Refine T 0
1 in a postorder fashion so that at the end, C(T 0
exists.
Phase II: Contract T 0Contract edges e 2 E(T 0
1 ) such that c e , the cluster below e, lies in C(T 1
We have thus shown the following theorem
Theorem 4.4. The algorithm stated above constructs the OLC of two trees T 1 and T 2 if the
OLC exists.
Analysis of Running Time
Phase 0: Preprocessing:
In [18], Harel and Tarjan give an O(n) time algorithm for preprocessing trees to answer lca
queries in constant time. We have already shown that computing the ordered representative sets
takes O(n) time. Thus the preprocessing stage takes O(n) time.
Phase I: Refining T 0This stage involves local refinements of T 0
1 , and we have shown that the cost of refining around
node v is O(deg(v)). Summing over all nodes v we obtain O(n) time.
Phase II: Contracting edges
This stage clearly takes only O(n) time.
Theorem 4.5. Construction of the optimistic local consensus tree can be done in linear time.
4.3 Verification phase
Lemma 4.4. Let T be a tree on a leaf set S. Let T   be obtained from T through a
sequence of refinements followed by a sequence of edge contractions. Then there exists a function
there is a subset S v of the children of f(v) in
Proof. We define set of clusters.
Therefore there is a subset S v of the children of f(v) such that [ v 0 2Sv ff v
Lemma 4.5. Suppose T is the OLC of T 1 and T 2 (on a leaf set S containing at least 5 species).
Then T is a star iff either one of the following holds
1. both T 1 and T 2 are oppositely oriented caterpillars, or
2. both T 1 and T 2 are stars
Proof. The "if" direction is easy to see. We now assume that the OLC, T , is a star. If
contains a triple a; b; c that is unresolved, T 2 must also be unresolved on a; b; c. Conversely
whenever T 1 is resolved on a; b; c, T 2 must be (differently) resolved on a; b; c. Thus either both
are binary or both are not.
In the case that both T 1 and T 2 are binary, the definition of the OLC coincides with the
definition of binary local consensus and we appeal to the proofs of Lemma 3.3 and Lemma 3.4
to argue that T 1 and T 2 must be oppositely oriented caterpillars.
are not binary, we will show that for any node v in T 1 with children fu
there is a node v 0 in T 2 with children fu 0
k g such that ff u i
. Pick any three
species a; b; c such that a; b; c is unresolved in T 1 and let
(a; b; c). Then a; b; c must
be unresolved in T 2 . Let v
(a; b; c). We claim that ff To see why, suppose
being in the same subtree under v as a. Then
This contradicts the assumption that T
is a star. Thus ff
Next, note that if x and y are under the same child of v in T 1 but under different children of
there exists a z such that x; y; z is resolved in T 1 but unresolved in T 2 . This would
contradict the fact the T is a star. This establishes the claim.
This implies that if there is a non-binary node v that is not the root of T 1 , we can find two
species a; b (a - v; b - v) and a species c, c 6- v such cg. Thus the root
must have three or more children in this case. But this means that if any cluster defined by a
child of the root contains two or more species, then there is a triple on which T 1 and T 2 agree.
Thus T 1 and T 2 must be stars. 2
The verification proceeds as follows :
Phase 0
Suppose the tree constructed by refining T 1 and then contracting the edges in the resulting
tree is T . We will do the same modification on T 2 , i.e. refine T 2 using the information from T 1
and then contract the edges in the resulting tree as before. Call this tree T 0
. Clearly, if T is not
isomorphic to T 0
, we can terminate and output that the OLC does not exist. This is because
we know that a compatible set of clusters defines a unique tree and we know that the OLC, if it
exists, is uniquely characterized.
Phase 1
If Phase 0 is successful, we then verify further. We compute an ordered representative set for
every node w in V (T ). For each node w in T , do
1. Check if the homeomorphic subtrees of T 1 and T 2 induced by rep(w) are both stars or they
are both oppositely oriented caterpillars. If they are neither of these, then terminate and
output that the OLC does not exist.
2. Identify the parent of w, say w   . Look at rep(w   ) excluding the representative element
which is below w. Call this set A. Identify the lca's of rep(w) in T 1 and T 2 . Check if there
is a species that belongs to A which lies below the lca of rep(w) in both T 1 or T 2 . If so,
terminate and output that the OLC does not exist.
Implementation of step 1 of Phase
Using the left-to-right ordering of the species in T 1 , compute the ordered representative set rep,
at each node in T as shown in the previous section. For any u 2 V (T ), to be able to quickly
compute the homeomorphic subtree of T 2 induced by the species in rep(u), we need to know the
ordering of theses species as they appear in the left-to-right ordering of T 2 . We associate with
each u, a new rep set, rep   (u), which is the rearranged version of the species in rep(u) according
to their ordering in T 2 . We define a specifies for each s 2 S,
the node v 2 V (T ) closest to the root of T such that s 2 rep(v). The function limit together
with the left-to-right ordering of the species in T 2 , help in filling the rep   sets, since, s will belong
to the rep   sets of all nodes in the path from s to limit(s). We first show how to compute
using algorithm LIMIT and then we show how the rep   sets are filled.
Initialisation
For each visited in a top-down traversal of T ,
do f
For each s 2 rep(v) such that
set
Once limit(s) has been identified for all s 2 S, we proceed to compute rep   (u);
as follows. Look at the left-to-right ordering of the species in T 2 . Now, for each species s in the
left-to-right order, we trace a path in T from the leaf for s towards the root of T and add s to
the rep   set of each node encountered in this path. We terminate when we reach limit(s).
Note that this process of identifying rep and rep   has to be done only once.
Analysis of running time :
The isomorphism test in Phase 0 can be performed in O(n) using a simple modification of the
tree-isomorphism testing algorithm in [1].
There is an O(n) cost for preprocessing of T 1 and T 2 to answer lca queries in Phase 1.
Our implementation of step 1 of Phase 1 involves a one time O(n) cost in preprocessing to
identify rep and rep   for each node in T . Then each time step 1 is called on a node w
an additional time of O(deg(rep(w))) is taken.
Exploiting that fact that T 1 and T 2 have been preprocessed to answer lca queries, it can be
seen that each step 2 of Phase 1 takes O(deg(w)
Thus the total time taken in the verification phase is O(n).
Correctness of our verification procedure :
Theorem 4.6. If T passes the above tests, then T is the OLC of T 1 and T 2 .
Proof. We need only show that T handles every triple properly. Each of the following cases
is handled assuming T has passed the isomorphism test.
Case 1
If T passes the isomorphism test with T 0
, then any triple a; b; c such that the two trees resolve
differently, will be unresolved in T . This follows since T is created by refining and then
contracting both T 1 and T 2 , and these actions can not take a resolved triple into a different
resolution.
Case 2
This involves a triple a; b; c having the same topology ((a; b); c) in both T 1 and T 2 . We claim
that the first step of Phase 1 will pass only if the topology of this triple is ((a; b); c). To see why,
suppose a; b; c is unresolved in T . ( a; b; c cannot be resolved as (a; (b; c)) or ((a; c); b) in T .) Look
at the nodes u and v, which are the lca's of a; b in T 1 and T 2 , respectively. The node w in T ,
which is the lca(a; b; c), is also lca(a; b) (since a; b; c is unresolved). We infer that
f is the function as defined in Lemma 4.4. This is because, any node above w will contain the
species c and any node below w will not contain either a or b. By a similar argument,
Now, when we look at rep(w) and compute the homeomorphic subtrees of T 1 and T 2 induced by
rep(w), in both of these induced trees, there will exist three species x; z such that x; y are both
below u (and v) in T 1 (and T 2 ) and z is not in the character defined by u (and v). Thus in both
the induced trees, the triple x; will have the same topology ((x; y); z). That is, these induced
trees will neither be both stars nor both oppositely oriented caterpillars. Thus the verification
process will terminate and output that the OLC does not exist.
Case 3
This involves a triple a; b; c which is resolved as ((a; b); c) in one tree and unresolved in the
other. The proof of this case essentially follows the lines of the proof of case 2.
Case 4
This involves a triple a; b; c which is unresolved in both the trees. We claim that the second
step of Phase 1 will pass only if this triple is unresolved in T . To see why, suppose a; b; c is
resolved as ((a; b); c) in T . Let lca T (a; b; c) = x and let lca T (a; y and also suppose without
loss of generality that x is the parent of y. Let y 1 be the child of y such that a 2 ff y 1
and let y 2
be the child of y such that b 2 ff y 2
. Let z 6= y be the child of x such that c 2 ff z .
Let
(a; b; c) and
(a; b; c).
We will look at functions f 1 and f 2 defined by Lemma 4.4 from V (T ) to V (T 1
respectively. v. Note that the cluster defined by any child of u
can have a non-empty intersection with at most one of ff y 1
and ff y 2
. Similarly for v. Thus any
representatives chosen from ff y 1
and ff y 2
respectively, have their least common ancestor at u in
1 and at v in T 2 . However, f 1 (z) - T 1
v. Thus any representative chosen from
ff z will lie below u and v in T 1 and T 2 respectively, causing us to conclude that the OLC does
not exist. 2
5 Pessimistic Local Consensus
Recall the definition of the Pessimistic Local Consensus be two rooted
trees on the same leaf set S. A rooted tree T is called the pessimistic local consensus of T 1
and T 2 iff for each triple a; b; c, T jfa; b;
5.1 Characterization The following theorem characterizes the PLC tree of two trees T 1 and
Theorem 5.1. Let T 1 and T 2 be two trees on the same leaf set S. If the pessimistic
local consensus tree T plc of T 1 and T 2 exists, then it is identically equal to T , where C(T
Proof. Pick any cluster ff 2 C(T ). Since ff belongs to both the trees, if we look at any triple
ff, then this triple will have to be resolved as ((x; y); z). Thus
Conversely, pick any cluster
We have two subcases here
1. ff is not compatible with at least one of C(T 1 ) or C(T 2 ). In this case, from Theorem 2.1,
2. ff is compatible with both C(T 1 ) and C(T 2 ). In this case, pick those nodes from T 1 and
which define the smallest clusters containing ff. We can pick a triple a; b; c, such that
a
ff and this triple is unresolved in either T 1 or T 2 . Thus
Construction Phase By Theorem 5.1, the pessimistic local consensus tree, if it exists,
is identically the strict consensus tree. Thus to construct the pessimistic local consensus tree, it
suffices to use the O(n) algorithm in [6] for the strict consensus tree.
5.3 Verification Phase Let T 1 and T 2 be the input trees, and let T be the strict consensus
tree constructed using the algorithm in [6]. We want to be able to verify whether T is actually
the pessimistic local consensus in the case that T is a star. If T 1 or T 2 is already a star then
there is nothing to verify since T is the true pessimistic local consensus. So assume that this is
not the case.
There are two cases which we will consider. The first is when either of T 1 or T 2 (say T 1 ) has
at least two children of the root which are not leaves. The second case is when both T 1 and T 2
have exactly one child of the root which is not a leaf. Having made observations about these
cases, we can apply the divide and conquer strategy we adopted for the binary local consensus
problem.
Lemma 5.1. Suppose T 1 and T 2 are two trees on the same leaf set S, with T 1 having at least
two children of the root which are not leaves. Let ff 1 ; ::; ff l be the maximal clusters of T 1 and
be the maximal clusters of T 2 . Then T , their pessimistic local consensus, is a star iff
Proof. Suppose 1. This means that 8x; y, if lca(x; y) in T 1 is below the root,
then in T 2 , lca(x; y) is the root. Thus for any triple x; topologies in T 1 and T 2 do not
agree. Thus T is a star.
Suppose defined by a node which is not a leaf. Look at an ff k ,
such that the node in T 1 defining ff k is not a leaf node. There are two cases to handle
here. Either, at least one species in ff k is not in fi j or all species in ff k are in fi j (i.e., ff k ae fi j ).
In the former case, pick that species z, which is in ff k but not in fi j . Also pick those two
species x; y which are in ff agree on the triple x; namely this triple
has topology ((x; y); z) in both the trees. Thus T cannot be a star.
In the latter case, since we know that fi j 6= S, we can pick two species x; y, from ff k and
another species z, from S \Gamma fi j . In both T 1 and T 2 , the topology of this triple is ((x; y); z). Thus
T cannot be a star. 2
Since each species belongs to at most one of these maximal clusters in each tree, this test can
be done in linear time.
The following lemma handles the case when both T 1 and T 2 have exactly one child of the root
which is not a leaf.
Lemma 5.2. Suppose T 1 and T 2 are two trees on the same leaf set S and T and their
pessimistic local consensus, is a star. Suppose both T 1 and T 2 have exactly one child of the
root each which is not a leaf. Let s be leaves in T 1 which are children of the root. Let v be
the lca in T 2 of s . Then every child of v contains at most one species x g.
Moreover, for any pair of species x; y g, the least common ancestor of x and y
in T 2 lies on the path from v to the root.
Proof. Suppose 9 a child of v which contains at least two species from S \Gamma fs g. Then
by picking x; y such that they both lie under this child if v in T 2 and picking an s i out of s
that lies under a different child of v, we find that both trees have the same topology for the triple
cannot be a star. Furthermore, if 9x; y such that lca(x; y)
in T 2 does not lie on the path from v to the root, then the triple x; would have identical
topologies in both trees and T wouldn't be a star. 2
Definition 5.1. A rooted tree T is a millipede if the set of internal nodes of T defines a
single path from the root to a leaf.
a b c
d

Figure

4: An example of a millipede
g. We have that T 2 jS 1 is a millipede (say, T
Let l be the children of the root in T
2 , which are leaves. Look at T 1 jS 1 , (say, T
Either, T
1 has one non-leaf child or it has at least two non-leaf children. In the former case, we
can apply the previous lemma and infer that T
will be a millipede. In the later
case, we can apply Lemma 5.2 to check if the pessimistic local consensus is a star.
In the following subsection, we will show how to verify if T is a star when both the input
trees are millipedes.
5.3.1 Verification when both the input trees are millipedes
The proof of the following lemma is straightforward.
Lemma 5.3. Suppose T 1 and T 2 are two millipedes on the same leaf set S. Then their
pessimistic local consensus, T , is a star iff there exists no triple such that both trees have the
same topologies on the triple.
We now describe a linear time algorithm for verifying that T 1 and T 2 have no triple on which
they have the same topology.
We define an ordering on the species in T 1 using the function f
distance of s from the root of T 1 ; and, h is the height of T 1 .
In T 2 , we can write S as the union of all the sets in the sequence S 1 is the
height of T 2 and each S i contains exactly those species which are at a distance i from the root
of T 2 . Now, in each S i , replace each species s in this set with f(s). Call this multiset of integers
We thus get a sequence M of multisets.
Definition 5.2. We will say a triple of integers p; q; r is special if
We observe that the pessimistic local consensus of T 1 and T 2 is a star iff no special triple p; q
and r exists.
The following algorithm CHECK PLC, takes as input the sequence M
returns FAIL if there exists a special triple of integers, and otherwise it returns PASS.
CHECK PLC works by scanning the multiset M i in the i th iteration. It makes use of three
variables global min, local min and temp. At the start of the i th iteration, global min stores
the smallest integer seen in the first multisets. The variable local min is used to store
the smallest integer a such that 9b for which a ! b and a 2 M
(local min is initialised to +1). The variable temp is initialised to 0. As long as temp remains 0,
local local min stores a and temp stores some b for which
the previously mentioned realtionship between a and b holds. At the i th iteration, CHECK PLC
either returns FAIL (if a special triple exists) or, if necessary, it modifies the variables global min,
local min and temp to hold their intended values for the first i multisets of the sequence.
The reasoning for storing these values at the start of the i th iteration is as follows. If 9p in
some i) such that p; q; r is a special triple, then global min together
with q; r 2 M i are also a special triple since global min - p. Similarly, if 9p in some M j , q 2 M l ,
i), such that p; q; r is a special triple, then local min, temp and r 2 M i are
also a special triple.
We now describe CHECK PLC.
Initialisation:
global
local
The procedure outputs FAIL (and terminates) if the pessimistic local consensus is not a star;
it outputs PASS otherwise.
For
do f
2.
do f
Scan through M i ;
If jAj - 2, then output FAIL;
If y, where y 2 A
local
global
If
do f
Scan through M i ;
If either jAj - 2 or jBj - 1, then output FAIL;
Else
If
If global min ! Min(M i ), then set local min = global min
If global min ? Min(M i ), then set local min = global min
y, where y 2 A
global
If
Output PASS
Analysis of running time : CHECK PLC runs in linear time since each M i is scanned only a
constant number of times.
Theorem 5.2. Algorithm CHECK PLC is correct.
Proof. By induction, observe that Step 1 is executed at the i th iteration if 8j; l; x, where
It then follows that if Step 1 is executed at
the i th iteration, then at the start of that iteration
local Thus, in this case global min stores the smallest integer seen in the first
multisets. Now, in the first i multisets, if any special triple p; q; r exists such that
and q; r 2 M i , then CHECK PLC correctly outputs FAIL since global min - p. Otherwise we
have two cases, depending upon the value of A. If then the variables global min, temp
and local min are updated so that global min holds the smallest value in the first i multisets.
Also, local min, now correctly holds the smallest value a for which there exists a b (stored in
temp) for which a ! b and a 2 M In the other case 0, in which
case global min is updated to hold Min(M i ) (which is the smallest value in the first i multisets).
Observe that once temp is updated to store a nonzero value, it never stores a 0 again. Thus,
once temp is set to a nonzero value in iteration i 0 , then from iteration iteration k, Step
2 is executed.
Assume that Step 2 is executed in some iteration i 0 and assume, inductively, that at the start
of iteration i 0 , global min stores the smallest value in the first i multisets and local min stores
the smallest value a for which there exists a b (stored in temp) such that a ! b and a 2 M
. Then in iteration i 0 , it can be easily seen that CHECK PLC correctly outputs
FAIL if there exist a special triple p; q; r such that
both the cases when
ensures that after iteration i 0 , global min stores the smallest value in the first i 0 multisets and
local min stores the smallest value a for which there exists a b (stored in temp) such that a ! b
and a 2 M
Using the above arguments, it can be seen that CHECK PLC gives the correct output on any
sequence of multisets. 2
Thus we also have the following theorem
Theorem 5.3. Given two millipedes T 1 and T 2 , we can check if their pessimistic local
consensus is a star in linear time.
6 Relaxed Versions
The local consensus rules we have seen so far are such that the output tree satisfying a particular
rule need not exist. This motivates the need to look at the relaxed versions of local consensus,
where solutions always exist. Recall the definitions of relaxed-accord local consensus and relaxed-
discord local consensus. The existance of solutions to these problems was shown in section 2.2.
6.1 Relaxed-Accord Local Consensus In this subsection we will show that the relaxed-
accord local consensus of two binary rooted trees T 1 and T 2 is actually the strict consensus of
these two trees.
Theorem 6.1. If T 1 and T 2 are two rooted binary trees then their relaxed-accord local
consensus T always exists, and is identically the strict consensus of T 1 and T 2 .
Proof. The existence of the relaxed-accord local consensus tree T , was shown in section 2.
Now we show that this tree is the strict consensus tree. Suppose there exists a triple a; b; c resolved
differently in T 1 and T 2 , as say, ((a; b); c) and (a; (b; c)) respectively. Say the lca T 1
neither ff u nor ff v is in the strict consensus tree. Thus the strict consensus
tree leaves unresolved any triple which has different topologies in T 1 and T 2 .
Let T 0 be a tree in which for every triple a; b; c on which T 1 and T 2 differ, T 0 has an unresolved
topology on this triple. Now suppose it is possible that T 0 contains a cluster that is not in the
intersection of the sets of clusters of T 1 and T 2 . Let ff be this cluster and suppose without loss
of generality that ff is not a cluster of T 1 . In T 0 , for any pair of species x; y 2 ff and species
z 62 ff the topology has to be ((x; y); z). However, if this is also the case in T 1 , then T 1 must
also possess the cluster ff contradicting our assumption. Thus there must exist a pair of species
and a species z 62 ff such that in T 1 their topology is not ((x; y); z). But this implies that
cannot be a relaxed-accord local consensus. Hence any candidate , T 0 , for a relaxed-accord
local consensus can only contain the clusters in the intersection of the cluster sets of T 1 and T 2 .
If T 0 contains a proper subset of the clusters in the intersection of the sets of clusters of T 1
and T 2 then there exists a triple a; b; c on which T 0 has an unresolved topology while the strict
consensus tree has a resolved topology that agrees with the topologies of T 1 and T 2 . Hence the
strict consensus of T 1 and T 2 is the relaxed-accord local consensus of T 1 and T 2 . 2
As a consequence, the relaxed-accord local consensus can be constructed in O(n) time using
the algorithm in [6], and there is no need to verify that the tree constructed is correct.
6.2 Relaxed-Discord local consensus In the relaxed-discord local consensus (RDLC)
problem we require that any triple on which the trees T 1 and T 2 agree must have its topology
preserved in the consensus tree T . Further T should leave unresolved a maximal set of triples on
which T 1 and T 2 disagree.
Previously we showed that the RDLC exists. Now we will show that it is unique. The
construction of the RDLC can be accomplished by defining the set
b)c)g. This set of rooted triples can then be passed to the algorithm of Aho
et al. [2], which computes a tree (if it exists) having the required form on every triple in the
set, and resolving a minimum number of additional triples outside that set. The algorithm in
takes O(pn) time where in our case, p 2 O(n 3 ), the use of the algorithm of
would result in a running time of O(n 4 ). We will obtain a speed-up to an O(n 2 ) algorithm
(which includes the verification) for the construction of the relaxed-discord tree, by using the
fact that the tree necessarily exists. Our algorithm however takes advantage of the ideas in [2],
and so we begin by briefly describing how that algorithm works.
6.2.1 The ASSU Algorithm
In [2], Aho et al. describe algorithms which determine if a family of constraints on least common
ancestor relations can be satisfied within a single rooted tree. We describe here the simple
algorithm they give for the case where the constraints are given as rooted resolved triples,
z). For such input the algorithm works top-down figuring out the clusters at the children
of the root before recursing. To do this the algorithm maintains disjoint sets. Initially all leaves
are in singleton sets. For each rooted triple ((x; y); z) the algorithm unions the sets containing x
and y to indicate that x and y must lie below the same child of the root. This algorithm never
unions sets unless this is forced. Recursive calls include constraints that are on species entirely
contained in the same component discovered in the previous call. If all the species are seen to
be in the same component (either initially or during a recursive call), the algorithm determines
that the constraints cannot be simultaneously satisfied. This simple algorithm has a worst case
behavior of O(pn), where there are p lca constraints and the underlying set S has n elements
which will be leaves in the final tree.
6.2.2 An improved algorithm for RDLC
We will now describe an algorithm to solve the RDLC in O(n 2 ) time. Since T 1 is itself consistent
with all triples on which they agree, it is clear that T , the tree produced by the ASSU algorithm,
is a refinement of this tree in the following sense. Each child of the root of T 1 (as well as
represents a cluster which is the union of some of the clusters represented by children of the root
of T . Let ff be the cluster of a child of the root of T 1 and let fi be a cluster of a child of the root
of T 2 . ff and fi are unions of the clusters of some of the children of the root of T . In fact, if ff " fi
is non-empty, then ff " fi is also the union of some of the clusters of the children of the root of
T . We will show that except in one special case ff " fi is in fact the cluster of exactly one child
of the root of T .
fi). For any (y; z) in ff " fi, ((y; z); x) is the form of the
triple within each of T 1 and T 2 and hence in T , y and z would lie under the same child of the
root. Thus in this case ff " fi is a cluster of a child of the root of T .
The case where ff [ can occur for at most one child of the root of T 1 and
one child of the root of T 2 as the following lemma shows.
Lemma 6.1. Let T 1 and T 2 be 2 trees on the same leaf set S. Let ff 1 ; ::; ff k be the clusters
defined by the children of the root of T 1 and l be the clusters defined by the children of the
root of T 2 . Then the case where ff i [ can occur for at most one i and one j.
Proof. Suppose not. Let ff i [
with we have that ff i ' fi j   . But since ff
implies that This is a contradiction since fi j and fi j   are clusters defined by the
children of the root and hence should be disjoint. 2
The case for ff [ can be handled as follows. Identify the lca, say u, of the species in
similarly, the lca, say v, of the species in S \Gamma fi in T 1 . Clearly, in T 2 , u will be
a descendent of the node defining fi and in T 1 , v will be a descendent of the node defining ff.
all the nodes in the path (in starting from the node defining fi, and ending at the
node u. Let be the clusters defined by the children (not on the path) of the nodes in
this path. Similarily, identify all the clusters defined by the children of the nodes in the
path (in T 1 ), starting from the node defining ff, to the node v. Unioning pairs (x; y) whenever
x and y lie in ff " fl i for some i or whenever they lie in we get a partition of
components and these turn out to be exactly the clusters present at the children of
the root of T .
With the above characterization a high-level description of the algorithm to construct T can
be given as follows:
RDLC Construction Algorithm:
1. For each pair of maximal clusters ff 2
recursively compute the tree on ff " fi and make its root a child of the root of
T .
2. If there are clusters ff and fi such that ff [ compute the partition of
recursively compute the tree for each component of the partition
and make the roots of these trees children of the root of T .
Running Time Analysis:
Note that this algorithm does not require an explicit verification of the constructed tree, since
in fact we know that the tree exists and we are simply computing it by mimicking efficiently what
the algorithm in [2] would create.
There are at most n recursive stages. We will show that each stage can be implemented in
proving the O(n 2 ) bound.
Case 2 can be handled in O(n) time as follows. Build a graph with vertices labeled by species
in ff " fi. Now for each i connect the vertices in ff " fl i by a path and do the same for each j and
vertices in Find connected components of this graph in O(n) time. For each connected
component Comp we will have to find homeomorphic subtrees of T 1 and T 2 whose leaf set is
Comp and recurse on these subtrees. This task is common to both cases and is described after
the discussion on Case 1.
To handle Case 1 it is important not to waste time on empty intersections. So we consider
each species in turn and label the intersection that this species lies in. Thus we will identify
at most n non-empty intersections. Let ff " fi be one such intersection. We need to find a
homeomorphic subtree of T 1 that has ff " fi as the leaf set. We will show how to do this in time
proportional to the number of leaves in ff " fi.
Assume that T 1 and T 2 have been preprocessed for least common ancestor queries. Also note
that we know the left-to-right ordering of all leaves of T 1 as well as of T 2 . Given the leaves in
left-to-right ordering is also known and is the one induced by the overall left-to-right
ordering. By Lemma 4.2 we can reconstruct the topology of the tree in linear time. This is
exactly what we need to show that one stage of the recursion can be accomplished in O(n) time
and that the overall time for the algorithm is O(n 2 ). Clearly this case can be handled in linear
time and can occur for at most one pair of children.
7 Polynomial Time Algorithms for Arbitrary Local Consensus Rules
We show in this section some polynomial time algorithms for constructing local consensus trees.
We begin by discussing the case where f is a partial local consensus function.
Lemma 7.1. (Aho et. al[2]) Let A be a multi-set of k rooted triples on a leaf set S, with
n. We can determine in O(kn log n) time if a tree T exists such that T jt is homeomorphic
to t for all t 2 A.
In [15], an algorithm is given for the problem addressed in [2] for the case where all the triples
are resolved. In this case a faster algorithm can be obtained.
Lemma 7.2. (Henzinger, King, Warnow [15]) Let A be a multi-set of k resolved rooted
triples on a leaf set S, with n. We can determine in minfO(k
whether a tree T exists such that T jfa; b; cg is homeomorphic to the rooted triple(s) in A on
(if such a triple exists in A).
Theorem 7.1. Let f be an arbitrary partial local consensus function and T a set of k
evolutionary trees on S, with Then we can determine if the local consensus tree exists
and construct it if it does in O(kn 3 ) time.
Proof. Given f , T , and a triple A, we can determine the form of T f jA (for those triples A for
which T f jA has a restricted form) in O(kn 3 ) time. By the previous lemma, we can determine if
partial local consensus tree exists, and construct it if it does, in O(n 2:5 time. The total time
is therefore bounded by the cost of computing the triples. 2
While partial local consensus trees can be constructed in O(kn 3 ), total local consensus trees
can be computed even faster.
Lemma 7.3. [Kannan, Lawler, Warnow [13]] Given an oracle O which can answer queries
of "What is the form of T jfa; b; cg for a species set fa; b; cg?", we can construct in O(n 2
tree T consistent with all the oracle queries (if it exists), and O(rn log n) time if the tree T has
degree bounded by r.
Theorem 7.2. Let f be a total local consensus function. Then given a set of k rooted trees
on n species, we can construct in O(kn 2 ) time the f-local consensus tree T f if it exists. If f
always returns resolved subtrees, then we can compute T f in O(kn log n) time.
Proof. We can implement the oracle determining the form of the homeomorphic subtree of T f
on a triple a; b; c by first preprocessing the trees to answer least common ancestor (lca) queries
in constant time, using [18]. Then, answering a query needs only O(k) time. By [13], we need
only O(n 2 ) queries and O(n 2 ) additional work, for a total cost of O(kn 2 ) in the general case.
When T f has degree bounded by r, we have total cost O(krn log n). If f always returns resolved
subtrees, then T f will be binary, so that the total cost is O(kn log n). 2
8 Discussion and Conclusions
Several approaches have been taken to handle the problem of resolving multiple solutions. One
approach has been to find a maximum subset S 0 ' S inducing homeomorphic subtrees; this
subtree is then called a Maximum Agreement Subtree[14, 10, 17]. The primary disadvantage of
this approach is that it does not return an evolutionary tree on the entire species set.
There is however a connection between this problem and one of the local consensus methods.
The tree produced by the relaxed discord local consensus method contains the maximum
agreement subtree as a homeomorphic subtree. This is not too hard to see.
The other approach which we take here, requires that the resolution of the inconsistencies
be represented in a single evolutionary tree for the entire species set. A classical problem in
this area is the Tree Compatibility Problem (also called the Cladistic Character Compatibility
Problem)[7, 8, 9] The Tree Compatibility Problem says that the set T of trees is compatible if a
tree T exists such that for every triple A ' S, T resolves A if and only T
which resolves A. This problem can be solved in linear time[12, 19]. The weakness of
this approach is that in practice, many data sets are incompatible, and it is therefore necessary
to be able to handle the case where some pairs of trees resolve triples differently.
Some other approaches of this type are the strict consensus and the median tree problems.
These models are stated in terms of unrooted trees, so that instead of clusters, characters (i.e.
bipartitions) on the species set are used to represent the trees. Using the character encoding of
the consensus tree as a measure of fitness to the input, the strict consensus seeks a tree with only
those characters that appear in every tree in the input. The median tree, on the other hand, is
defined by a metric, rooted trees which is defined to be the cardinality of the
symmetric difference of the character sets of T 1 and T 2 . Given input trees T is the
median tree if it minimizes P
The median tree can be computed in polynomial time
and has a nice characterization in terms of the character encoding [4, 16, 6]. Both the above
notions are related to versions of the local consensus problem, and the relevant local consensus
trees always contain at least as much 'information' as these trees.
The work represented in this paper can be extended in several directions. As we have noted,
for all local consensus functions the local consensus tree of a set of k trees can be computed in
time polynomial in k and Many of these local consensus trees can be constructed in
O(kn) time.



--R

The design and analysis of computer algorithms

A formal theory of consensus
The median procedure for n-Trees
Mitochondrial DNA sequences of primates: tempo and mode of evolution
Optimal algorithms for comparing trees with labeled leaves



Optimal evolutionary tree comparison by sparse dynamic programming
Numerical methods for inferring evolutionary trees
Efficient algorithms for inferring evolutionary trees
Determining the evolutionary tree
Maximum agreement subtree in a set of evolutionary trees - metrics and efficient algorithms
A fast algorithm for constructing rooted trees from constraints
The Complexity of the Median Procedure for Binary Trees
computing the maximum agreement subtree
Fast Algorithm for Finding Nearest Common Ancestors

--TR
graphs;algorithms;evolutionary trees