arXiv:1705.05295v2 [cs.DS] 19 May 2017

Constructing a Consensus Phylogeny from a
Leaf-Removal Distance
Cedric Chauve1 , Mark Jones2 , Manuel Lafond3 , Céline
Scornavacca4 , and Mathias Weller5
1

Department of Mathematics, Simon Fraser University, Burnaby,
BC, Canada,, cedric.chauve@sfu.ca
2
Delft Institute of Applied Mathematics, Delft University of
Technology, P.O. Box 5, 2600 AA, Delft, the Netherlands,
M.E.L.Jones@tudelft.nl
3
Department of Mathematics and Statistics, University of Ottawa,
585 King Edward Ave., K1N 6N5 Ottawa, Canada,
mlafond2@uOttawa.ca
4
Institut des Sciences de l’Evolution – Université Montpellier,
CNRS, IRD, EPHE, Place Eugène Bataillon, 34095 Montpellier,
France, celine.scornavacca@umontpellier.fr
5
Laboratoire d’Informatique, de Robotique et de Microélectronique
de Montpellier, 34392 Montpellier Cedex 5 - France,
mathias.weller@lirmm.fr
January 3, 2018
Abstract
Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as
input a set of trees describing possibly discordant evolutionary scenarios
for a given set of genes or species, and aims at finding a single tree that
minimizes the leaf-removal distance to the input trees. This problem is a
specific instance of the general consensus/supertree problem, widely used
to combine or summarize discordant evolutionary trees. The problem we
introduce is specifically tailored to address the case of discrepancies between the input trees due to the misplacement of individual taxa. Most
supertree or consensus tree problems are computationally intractable, and
we show that the problem we introduce is also NP-hard. We provide
tractability results in form of a 2-approximation algorithm and a parameterized algorithm with respect to the number of removed leaves. We also
introduce a variant that minimizes the maximum number d of leaves that

1

are removed from any input tree, and provide a parameterized algorithm
for this problem with parameter d.

1

Introduction

In the present paper, we consider a very generic computational biology problem: given a collection of trees representing, possibly discordant, evolutionary
scenarios for a set of biological entities (genes or species – also called taxa in
the following), we want to compute a single tree that agrees as much as possible
with the input trees. Several questions in computational biology can be phrased
in this generic framework. For example, for a given set of homologous gene sequences that have been aligned, one can sample evolutionary trees for this gene
family according to a well defined posterior distribution and then ask how this
collection of trees can be combined into a single gene tree, a problem known
as tree amalgamation [13]. In phylogenomics, one aims at inferring a species
tree from a collection of input trees obtained from whole-genome sequence data.
A first approach considers gene families and proceeds by computing individual
gene trees from a large set of gene families, and then combining this collection
of gene trees into a unique species tree for the given set of taxa; this requires
handling the discordant signal observed in the gene trees due to evolutionary
processes such as gene duplication and loss [10], lateral gene transfer [14], or
incomplete lineage sorting [12]. Another approach concatenates the sequence
data into a single large multiple sequence alignment, that is then partitioned
into overlapping subsets of taxa for which partial evolutionary trees are computed, and a unique species tree is then inferred by combining the resulting
collection of partial trees [11].
For example, the Maximum Agreement Subtree (MAST) problem considers
a collection of input trees1 , all having the same leaf labels and looks for a
tree of maximum size (number of leaves), which agrees with each of the input
trees. This problem is tractable for trees with bounded degree but NP-hard
generally [1]. The MAST problem is a consensus problem, because the input
trees share the same leaf labels set, and the output tree is called a consensus
tree. In the supertree framework, the input trees might not all have identical
label sets, but the output is a tree on the whole label set, called a supertree.
For example, in the Robinson-Foulds (RF) supertree problem, the goal is to
find a supertree that minimizes the sum of the RF-distances to the individual
input trees [15]. One way to compute consensus trees and supertrees that is
closely related to our work is to modify the collection of input trees minimally
in such a way that the resulting modified trees all agree. For example, in the
MAST problem, modifications of the input trees consist in removing a minimum
number of taxa from the whole label set, while in the Agreement Supertree
by Edge Contraction (AST-EC) problem, one is asked to contract a minimum
number of edges of the input trees such that the resulting (possibly non-binary)
1 All trees we consider here are uniquely leaf-labeled, rooted (i.e. are out-trees) and binary;
see next section for formal definitions.

2

trees all agree with at least one supertree [7]; in the case where the input trees
are all triplets (rooted trees on three leaves), this supertree problem is known as
the Minimum Rooted Triplets Inconsistency problem [4]. The SPR Supertree
problem considers a similar problem where the input trees can be modified with
the Subtree-Prune-and-Regraft (SPR) operator [16].
In the present work, we introduce a new consensus problem, called LR-Consensus.
Given a collection of input trees having the same leaf labels set, we want to remove a minimum number of leaves – an operation called a Leaf-Removal (LR) –
from the input trees such that the resulting pruned trees all agree. Alternatively,
this can be stated as finding a consensus tree that minimizes the cumulated leafremoval distance to the collection of input trees. This problem also applies to
tree amalgamation and to species tree inference from one-to-one orthologous
gene families, where the LR operation aims at correcting the misplacement of
a single taxon in an input tree.
In the next section, we formally define the problems we consider, and how
they relate to other supertree problems. Next we show that the LR-Consensus
problem is NP-hard and that in some instances, a large number of leaves need
to be removed to lead to a consensus tree. We then provide a 2-approximation
algorithm, and show that the problem is fixed-parameter tractable (FPT) when
parameterized by the total number of LR. However, these FPT algorithms have
impractical time complexity, and thus, to answer the need for practical algorithms, we introduce a variant of the LR-Consensus problem, where we ask if a
consensus tree can be obtained by removing at most d leaves from each input
tree, and describe an FPT algorithm with parameter d.

2

Preliminary notions and problems statement

Trees. All trees in the rest of the document are assumed to be rooted and
binary. If T is a tree, we denote its root by r(T ) and its leaf set by L(T ). Each
leaf is labeled by a distinct element from a label set X , and we denote by X (T )
the set of labels of the leaves of T . We may sometimes use L(T ) and X (T )
interchangeably. For some X ⊆ X , we denote by lcaT (X) the least common
ancestor of X in T . The subtree rooted at a node u ∈ V (T ) is denoted Tu and
we may write LT (u) for L(Tu ). If T1 and T2 are two trees and e is an edge of
T1 , grafting T2 on e consists in subdividing e and letting the resulting degree 2
node become the parent of r(T2 ). Grafting T2 above T1 consists in creating a
new node r, then letting r become the parent of r(T1 ) and r(T2 ). Grafting T2
on T1 means grafting T2 either on an edge of T1 or above T1 .
The leaf removal operation. For a subset L ⊆ X , we denote by T − L
the tree obtained from T by removing every leaf labeled by L, contracting the
resulting non-root vertices of degree two, and repeatedly deleting the resulting
root vertex while it has degree one. The restriction T |L of T to L is the tree
T − (X \ L), i.e. the tree obtained by removing every leaf not in L. A triplet
is a rooted tree on 3 leaves. We denote a triplet R with leaf set {a, b, c} by ab|c
3

if c is the leaf that is a direct child of the root (the parent of a and b being its
other child). We say R = ab|c is a triplet of a tree T if T |{a,b,c} = R. We denote
tr(T ) = {ab|c : ab|c is a triplet of T }.
We define a distance function dLR between two trees T1 and T2 on the same
label set X consisting in the minimum number of labels to remove from X so
that the two trees are equal. That is,
dLR (T1 , T2 ) = min{|X| : X ⊆ X and T1 − X = T2 − X}
Note that dLR is closely related to the Maximum Agreement Subtree (MAST)
between two trees on the same label set X , which consists in a subset X 0 ⊆ X of
maximum size such that T1 |X 0 = T2 |X 0 : dLR (T1 , T2 ) = |X | − |X 0 |. The MAST
of two binary trees on the same label set can be computed in time O(n log n),
where n = |X | [5], and so dLR can be found within the same time complexity.
Problem statements. In this paper, we are interested in finding a tree T on
X minimizing the sum of dLR distances to a given set of input trees.
LR-Consensus
Given: a set of trees T = {T1 , . . . , Tt } with X P
(T1 ) = . . . = X (Tt ) = X .
Find: a tree T on label set X that minimizes Ti ∈T dLR (T, Ti ).
We can reformulate the LR-Consensus problem as the problem of removing
a minimum number of leaves from the input trees so that they are compatible.
Although the equivalence between both formulations is obvious, the later formulation will often be more convenient. We need to introduce more definitions
in order to establish this equivalence.
A set of trees
S T = {T1 , . . . , Tt } is called compatible if there is a tree T such
that X (T ) = Ti ∈T X (Ti ) and T |X (Ti ) = Ti for every i ∈ [t]. In this case, we say
that T displays T . A list C = (X1 , . . . , Xt ) of subsets of X is a leaf-disagreement
P
for T if {T1 − X1 , . . . , Tt − Xt } is compatible. The size of C is i∈[t] |Xi |. We
denote by ASTLR (T ) the minimum size of a leaf-disagreement for T , and may
sometimes write ASTLR (T1 , . . . , Tt ) instead of ASTLR (T ). A subset X 0 ⊆ X
of labels is a label-disagreement for T if {T1 − X 0 , . . . , Tt − X 0 } is compatible.
Note that, if T = {T1 , T2 }, then the minimum size of a label-disagreement for
T is dLR (T1 , T2 ). We may now define the AST-LR problem (see Figure 1 for an
example).
Agreement Subtrees by Leaf-Removals (AST-LR)
Given: a set of trees T = {T1 , . . . , Tt } with X (T1 ) = . . . = X (Tt ) = X .
Find: a leaf-disagreement C for T of minimum size.
Lemma 1. Let T = {T1 , . . . , Tt } be a set ofP
trees on the same label set X , with
n = |X |. Given a supertree T such that v := Ti ∈T dLR (T, Ti ), one can compute
in time O(tn log(n)) a leaf-disagreement C of size at most v. Conversely, given
a leaf-disagreement C forPT of size v, one can compute in time O(tn log2 (tn))
a supertree T such that Ti ∈T dLR (T, Ti ) ≤ v.
4

T1

b

a

T2

c

d

a

T3

b

c

d

a

d

c

b

Figure 1: Example instance T = {T1 , T2 , T3 } of AST-LR with label set X =
{a, b, c, d}. The list (X1 = {d}, X2 = {b}, X3 = {a}) is a leaf-disagreement for T
of size 3.
From Lemma 12 both problems share the same optimality value, the NPhardness of one implies the hardness of the other and approximating one problem
within a factor c implies that the other problem can be approximated within a
factor c. We conclude this subsection with the introduction of a parameterized
variant of the AST-LR problem.
AST-LR-d
Input: a set of trees T = {T1 , . . . , Tt } with L(T1 ) = . . . = L(Tt ) = X , and an
integer d.
Question: Are there X1 , . . . , Xt ⊆ X such that |Xi | ≤ d for each i ∈ [t], and
{T1 − X1 , . . . , Tt − Xt } is compatible?
We call a tree T ∗ a solution to the AST-LR-d instance if dLR (Ti , T ∗ ) ≤ d for
each i ∈ [t].
Relation to other supertree/consensus tree problems. The most widely
studied supertree problem based on modifying the input trees is the SPR Supertree problem, where arbitrarily large subtrees can be moved in the input
trees to make them all agree (see [16] and references there). The interest of
this problem is that the SPR operation is very general, modelling lateral gene
transfer and introgression. The LR operation we introduce is a limited SPR,
where the displaced subtree is composed of a single leaf. An alternative to the
SPR operation to move subtrees within a tree is the Edge Contraction (EC)
operation, that contracts an edge of an input tree, thus increasing the degree
of the parent node. This operation allows correcting the local misplacement of
a full subtree. AST-EC is NP-complete but can be solved in O((2t)p tn2 ) time
where p is the number of required EC operations [7].
Compared to the two problems described above, an LR models a very specific type of error in evolutionary trees, that is the misplacement of a single
taxon (a single leaf) in one of the input trees. This error occurs frequently
in reconstructing evolutionary trees, and can be caused for example by some
evolutionary process specific to the corresponding input tree (recent incomplete
lineage sorting, or recent lateral transfer for example). Conversely, it is not well
2 All

missing proofs are provided in Appendix.

5

adapted to model errors, due for example to ancient evolutionary events that
impacts large subtrees. However, an attractive feature of the LR operation is
that computing the LR distance is equivalent to computing the MAST cost and
is thus tractable, unlike the SPR distance which is hard to compute. This suggests that the LR-Consensus problem might be easier to solve than the SPR
Supertree problem, and we provide indeed several tractability results. Compared to the AST-EC problem, the AST-LR problem is naturally more adapted
to correct single taxa misplacements as the EC operation is very local and the
number of EC required to correct a taxon misplacement is linear in the length
of the path to its correct location, while the LR cost of correcting this is unitary. Last, LR-Consensus is more flexible than the MAST problem as it relies on
modifications of the input trees, while with the way MAST corrects a misplaced
leaf requires to remove this leaf from all input trees. This shows that the problems AST-LR and AST-LR-d complement well the existing corpus of gene trees
correction models.

3

Hardness and approximability of AST-LR

In this section, we show that the AST-LR problem is NP-hard, from which the
LR-Consensus hardness follows. We then describe a simple factor 2 approximation algorithm. The algorithm turns out to be useful for analyzing the worst
case scenario for AST-LR in terms of the required number of leaves to remove,√as
we show that there are AST-LR instances that require removing about n − n
leaves in each input tree.

NP-hardness of AST-LR
We assume here that we are considering the decision version of AST-LR, i.e.
deciding whether there is a leaf-disagreement of size at most ` for a given `.
We use a reduction from the MinRTI problem: given a set R of rooted triplets,
find a subset R0 ⊂ R of minimum cardinality such that R \ R0 is compatible.
The MinRTI problem is NP-Hard [4] (even W [2]-hard and hard to approximate
within a O(log n) factor). Denote by M IN RT I(R) the minimum number of
triplets to remove from R to attain compatibility. We describe the reduction
here.
St Let R = {R1 , . . . , Rt } be an instance of MinRTI, with the label set L :=
i=1 X (Ri ). For a given integer m, we construct an AST-LR instance T =
{T1 , . . . , Tt } which is such that M IN RT I(R) ≤ m if and only if ASTLR (T ) ≤
t(|L| − 3) + m.
We first construct a tree Z with additional labels which will serve as our
main gadget. Let {Li }1≤i≤t be a collection of t new label sets, each of size
(|L|t)10 , all disjoint from each other and all disjoint from L. Each tree in our
AST-LR instance will be on label set X = L ∪ L1 ∪ . . . ∪ Lt . For each i ∈ [t],
let Xi be any tree with label set Li . Obtain Z by taking any tree on t leaves

6

a

X1

TL0

X2

b

c

X3

Figure 2: Construction of the tree T1 for an instance R = {R1 , R2 , R3 } of
MinRTI in which R1 = ab|c.
l1 , . . . , lt , then replacing each leaf li by the Xi tree (i.e. li is replaced by r(Xi )).
Denote by rZ (Xi ) the root of the Xi subtree in Z.
Then for each i ∈ [t], we construct Ti from Ri as follows. Let L0 = L \ X (Ri )
be the set of labels not appearing in Ri , noting that |L0 | = |L| − 3. Let TL0 be
any tree with label set L0 , and obtain the tree Zi by grafting TL0 on the edge
between rZ (Xi ) and its parent. Finally, Ti is obtained by grafting Ri above
Zi . See Figure 2 for an example. Note that each tree Ti has label set X as
desired. Also, it is not difficult to see that this reduction can be carried out in
polynomial time. This construction can now be used to show the following.
Theorem 1. The AST-LR and LR-Consensus problems are NP-hard.
The idea of the proof is to show that in the constructed AST-LR instance,
we are ”forced” to solve the corresponding MinRTI instance. In more detail, we
show that M IN RT I(R) ≤ m if and only if ASTLR (T ) ≤ t(|L| − 3) + m. In one
direction, given a set R0 of size m such that R \ R0 is compatible, one can show
that the following leaf removals from T make it compatible: remove, from each
Ti , the leaves L0 = L\X (Ri ) that were inserted into the Z subtree, then for each
Ri ∈ R0 , remove a single leaf in X (Ri ) from Ti . This sums up to t(|L| − 3) + m
leaf removals. Conversely, it can be shown that there always exists an optimal
solution for T that removes, for each Ti , all the leaves L0 = L \ X (Ri ) inserted
in the Z subtree, plus an additional single leaf l from m trees Ti1 , . . . , Tim such
that l ∈ L. The corresponding triplets Ri1 , . . . , Rim can be removed from R so
that it becomes compatible.

Approximating AST-LR and bounding worst-case scenarios
Given the above result, it is natural to turn to approximation algorithms in order
to solve AST-LR or LR-Consensus instances. It turns out that there is a simple
factor 2 approximation for LR-Consensus which is achieved by interpreting the
problem as finding a median in a metric space. Indeed, it is not hard to see
that dLR is a metric (over the space of trees on the same label set X ). A direct
consequence, using an argument akin to the one in [9, p.351], is the following.
Theorem 2. The following is a factor P
2 approximation algorithm for LR-Consensus:
return the tree T ∈ T that minimizes Ti ∈T dLR (T, Ti ).
7

Theorem 2 can be used to lower-bound the ‘worst’ possiblepinstance of
AST-LR. We show that in some cases, we can only keep about |X | leaves
√
per tree. That is, there are instances for which ASTLR (T ) = Ω(t(n − n)),
where t is the number of trees and n = |X |. The argument is based on a probabilistic argument, for which we will make use of the following result [3, Theorem
4.3.iv].
√
Theorem 3 ([3]). For any constant c > e/ 2, there is some n0 such that for
all n ≥ n0 , the following holds: if T1 and T2 are two binary trees on n leaves
√
chosen randomly, uniformly and independently, then E[dLR (T1 , T2 )] ≥ n − c n.
√
Corollary 1. There are instances of AST-LR in which Ω(t(n − n)) leaves need
to be deleted.
The above is shown by demonstrating that, by picking
P a set T of t random trees, the expected optimal sum of distances minT Ti ∈T dLR (T, Ti ) is
√
Ω(t(n − n). This is not direct though, since the tree T ∗ that minimizes this
sum is not itself random, and so we cannot apply Theorem 3 directly on T ∗ . We
can however, show that the tree T 0 ∈ T obtained using the
√ 2-approximation,
which is random, has expected sum of distances Ω(t(n − n)). Since T ∗ requires, at best, half the leaf deletions of T 0 , the result follows. Note that finding
a non-trivial upper bound on ASTLR (T ) is open.

4

Fixed-parameter tractability of AST-LR and AST-LR-d.

An alternative way to deal with computational hardness is parameterized complexity. In this section, we first show that AST-LR is fixed-parameter-tractable
with respect to q := ASTLR (T ). More precisely, we show that AST-LR can be
solved in O(12q n3 ) time, where n := |X |. We then consider an alternative parameter d, and show that finding a tree T ∗ , if it exists, such that dLR (Ti , T ∗ ) ≤ d
for every input tree Ti , can be done in O(cd d3d (n3 + tn log n)) time for some
constant c.

4.1

Parameterization by q

The principle of the algorithm is the following. It is known that a set of trees T =
{T1 , . . . , TSt } is compatible if and only if the union of their triplet decomposition
tr(T ) = Ti ∈T tr(Ti ) is compatible [2]. In a step-by-step fashion, we identify
a conflicting set of triplets in tr(T ), each time branching into the (bounded)
possible leaf-removals that can resolve the conflict. We stop when either tr(T )
is compatible after the performed leaf-removals, or when more than q leaves
were deleted.
We employ a two phase strategy. In the first phase, we eliminate direct
conflicts in tr(T ), i.e. if at least two of ab|c, ac|b and bc|a appear in tr(T ),
then we recursively branch into the three ways of choosing one of the 3 triplets,
and remove one leaf in each Ti disagreeing with the chosen triplet (we branch

8

into the three possible choices, either removing a, b or c). The chosen triplet is
locked in tr(T ) and cannot be changed later.
When the first phase is completed, there are no direct conflicts and tr(T )
consists in a full set of triplets on X . That is, for each distinct a, b, c ∈ X , tr(T )
contains exactly one triplet on label set {a, b, c}. Now, a full set of triplets is
not necessarily compatible, and so in the second phase we modify tr(T ), again
deleting leaves, in order to make it compatible. Only the triplets that have
not been locked previously can be modified. This second phase is analogous to
the FPT algorithm for dense MinRTI presented in [8]. The dense MinRTI is a
variant of the MinRTI problem, introduced in Section 3, in which the input is
a full set of triplets and one has to decide whether p triplets can be deleted to
attain compatibility.
Theorem 4 ([8]). A full set of triplets R is compatible if and only if for any
set of four labels {a, b, c, d}, R does not contain the subset {ab|c, cd|b, bd|a} nor
the subset {ab|c, cd|b, ad|b}.
One can check, through an exhaustive enumeration of the possibilities, that
there are only four ways to correct a conflicting set of triplets R1 , R2 , R3 where
R1 = ab|c, R2 = cd|b, R3 ∈ {bd|a, ad|b}. We can: (1) transform R1 to bc|a; (2)
transform R1 to ac|b; (3) transform R2 to bd|c; (4) transform R3 to ab|d. This
leads to a O(4p n3 ) algorithm for solving dense MinRTI: find a conflicting set of
four labels, and branch on the four possibilities, locking the transformed triplet
each time.
For the second phase of AST-LR, we propose a slight variation of this algorithm. Each time a triplet R is chosen and locked, say R = ab|c, the trees
containing ac|b or bc|a must loose a, b or c. We branch into these three possibilities. Thus for each conflicting 4-set, there are four ways of choosing a triplet,
then for each such choice, three possible leaves to delete from a tree. This gives
12 choices to branch into recursively. Algorithm 1 is described in detail in the
Appendix and its analysis yields the following.
Theorem 5. AST-LR can be solved in time O(12q tn3 ).
Although Theorem 5 is theoretically interesting as it shows that AST-LR is in
FPT with respect to q, the 12q factor might be too high for practical purposes,
motivating the alternative approach below.

4.2

Parameterization by maximum distance d

We now describe an algorithm for the AST-LR-d problem, running in time
O(cd d3d (n3 + tn log n)) that, if it exists, finds a solution (where here c is a
constant not depending on d nor n).
We employ the following branch-and-bound strategy, keeping a candidate
solution at each step. Initially, the candidate solution is the input tree T1 and, if
T1 is indeed a solution, we return it. Otherwise (in particular if dLR (T1 , Ti ) > d
for some input tree Ti ), we branch on a set of “leaf-prune-and-regraft” operations

9

on T1 . In such an operation, we prune one leaf from T1 and regraft it somewhere
else. If we have not produced a solution after d such operations, then we halt this
branch of the algorithm (as any solution must be reachable from T1 by at most
d operations). The resulting search tree has depth at most d. In order to bound
the running time of the algorithm, we need to bound the number of “leaf-pruneand-regraft” operations to try at each branching step. There are two steps to
this: first, we bound the set of candidate leaves to prune, second, given a leaf,
we bound the number of places where to regraft it. To bound the candidate set
of leaves to prune, let us call a leaf x interesting if there is a solution T ∗ , and
minimal sets X1 , Xi ⊆ X of size at most d, such that (a) T1 − X1 = T ∗ − X1 ,
(b) Ti − Xi = T ∗ − Xi , and (c) x ∈ X1 \ Xi , where Ti is an arbitrary input tree
for which dLR (T1 , Ti ) > d. It can be shown that an interesting leaf x must exist
if there is a solution. Moreover, though we cannot identify x before we know
T ∗ , we can nevertheless construct a set S of size O(d2 ) containing all interesting
leaves. Thus, in our branching step, it suffices to consider leaves in S.
Assuming we have chosen the correct x, we then bound the number of places
to try regrafting x. Because of the way we chose x, we may assume there
is a solution T ∗ and Xi ⊆ X such that |Xi | ≤ d, Ti − Xi = T ∗ − Xi and
x ∈
/ Xi . Thus we may treat Ti as a “guide” on where to regraft x. Due to
the differences between T1 , Ti and T ∗ , this guide does not give us an exact
location in T1 to regraft x. Nevertheless, we can show that the number of
candidate locations to regraft x can be bounded by O(d). Thus, in total we
have O(d3 ) branches at each step in our search tree of depth d, and therefore
have to consider O((O(3d ))d ) = O(cd d3d ) subproblems.
Theorem 6. AST-LR-d can be solved in time O(cd d3d (n3 + tn log n)), where c
is a constant not depending on d or n.

5

Conclusion

To conclude, we introduced a new supertree/consensus problem, based on a simple combinatorial operator acting on trees, the Leaf-Removal. We showed that,
although this supertree problem is NP-hard, it admits interesting tractability
results, that compare well with existing algorithms. Future research should
explore if various simple combinatorial operators, that individually define relatively tractable supertree problems (for example LR and EC) can be combined
into a unified supertree problem while maintaining approximability and fixedparameter tractability.
Acknowledgement: MJ was partially supported by Labex NUMEV (ANR-10LABX-20) and Vidi grant 639.072.602 from The Netherlands Organization for Scientific Research (NWO). CC was supported by NSERC Discovery Grant 249834. CS was
partially supported by the French Agence Nationale de la Recherche Investissements
dAvenir/Bioinformatique (ANR-10-BINF-01-01, ANR-10- BINF-01-02, Ancestrome).
ML was supported by NSERC PDF Grant.

10

References
[1] A. Amir and D. Keselman. Maximum agreement subtree in a set of evolutionary trees: Metrics and efficient algorithms. SIAM J. Comput., 26:1656–
1669, 1997.
[2] D. Bryant. Building trees, hunting for trees, and comparing trees. PhD
thesis, Bryant University, 1997.
[3] D. Bryant, A. McKenzie, and M. Steel. The size of a maximum agreement
subtree for random binary trees. Dimacs Series in Discrete Mathematics
and Theoretical Computer Science, 61:55–66, 2003.
[4] J. Byrka, S. Guillemot, and J. Jansson. New results on optimizing rooted
triplets consistency. Discrete Appl. Math., 158:1136–1147, 2010.
[5] R. Cole, M. Farach-Colton, R. Hariharan, T. M. Przytycka, and M. Thorup.
An O(nlog n) algorithm for the maximum agreement subtree problem for
binary trees. SIAM J. Comput., 30:1385–1404, 2000.
[6] Y. Deng and D. Fernández-Baca. Fast Compatibility Testing for Rooted
Phylogenetic Trees. In Combinatorial Pattern Matching 2016, volume 54
of LIPIcs. Leibniz Int. Proc. Inform., pages 12:1–12:12, 2016.
[7] D. Fernández-Baca, S. Guillemot, B. Shutters, and S. Vakati. Fixedparameter algorithms for finding agreement supertrees. SIAM J. Comput.,
44:384–410, 2015.
[8] S. Guillemot and M. Mnich. Kernel and fast algorithm for dense triplet
inconsistency. Theoret. Comput. Sci., 494:134–143, 2013.
[9] D. Gusfield. Algorithms on strings, trees and sequences: computer science
and computational biology. Cambridge university press, 1997.
[10] M. Hellmuth, N. Wieseke, M. Lechner, H.-P. Lenhof, M. Middendorf, and
P. F. Stadler. Phylogenomics with paralogs. Proc. Natl. Acad. Sci. USA,
112:2058–2063, 2015.
[11] E. D. Jarvis et al. Whole-genome analyses resolve early branches in the
tree of life of modern birds. Science, 346:1320–1331, 2014.
[12] C. Scornavacca and N. Galtier. Incomplete lineage sorting in mammalian
phylogenomics. Sys. Biol., 66:112–120, 2017.
[13] C. Scornavacca, E. Jacox, and G. J. Szollösi. Joint amalgamation of most
parsimonious reconciled gene trees. Bioinformatics, 31:841–848, 2015.
[14] G. J. Szollösi, B. Boussau, S. S. Abby, E. Tannier, and V. Daubin. Phylogenetic modeling of lateral gene transfer reconstructs the pattern and relative
timing of speciations. Proc. Natl. Acad. Sci. USA, 109:17513–17518, 2012.

11

[15] P. Vachaspati and T. Warnow. FastRFS: fast and accurate robinson-foulds
supertrees using constrained exact optimization. Bioinformatics, 33:631–
639, 2017.
[16] C. Whidden, N. Zeh, and R. G. Beiko. Supertrees based on the subtree
prune-and-regraft distance. Sys. Biol., 63:566–581, 2014.

12

A

Omitted proofs

Here we give proofs for several results whose proofs were omitted in the main
paper. Note that the proof of Theorem 6 is deferred to its own section.
Lemma 1 (restated). Let T = {T1 , . . . , Tt } be a setPof trees on the same
label set X . Then, given a supertree T such that v := Ti ∈T dLR (T, Ti ), one
can compute in time O(tn log n) a leaf-disagreement C of size at most v, where
n = |X |. Conversely, given a leaf-disagreement C forPT of size v, one can
compute in time O(tn log2 (tn)) a supertree T such that Ti ∈T dLR (T, Ti ) ≤ v.
Proof. In the first direction, for each Ti ∈ T , there is a set Xi ⊆ X of size
dLR (T, Ti ) such that Ti − Xi = T − Xi . Moreover, Xi can be found in time
O(n log n). Thus (X1 , . . . , Xt ) is a leaf-disagreement of the desired size and
can be found in time O(tn log n). Conversely, let C = (X1 , . . . , Xt ) be a leafdisagreement of size v. As T 0 = {T1 − X1 , . . . , Tt − Xt } is compatible, there is a
tree T that displays T 0 , and it is easy to see that the sum of distances between
T and T 0 is at most the size of C. As for the complexity, it is shown in [6] how
to compute in time O(tn log2 (tn)), given a set of trees T 0 , a tree T displaying
T 0 if one exists.
We next consider the case where T consists only of two trees.
Lemma 2. Let T1 , T2 be two trees on the same label set X . Then ASTLR (T1 , T2 ) =
dLR (T1 , T2 ). Moreover, every optimal leaf-disagreement C = (X10 , X20 ) for T1 and
T2 can be obtained in the following manner: for every label-disagreement X 0 of
size dLR (T1 , T2 ), partition X 0 into X10 , X20 .
Proof. Let X 0 ⊂ X such that |X 0 | = dLR (T1 , T2 ) and T1 − X 0 = T2 − X 0 . Then
clearly, for any bipartition (X10 , X20 ) of X 0 , T10 := T1 − X10 and T20 := T2 − X20
are compatible, since the leaves that T10 and T20 have in common yield the same
subtree, and leaves that appear in only one tree cannot create incompatibility.
In particular, ASTLR (T1 , T2 ) ≤ dLR (T1 , T2 ).
Conversely, let C = (X10 , X20 ) be a minimum leaf-disagreement. We have
0
X1 ∩ X20 = ∅, for if there is some ` ∈ X10 ∩ X20 , then ` could be reinserted into
one of the two trees without creating incompatibility. Thus C is a bipartition
of X 0 = X10 ∪ X20 . Moreover, we must have T1 − X 0 = T2 − X 0 , implying
|X 0 | ≥ dLR (T1 , T2 ). Combined with the above inequality, |X 0 | = dLR (T1 , T2 ),
and the Lemma follows.
It follows from Lemma 2 that any optimal label-disagreement X 0 can be
turned into an optimal leaf-disagreement, which is convenient as X 0 can be
found in polynomial time. We will make heavy use of this property later on.
Note that the same type of equivalence does not hold when 3 or more trees
are given, i.e. computing a MAST of three trees does not necessarily yield a
leaf-disagreement of minimum size. Consider for example the instance T =
{T1 , T2 , T3 } in Figure 1. An optimal leaf-disagreement for T has size 2 and

13

consists of any pair of distinct leaves. On the other hand, an optimal leafdisagreement for T has size 3, and moreover each leaf corresponds to a different
label.
Theorem 1 (restated). The AST-LR and LR-Consensus problems are NPhard.
Proof. We begin by restating the reduction from MinRTI to AST-LR.
St Let R = {R1 , . . . , Rt } be an instance of MinRTI, with the label set L :=
i=1 X (Ri ). For a given integer m, we construct an AST-LR instance T =
{T1 , . . . , Tt } which is such that M IN RT I(R) ≤ m if and only if ASTLR (T ) ≤
t(|L| − 3) + m.
We first construct a tree Z with additional labels which will serve as our
main gadget. Let {Li }1≤i≤t be a collection of t new label sets, each of size
(|L|t)10 , all disjoint from each other and all disjoint from L. Each tree in our
AST-LR instance will be on label set X = L ∪ L1 ∪ . . . ∪ Lt . For each i ∈ [t],
let Xi be any tree with label set Li . Obtain Z by taking any tree on t leaves
l1 , . . . , lt , then replacing each leaf li by the Xi tree (i.e. li is replaced by r(Xi )).
Denote by rZ (Xi ) the root of the Xi subtree in Z.
Then for each i ∈ [t], we construct Ti from Ri as follows. Let L0 = L \ X (Ri )
be the set of labels not appearing in Ri , noting that |L0 | = |L| − 3. Let TL0 be
any tree with label set L0 , and obtain the tree Zi by grafting TL0 on the edge
between rZ (Xi ) and its parent. Finally, Ti is obtained by grafting Ri above
Zi . See Figure 2 for an example. Note that each tree Ti has label set X as
desired. Also, it is not difficult to see that this reduction can be carried out in
polynomial time.
We now show that M IN RT I(R) ≤ m if and only if ASTLR (T ) ≤ t(|L| −
3) + m.
(⇒) Let R0 ⊂ R such that |R0 | ≤ m and R∗ := R \ R0 is compatible, and let
T (R∗ ) be a tree displaying R∗ . Note that |R∗ | ≥ t − m. We obtain a AST-LR
solution by first deleting, in each Ti ∈ T , all the leaves labeled by L \ X (Ri )
(thus Ti becomes the tree obtained by grafting Ri above Z). Then for each
deleted triplet Ri ∈ R0 , we remove any single leaf of Ti labeled by some element
in X (Ri ). In this manner, no more than t(|L| − 3) + m leaves get deleted.
Moreover, grafting T (R∗ ) above Z yields a tree displaying the modified set of
trees, showing that they are compatible.
(⇐) We first argue that if T admits a leaf-disagreement C = (X1 , . . . , Xt ) of
size at most t(|L| − 3) + m, then there is a better or equal solution that removes,
in each Ti , all the leaves labeled by L \ X (Ri ) (i.e. those grafted in the Zi tree).
For each i ∈ [t], let Ti0 = Ti − Xi , and denote T 0 = {T10 , . . . , Tt0 }. Suppose that
there is some i ∈ [t] and some ` ∈ L \ X (Ri ) such that ` ∈ X (Ti0 ).
We claim that ` ∈
/ X (Tj0 ) for every i 6= j ∈ [t]. Suppose otherwise that
0
` ∈ X (Tj ) for some j 6= i. Consider first the case where ` ∈
/ X (Rj ). Note that
by the construction of Zi and Zj , for every xi ∈ X (Xi ) ∩ X (Ti0 ) ∩ X (Tj0 ) and
every xj ∈ X (Xj ) ∩ X (Ti0 ) ∩ X (Tj0 ), Ti0 contains the `xi |xj triplet whereas Tj0
contains the `xj |xi triplet. Since these triplets are conflicting, no supertree can

14

contain both and so no such xi , xj pair can exist, as we are assuming that a
supertree for Ti0 and Tj0 exists. This implies that one of X (Xi ) ∩ X (Ti0 ) ∩ X (Tj0 )
or X (Xj ) ∩ X (Ti0 ) ∩ X (Tj0 ) must be empty. Suppose without loss of generality
that the former is empty. Then each xi ∈ Xi must have been deleted in at least
one of Ti or Tj . As |X (Xi )| = (|L|t)10 > t(|L| − 3) + m, this contradicts the
size of the solution C. In the second case, we have ` ∈ X (Rj ). But this time, if
there are xi ∈ X (Xi ) ∩ X (Ti0 ) ∩ X (Tj0 ) and xj ∈ X (Xj ) ∩ X (Ti0 ) ∩ X (Tj0 ), then
Tj0 contains the xi xj |` triplet, again conflicting with the `xi |xj triplet found in
Ti . As before, we run into a contradiction since too many Xi or Xj leaves need
to be deleted. This proves our claim.
We thus assume that ` only appears in Ti0 . Let Rj ∈ R such that ` ∈ X (Rj ),
noting that ` does not appear in Tj0 . Consider the solution T 00 obtained from T 0
by removing ` from Ti0 , and placing it back in Tj0 where it originally was in Tj .
Formally this is achieved by replacing, in the leaf-disagreement C, Xi by Xi ∪{`}
and Xj by Xj \ {`}. Since ` still appears only in one tree, no conflict is created
and we obtain another solution of equal size. By repeating this process for
every such leaf `, we obtain a solution in which every leaf labeled by L \ X (Ri )
is removed from Ti0 . We now assume that the solution T 0 has this form.
Consider the subset R0 = {Ri ∈ R : |X (Ti0 ) ∩ X (Ri )| < 3}, that is those
triplets Ri for which the corresponding tree Ti had a leaf removed outside of the
Zi tree. By the form of the T 0 solution, at least t(|L| − 3) removals are done in
the Zi trees, and as only m removals remain, R0 has size at most m. We show
that R \ R0 is a compatible set of triplets. Since T 0 is compatible, there is a
tree T that displays each Ti0 ∈ T 0 , and since each triplet of R \ R0 belongs to
some Ti0 , T also displays R \ R0 . This concludes the proof.
Theorem 2 (restated). The following is a factor 2 approximation
algorithm
P
for LR-Consensus: return the tree T ∈ T that minimizes Ti ∈T dLR (T, Ti ).
∗
Proof. Let
solution for LR-Consensus, i.e. T ∗ is a tree minP T be an optimal
∗
imizing Ti ∈T dLR (Ti , T ), and let T be chosen as described in the theorem
statement. Moreover let T 0 be the tree of T minimizing dLR (T 0 , T ∗ ). By the
triangle inequality,
X
X
X
dLR (T 0 , Ti ) ≤
(dLR (T 0 , T ∗ ) + dLR (T ∗ , Ti )) ≤ 2
dLR (T ∗ , Ti )
Ti ∈T

Ti ∈T

Ti ∈T

where the last inequality is due to the fact that dLR (T 0P
, T ∗ ) ≤ dLR (T ∗ , Ti )
0
for all i, by our choicePof T . Our choice of T implies
Ti ∈T dLR (T, Ti ) ≤
P
0
∗
d
(T
,
T
)
≤
2
d
(T
,
T
).
i
Ti ∈T LR
Ti ∈T LR i
Corollary 1 (restated). There are instances of AST-LR in which Ω(t(n −
leaves need to be deleted.

√

n))

Proof. Let T = {T1 , . . . , Tt } be a random set of t trees chosen uniformly and
independently. For large enough n, the expected sum of distances between each

15

pair of trees is

X
E


X

dLR (Ti , Tj ) =

E[dLR (Ti , Tj )] ≥

1≤i<j≤t

1≤i<j≤t

 
√
t
(n − c n)
2

Pt
for some constant c, by Theorem 3. Let S := minT i=1 dLR (T, Ti ) be the random variable corresponding to the
Ptminimum sum of distances. By Theorem 2,
there is a tree T 0 ∈ T such that i=1 dLR (T 0 , Ti ) ≤ 2S. We have
X

dLR (Ti , Tj ) ≤

1≤i<j≤t

X

dLR (Ti , T 0 ) + dLR (T 0 , Tj )

1≤i<j≤t

= (t − 1)

t
X

dLR (Ti , T 0 )

i=1

≤ (t − 1)2S
Since, in general for two random variables X and Y , always having X ≤ Y
implies E[X] ≤ E[Y ], we get


 
X
√
t
(n − c n) ≤ E 
dLR (Ti , Tj ) ≤ E[(t − 1)2S] = 2(t − 1)E[S]
2
1≤i<j≤t

√
√
yielding E[S] ≥ t/4(n − c n) = Ω(t(n − n)), and so there must exist an
instance T satisfying the statement.
Theorem 5 (restated). AST-LR can be solved in time O(12q tn3 ).
Proof. We provide an algorithm, Algorithm 1, for AST-LR, and prove its correctness and complexity.
We first argue that the algorithm is correct. First observe that the algorithm only returns TRUE when a conflict-free set of triplets is attained without
deleting more than q leaves, and so there are no false-positives. Moreover, it
is not hard to see that the first phase of the algorithm tries every possible way
of obtaining a full set of triplets from tr(T ) using at most q leaf removals. Indeed, for every set of 3 labels a, b, c that are present in a direct conflict, the
algorithm branches into the 3 ways of locking ab|c, ac|b or bc|a and for each
tree Ti disagreeing with the chosen triplet, all three ways of removing a leaf to
agree with the chosen triplet are tested. In a similar manner, for each dense set
D of triplets that is attained, each way of freeing D from conflicting 4-sets is
evaluated (not only in the ways of choosing a triplet to resolve the conflict, but
also in the ways of removing leaves from the trees of T so that they agree with
the locked triplets). It follows that if tr(T ) can be made compatible by deleting
at most q leaves, then some leaf in the branch tree created by the algorithm will
return TRUE, and so there are no false-negatives.
16

Algorithm 1 Recursive AST-LR FPT algorithm.
1:

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

procedure mastrl(T , q, phase, F )
T is the set of input trees, q is the maximum number of leaves to delete,
phase is the current phase number (initially 1), F is the set of locked triplets
so far
if q < 0 or F contains conflicting triplets then
Return FALSE
else if there is ab|c ∈ F and a tree Ti ∈ T such that ac|b ∈ tr(Ti ) or
bc|a ∈ Ti then
Branching: If one of the following calls returns True
mastrl((T \ {Ti }) ∪ {Ti − {a}}, q − 1, phase, F ) //remove a from
Ti
mastrl((T \ {Ti }) ∪ {Ti − {b}}, q − 1, phase, F ) //remove b from
Ti
mastrl((T \ {Ti }) ∪ {Ti − {c}}, q − 1, phase, F ) //remove c from
Ti
then Return True, otherwise Return False
else if phase = 1 then
if there are a, b, c ∈ X such that at least 2 of ab|c, ac|b or bc|a appear
in T then
Branching: If one of the following calls returns True
mastrl(T , q, phase, F ∪ {ab|c})
mastrl(T , q, phase, F ∪ {ac|b})
mastrl(T , q, phase, F ∪ {bc|a})
then Return True, otherwise Return False
else
Return mastrl(T , q, 2, F ) //enter phase 2
else if phase = 2 then
if there is a conflicting set {a, b, c, d} in tr(T ) ∪ F then
Branching: If one of the following calls returns True
mastrl(T , q, phase, F ∪ {ac|b})
mastrl(T , q, phase, F ∪ {bc|a})
mastrl(T , q, phase, F ∪ {bd|c})
mastrl(T , q, phase, F ∪ {ab|d})
then Return True, otherwise Return False
else
Return True //There are no conflicts ⇒ tr(T ) ∪ F is compatible

17

As for the complexity, when the algorithm enters the ‘else if’ block of line 4, it
branches into 3 cases that decrement q. When it enters the ‘if’ block of line 11,
it branches into 3 cases but q is not decremented. However each of these 3
recursive calls immediately leads to the ‘else if’ block on line 4, and so this case
can be seen as branching into 9 cases. Similarly, when the algorithm enters the
‘if’ block of line 19, it branches into 4 cases, each of which leads to the 3 subcases
following line 4. Thus 12 cases are considered. Therefore, the branching tree
created by the algorithm has degree at most 12 and depth at most q, and so
at most 12q cases are considered. Finally, each call to the algorithm requires
time O(tn3 ) since this is the time required to identify conflicting sets of triplets
within the t trees.

B

Leaf Prune-and-Regraft Moves

Here we introduce the notion of leaf prune-and-regraft (LPR) moves, which
will be used in the proof of Theorem 6, and which may be of independent
interest. In an LPR move, we prune a leaf from a tree and then regraft it
another location (formal definitions below). LPR moves provide an alternate
way of characterizing the distance function dLR - indeed, we will show that
dLR (T1 , T2 ) ≤ k if and only if there is a sequence of at most k LPR moves
transforming T1 into T2 .
Definition 1. Let T be a tree on label set X . A LPR move on T is a pair (`, e)
where ` ∈ X and e ∈ {E(T − {`}), ⊥}. Applying (`, e) consists in grafting ` on
the e edge of T − {`} if e 6=⊥, and above the root of T − {`} if e =⊥.
An LPR sequence L = ((`1 , e1 ), . . . , (`k , ek )) is an ordered tuple of LPR
moves, where for each i ∈ [k], (`i , ei ) is an LPR move on the tree obtained after
applying the first i − 1 LPR moves of L. We may write L = (`1 , . . . , `k ) if the
location at which the grafting takes place does not need to be specified. We say
that L turns T1 into T2 if, by applying each LPR move of L in order on T1 , we
obtain T2 .
See Figure 4 for an example of an LPR sequence.
In the following statements, we assume that T1 and T2 are two trees on label
set X . We exhibit an equivalence between leaf removals and LPR sequences,
then show that the order of LPR moves in a sequence do not matter in terms
of turning one tree into another - in particular any leaf can be displaced first.
Lemma 3. There is a subset X ⊆ X such that T1 − X = T2 − X if and
only if there is an LPR sequence (x1 , x2 , . . . , xk ) turning T1 into T2 such that
X = {x1 , . . . , xk }.
Proof. If T1 = T2 then the proof is trivial, so we will assume this is not the case.
We prove the lemma by induction on |X|.
For the base case, suppose that X = {x}. If T1 − X = T2 − X, then let
Tm = T1 − X = T2 − X. We find an LPR move (x, e) with e ∈ E(Tm ) ∪ {⊥}
turning T1 into T2 . Observe that T2 can be obtained by grafting x on Tm , either
18

a

a

b

c

d

e

a

c

b

c

e

b

d

e

d

Figure 3: Sequence of trees showing the LPR sequence L = ((b, f ), (d, ⊥)),
where f is the edge between the root and the least common ancestor of a and
c in the first tree.
on an edge uv, in which case we set e = uv, or above the root, in which case we
set e =⊥. Since Tm = T1 − {x}, it follows that (x, e) is an LPR move turning
T1 into T2 . In the other direction, assume there is an LPR move (x, e) turning
T1 into T2 . Observe that for any tree T 0 derived from T1 by an LPR move using
x, T 0 − {x} = T1 − {x}. In particular, T2 − {x} = T1 − {x} and we are done.
For the induction step, assume that |X| > 1 and that the claim holds for
any X 0 such that |X 0 | < |X|. If T1 − X = T2 − X, then define Tm = T1 − X,
and let x be an arbitrary element of X. We will first construct a tree T10 such
that T1 − {x} = T10 − {x} and T10 − (X \ {x}) = T2 − (X \ {x}).
Observe that T2 − (X \ {x}) can be obtained by grafting x in Tm . Let e = uv
if this grafting takes place on an edge of Tm with v being the child of u, or e =⊥
if x is grafted above Tm , and in this case let v = r(Tm ). Let v 0 = vT1 −{x} be
the node in T1 − {x} corresponding to v.
Let T10 be derived from T1 − {x} by grafting x onto the edge between v 0
and its parent if v 0 is non-root, and grafting above v 0 otherwise. It is clear
that T1 − {x} = T10 − {x}. Furthermore, by our choice of v 0 we have that
T10 − (X \ {x}) = T2 − (X \ {x}).
Now that we have T1 −{x} = T10 −{x} and T10 −(X \{x}) = T2 −(X \{x}), by
the inductive hypothesis there is an LPR sequence turning T1 into T10 consisting
of a single move (x, e), and an LPR sequence (x1 , x2 , . . . , xk−1 ) turning T10 into
T2 such that {x1 , . . . , xk0 } = (X \ {x}). Then by concatenating these two
sequences, we have an LPR sequence (x1 , x2 , . . . , xk ) turning T1 into T2 such
that X = {x1 , . . . , xk }.
19

For the converse, suppose that there is an LPR sequence (x1 , x2 , . . . , xk )
turning T1 into T2 such that X = {x1 , . . . , xk }. Let T10 be the tree derived from
T1 by applying the first move in this sequence. That is, there is an LPR move
(x1 , e) turning T1 into T10 , and there is an LPR sequence (x2 , . . . , xk ) turning
T10 into T2 . Then by the inductive hypothesis T1 − {x1 } = T10 − {x1 } and
T10 − {x2 , . . . , xk } = T2 − {x2 , . . . , xk }. Thus, T1 − X = T10 − X = T2 − X, as
required.
Lemma 4. If there is an LPR sequence L = (x1 , . . . , xk ) turning T1 into T2 ,
then for any i ∈ [k], there is an LPR sequence L0 = (x01 , . . . , x0k ) turning T1 into
T2 such that x01 = xi and {x1 , . . . , xk } = {x01 , . . . , x0k }.
Proof. Consider again the proof that if T1 − X = T2 − X then there is an LPR
sequence (x1 , . . . xk ) turning T1 into T2 such that X = {x1 , . . . , xk } (given in the
proof of Lemma 3). When |X| > 1, we construct this sequence by concatenating
the LPR move (x, e) with an LPR sequence of length |X| − 1, where x is an
arbitrary element of X. As we could have chosen any element of X to be x,
we have the following: If T1 − X = T2 − X then for each x ∈ X, there is an
LPR sequence (x1 , . . . , xk ) turning T1 into T2 such that X = {x1 , . . . , xk } and
x1 = x.
Thus our proof is as follows: Given an LPR sequence L = (x1 , . . . , xk )
turning T1 into T2 and some i ∈ [k], Lemma 3 implies that T1 − {x1 , . . . , xk } =
T2 − {x1 , . . . , xk }. By the observation above, this implies that there is an LPR
sequence (x01 , . . . , x0k ) turning T1 into T2 such that {x1 , . . . , xk } = {x01 , . . . , x0k }
and x01 = x.

C

Proof of Theorem 6

This section makes use of the concept of LPR moves, which are introduced in
the previous section. As discussed in the main paper, we employ a branch-andbound style algorithm, in which at each step we alter a candidate solution by
pruning and regrafting a leaf. That is, we apply an LPR move.
The technically challenging part is bound the number of possible LPR moves
to try. To do this, we will prove Lemma 7, which provides a bound on the number
of leaves to consider, and Lemma 10, which bounds the number of places a leaf
may be regrafted to.
Denote by tr(T ) the set of rooted triplets of a tree T . Two triplets R1 ∈
tr(T1 ) and R2 ∈ tr(T2 ) are conflicting if R1 = ab|c and R2 ∈ {ac|b, bc|a}. We denote by conf (T1 , T2 ) the set of triplets of T1 for which there is a conflicting triplet
in T2 . That is, conf (T1 , T2 ) = {ab|c ∈ tr(T1 ) : ac|b ∈ tr(T2 ) or bc|a ∈ tr(T2 )}.
Finally we denote by conf set(T1 , T2 ) = {{a, b, c} : ab|c ∈ conf (T1 , T2 )}, i.e.
the collection of 3-label sets formed by conflicting triplets. Given a collection
C = {S1 , . . . , S|C| } of sets, a hitting set of C is a set S such that S ∩ Si 6= ∅ for
each Si ∈ C.
Lemma 5. Let X ⊆ X . Then T1 − X = T2 − X if and only if X is a hitting
set of conf set(T1 , T2 ).
20

Proof. It is known that for two rooted trees T1 , T2 that are leaf-labelled and
binary, T1 = T2 if and only if tr(T1 ) = tr(T2 ) [2]. Note also that tr(T − X) =
{ab|c ∈ tr(T1 ) : X ∩ {a, b, c} = ∅} for any tree T and X ⊆ X .
Therefore we have that T1 − X = T2 − X if and only if tr(T1 − X) =
tr(T2 − X), which holds if and only if for every a, b, c ∈ X \ X, if ab|c ∈ tr(T1 )
then ab|c ∈ tr(T2 ). This in turn occurs if and only if X is a hitting set for
conf set(T1 , T2 ).
In what follows, we call X ⊆ X a minimal disagreement between T1 and T2
if T1 − X = T2 − X and for any X 0 ⊂ X, T1 − X 0 6= T2 − X 0 .
Lemma 6. Suppose that d < dLR (T1 , T2 ) ≤ d0 +d with d0 ≤ d, and that there is a
tree T ∗ and subsets X1 , X2 ⊆ X such that T1 −X1 = T ∗ −X1 , T2 −X2 = T ∗ −X2
and |X1 | ≤ d0 , |X2 | ≤ d. Then, there is a minimal disagreement X between T1
and T2 of size at most d + d0 and x ∈ X such that x ∈ X1 \ X2 .
Proof. Let X 0 = X1 ∪ X2 . Observe that T1 − X 0 = T ∗ − X 0 = T2 − X 0 and
|X 0 | ≤ d+d0 . Letting X be the minimal subset of X 0 such that T1 −X = T2 −X,
we have that X is a minimal disagreement between T1 and T2 and |X| ≤ d + d0 .
Furthermore as |X| ≥ dLR (T1 , T2 ) > d, |X \X2 | > 0, and so there is some x ∈ X
with x ∈ X \ X2 = X1 \ X2 .
We are now ready to state and prove Lemma 7.
Lemma 7. Suppose that dLR (T1 , T2 ) ≤ d for some integer d. Then, there is
some S ⊆ X such that |S| ≤ 8d2 , and for any minimal disagreement X between
T1 and T2 with |X| ≤ d, X ⊆ S. Moreover S can be found in time O(n2 ).
We will call S as described in Lemma 7 a d-disagreement kernel between
T1 and T2 . Thus Lemma 6 essentially states that if T1 isn’t a solution and
dLR (T1 , T2 ) > d, then for T1 to get closer to a solution, there is a leaf x in the
dLR (T1 , T2 )-disagreement kernel that needs to be removed and regrafted in a
location that T2 ‘agrees with’. Lemma 7 in turn gives us a set S of size at most
8d2 such that the desired x must be contained in S.
Proof. By Lemma 5, it is enough to find a set S such that S contains every
minimal hitting set of conf set(T1 , T2 ) of size at most d.
We construct S as follows.
Let X be a subset of X of size at most d such that T1 − X = T2 − X. As
previously noted, this can found in time O(n log n) [5].
For notational convenience, for each x ∈ X we let x1 , x2 be two new labels,
and set X1 = {x1 : x ∈ X}, X2 = {x2 : x ∈ X}. Thus, X1 , X2 are disjoint
“copies” of X. Let T10 be derived from T1 by replacing every label from X
with the corresponding label in X1 , and similarly let T20 be derived from T2 by
replacing every label from X with the corresponding label in X2 .
Let TJ be a tree with label set (X \ X) ∪ X1 ∪ X2 such that TJ − X2 = T10
and TJ − X1 = T20 . The tree TJ always exists and can be found in polynomial
time. Intuitively, we can start from T10 , and graft the leaves of X2 where T2
21

T1

x

a

b

c

dc

T2

e

f

g

y

h

a

b

y

c

dc

e

x

f

g

h

TJ

c

x1

a

b

e

d

f

y2 x2

g

y1

h

Figure 4: Construction of the tree TJ , given two trees T1 , T2 , with X = {x, y}
such that T1 − X = T2 − X.
“wants” them to be. See Figure 4 for an example. Algorithm 2 gives a method
for constructing TJ , and takes O(n2 ) time.
In addition, let L be the set of all labels in X \ X that are descended in TJ
from lcaTJ (X1 ∪ X2 ), and let R = X \ (L ∪ X). Thus, L, X, R form a partition
of X , and L, X1 , X2 , R form a partition of the labels of TJ .
For the rest of the proof, we call {x, y, z} a conflict triple if {x, y, z} ∈
conf set(T1 , T2 ).
We first observe that no triple in conf set(T1 , T2 ) contains a label in R.
Indeed, consider a triple {x, y, z}. Any conflict triple must contain a label from
X, so assume without loss of generality that x ∈ X, z ∈ R. If x ∈ X, y ∈ L, z ∈
R, then we have that TJ contains the triplets x1 y|z, x2 y|z, and so T1 and T2 both
contain xy|z, and {x, y, z} is not a conflict triple. Similarly if x, y ∈ X, z ∈ R,
then TJ contains the triplets x1 y1 |z, x2 y2 |z, and again {x, y, z} is not a conflict
triple. If x ∈ X and y, z ∈ R, then the triplet on {x1 , y, z} in TJ depends only
on the relative positions in TJ of y, z and lcaTJ (X1 ∪ X2 ). Thus we get the
same triplet if we replace x1 with x2 , and so {x, y, z} is not a conflict triple.
This concludes the proof that no triple in conf set(T1 , T2 ) contains a label
in R. Having shown this, we may conclude that any minimal disagreement
between T1 and T2 is disjoint from R, and so our returned set S only needs to
contain labels in L ∪ X.
Now consider the tree T ∗ = TJ |X1 ∪X2 , i.e. the subtree of TJ restricted to
the labels in X1 ∪ X2 . Thus in the example of Figure 4, T ∗ is the subtree of TJ

22

Algorithm 2 Algorithm to construct “Join tree” of T10 , T20
1:

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

32:
33:

procedure join-trees(T10 , T20 , L0 , X10 , X20 )
T10 is a tree on L0 ∪ X10 , T20 is a tree on L0 ∪ X20 , T10 |L0 = T20 |L0 . Output: A
tree TJ on L0 ∪ X10 ∪ X20 such that TJ |L0 ∪X10 = T10 and TJ |L0 ∪X20 = T20
if L0 ∪ X10 = ∅ then
Return T20
else if L0 ∪ X20 = ∅ then
Return T10
else if X10 ∪ X20 = ∅ then
Return T10
Set r1 = root of T10 , u, v the children of r1
Set r2 = root of T20 , w, z the children of r2
Set X1u = descendants of u in X10 , L1u = descendants of u in L0
Set X1v = descendants of v in X10 , L1v = descendants of v in L0
Set X2w = descendants of w in X20 , L2w = descendants of w in L0
Set X2z = descendants of z in X20 , L2z = descendants of z in L0
if L1u = L2w and L1v = L2z then
Set Tlef t = join-trees(T10 |L1u ∪X1u , T20 |L1u ∪X2w , L1u , X1u , X2w )
Set Tright = join-trees(T10 |L1v ∪X1v , T20 |L1v ∪X2z , L1v , X1v , X2z )
else if L1u = L2z and L1v = L2w then
Set Tlef t = join-trees(T10 |L1u ∪X1u , T20 |L1u ∪X2z , L1u , X1u , X2z )
Set Tright = join-trees(T10 |L1v ∪X1v , T20 |L1v ∪X2w , L1v , X1v , X2w )
else if L1u =∅ then
Set Tlef t = join-trees(T10 |X1u , T20 |∅ , ∅, X1u , ∅)
Set Tright = join-trees(T10 |L0 ∪X1v , T20 , L0 , X1v , X20 )
else if L1v = ∅ then
Set Tlef t = join-trees(T10 |L0 ∪X1u , T20 , L0 , X1u , X20 )
Set Tright = join-trees(T10 |X1v , T20 |∅ , ∅, X1v , ∅)
else if L2w = ∅ then
Set Tlef t = join-trees(T10 |∅ , T20 |X2w , ∅, ∅, X2w )
Set Tright = join-trees(T10 , T20 |L0 ∪X2z , L0 , X10 , X2z )
else if L2z = ∅ then
Set Tlef t = join-trees(T10 , T20 |L0 ∪X2w , L0 , X10 , X2w )
Set Tright = join-trees(T10 |∅ , T20 |X2z , ∅, ∅, X2z )
. If none of the above cases holds, then T10 |L0 6= T20 |L0 , contradicting the
requirements on the input
Set TJ = the tree on L0 ∪ X10 ∪ X20 whose root has Tlef t and Tright as
children.
Return TJ .

23

spanned by {x1 , x2 , y1 , y2 }. We will now use the edges of T ∗ to form a partition
of L, as follows. For any edge uv in T ∗ with u the parent of v, let s(uv) denote
the set of labels y ∈ X such that y has an ancestor which is an internal node on
the path from u to v in TJ , but y is not a descendant of v itself. For example in
Figure 4, if u is the least common ancestor of x1 , y1 and v is the least common
ancestor of x1 , y2 , then uv is an edge in T ∗ and s(uv) = {c, d, e}.
Observe that {s(uv) : uv ∈ E(T ∗ )} forms a partition of L. (Indeed, for any
l ∈ L, let u be the minimal element in T ∗ on the path in TJ between l and
lcaTJ (X1 ∪ X2 ) (note that u exists as lcaTJ (X1 ∪ X2 ) itself is in T ∗ ). As u is
in T ∗ , both of its children are on paths in TJ between u and a child of u in T ∗ .
In particular, the child of u which is an ancestor of l is an internal node on the
path between u and v in TJ , for some child v of u in T ∗ , and l is not descended
from v by construction. It is clear by construction that all s(uv) are disjoint.)
The main idea behind the construction of S is that we will add X to S,
together with O(d) labels from s(uv) for each edge uv in T ∗ . As the number of
edges in T ∗ is 2(|X1 ∪ X2 | − 1) = O(d), we have the required bound of O(d2 )
on |S|.
So now consider s(uv) for some edge uv in T ∗ . In order to decide which
labels to add to S, we need to further partition s(uv). Let u = u0 u1 . . . ut = v
be the path in TJ from u to v. For each i ∈ [t − 1] (note that this does not
include i = 0), we call the set of labels descended from ui but not ui+1 a dangling
clade. Observe that the dangling clades form a partition of s(uv). Thus in the
example of Figure 4, if u is the least common ancestor of x1 , y1 and v is the
least common ancestor of x1 , y2 , then for the edge uv the dangling clades are
{c} and {d, e}.
We now make the following observations about the relation between s(uv)
and triples in conf set(T1 , T2 ).
Observation 1: if {x, y, z} is a conflict triple and x ∈ s(uv), y, z ∈
/ s(uv),
then {x0 , y, z} is also a conflict triple for any x0 ∈ s(uv). (The intuition behind
this is that there are no labels appearing ’between’ x and x0 that are not in
s(uv).)
Observation 2: for any triple {x, y, z} with x, y ∈ s(uv), {x, y, z} is a
conflict triple if and only if x, y are in different dangling clades and z ∈ X
with zi descended from v, z3−i not descended from u1 for some i ∈ [2] (recall
that z1 ∈ X1 and z2 ∈ X2 ). To prove one direction, it is easy to see that if
the conditions hold, then Ti displays either xz|y or yz|x (depending on which
dangling clade appears ’higher’), and T3−i displays xy|z. For the converse,
observe first that z ∈ X as X is a hitting set for conf set(T1 , T2 ) and x, y ∈
/ X.
Then if xy are in the same dangling clade, we have that both T1 and T2 display
xy|z. So x, y must be in different dangling clades. Next observe that each of
z1 , z2 must either be descended from v or not descended from u1 , as otherwise v
would not be the child of u in T ∗ . If z1 , z2 are both descended from v or neither
are descended from u1 , then T1 and T2 display the same triplet on {x, y, z}.
So instead one must be descended from v and one not descended from u1 , as
required.
Using Observations 1 and 2, we now prove the following:
24

Observation 3: for any minimal disagreement X 0 between T1 and T2 , one
of the following holds:
• X 0 ∩ s(uv) = ∅;
• s(uv) ⊆ X 0 ;
• s(uv) \ X 0 forms a single dangling clade.
To see this, let X 0 be any minimal hitting set of conf set(T1 , T2 ) with s(uv)∩
X 6= ∅ and s(uv) \ X 0 6= ∅. As X 0 is minimal, any x ∈ s(uv) ∩ X 0 must be in a
conflict triple {x, y, z} with y, z ∈
/ X 0 . As X is a hitting set for conf set(T1 , T2 ),
at least one of y, z must be in X. If y, z ∈
/ s(uv), then by Observation 1 {x0 , y, z}
0
is also a conflict triple for any x ∈ s(uv) \ X 0 . But this is a contradiction as
{x0 , y, z} has no elements in X 0 . Then one of y, z must also be in s(uv). Suppose
without loss of generality that y ∈ s(uv). We must also have that z ∈ X, as X
is a hitting set for conf set(T1 , T2 ) and x, y ∈
/ X. By Observation 2, we must
have that one of z1 , z2 is descended from v, and the other is not descended from
u1 . This in turn implies (again by Observation 2) that for any x0 ∈ s(uv) \ X 0 , if
x0 and y are in different dangling clades then {x0 , y, z} is a conflict triple. Again
this is a contradiction as {x0 , y, z} has no elements of X 0 , and so we may assume
that all elements of s(uv) \ X 0 are in the same dangling clade.
It remains to show that every element of this dangling clade is in s(uv) \ X 0 .
To see this, suppose there exists some x ∈ X 0 in the same dangling clade as
the elements of s(uv) \ X 0 . Once again we have that x is in some conflict triple
{x, y, z} with y, z ∈
/ X 0 , and if y, z ∈
/ s(uv) then {x0 , y, z} is also a conflict triple
0
0
for any x ∈ s(uv) \ X , a contradiction. So we may assume that one of y, z is
in s(uv) \ X 0 . But all elements of s(uv) \ X 0 are in the same dangling clade as
x, and so by Observation 2 {x, y, z} cannot be a conflict triple, a contradiction.
So finally we have that all elements of s(uv) \ X 0 are in the same dangling clade
and all elements of this clade are in s(uv) \ X 0 , as required.
With the proof of Observation 3 complete, we are now in a position to
construct S. For any minimal hitting set X 0 of conf set(T1 , T2 ) with size at
most d, by Observation 3 either X 0 ∩ s(uv) = ∅, or s(uv) ⊆ X 0 (in which
case |s(uv)| ≤ d), or s(uv) \ X 0 forms a single dangling clade C (in which case
|s(uv) \ C| ≤ d).
So add all elements of X to S. For all uv ∈ E(TJ ) and any dangling clade
C of labels in s(uv), add s(uv) \ C to S if |s(uv) \ C| ≤ d. Observe that this
construction adds at most 2d labels from s(uv) to S.
Thus, in total, we have that the size of S is at most |X| + 2d|E(TJ )| ≤
d + 2d(2(|X1 ∪ X2 | − 1)) ≤ d + 2d(4d − 2) = 8d2 − 3d ≤ 8d2 .
Algorithm 3 describes the full procedure formally. The construction of TJ
occurs once and as noted above takes O(n2 ) time. As each other line in the
algorithm is called at most n times and takes O(n) time, the overall running
time of the algorithm O(n2 ).
0

The last ingredient needed for Theorem 6 is Lemma 10, which shows that if
a leaf x of T1 as described in Lemma 6 has to be moved, then there are not too
25

Algorithm 3 Algorithm to construct a d-disagreement kernel between T1 and
T2
1:

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

procedure disagreement-kernel(d, T1 , T2 )
T1 and T2 are trees on X ,d an integer.
Output: A set S ⊆ X such that for every minimal disagreement X
between T1 and T2 with |X| ≤ d, X ⊆ S.
Find X such that |X| ≤ d and T1 − X = T2 − X
Set S = X
Let X1 , X2 be copies of X and replace T1 , T2 with corresponding trees
T10 , T20 on (X \ X) ∪ X1 , (X \ X) ∪ X2 .
Let TJ = join-trees(T10 , T20 , (X \ X), X1 , X2 )
Let T ∗ = TJ |X1 ∪X2
for uv ∈ E(T ∗ ) do
Let u = u0 u1 . . . ut = v be the path in TJ from u to v
Let s(uv) = {l ∈ X \ X : l is descended from u1 but not from v}
Set p = |s(uv)| − d
. Any clade C has |C| ≥ p iff |s(uv) \ C| ≤ d
for i ∈ [t] do
Set C = {l ∈ s(uv) : l is descended from ui but not from ui+1 } .
C is a single ’dangling clade’
if |C| ≥ p then
Set S = S ∪ (s(uv) \ C)
Return S.

many ways to regraft it in order to get closer to T ∗ .
In the course of the following proofs, we will want to take observations about
one tree and use them to make statements about another. For this reason it’s
useful to have a concept of one node ”corresponding” to another node in a
different tree. In the case of leaf nodes this concept is clear - two leaf nodes
are equivalent if they are assigned the same label- but for internal nodes there
is not necessarily any such correspondence. However, in the case that one tree
is the restriction of another to some label set, we can introduce a well-defined
notion of correspondence:
Given two trees T, T 0 such that T 0 = T |X for some X ⊆ X (T ), and a node
u ∈ V (T 0 ), define the node uT of T by uT = lcaT (LT 0 (u)). That is, uT is the
least common ancestor, in T , of the set of labels belonging to descendants of u
in T 0 . We call uT the node corresponding to u in T .
We note two useful properties of uT here:
Lemma 8. For any T, T 0 , X ⊆ X (T ) such that T 0 = T |X and any u, v ∈ V (T 0 ),
uT is an ancestor of vT if and only if u is an ancestor of v.
Proof. If u is an ancestor of v then LT 0 (v) ⊆ LT 0 (u), which implies that uT
is an ancestor of vT . For the converse, observe that for any Z ⊆ X, any
label in X descending from lcaT (Z) in T is also descending from lcaT 0 (Z) in
T 0 . In particular letting Z = LT 0 (u), we have LT (uT ) ∩ X = LT (lcaT (Z)) ∩
26

X ⊆ LT 0 (lcaT 0 (Z)) = LT 0 (lcaT 0 (LT 0 (u))) = LT 0 (u) ⊆ LT (uT ) ∩ X. Thus
LT 0 (u) = LT (uT ) ∩ X and similarly LT 0 (v) = LT (vT ) ∩ X. Then we have
that uT being an ancestor of vT implies LT (vT ) ⊆ LT (uT ), which implies that
LT 0 (v) = LT (vT ) ∩ X ⊆ LT (uT ) ∩ X = LT 0 (u), which implies that u is an
ancestor of v.
Lemma 9. For any T 00 , T 0 , T and Y ⊆ X ⊆ X (T ) such that T 0 = T |X and
T 00 = T 0 |Y , (uT 0 )T = uT .
Proof. It is sufficient to show that any node in V (T ) is a common ancestor of
LT 0 (lcaT 0 (Z)) if and only if it is a common ancestor of Z, where Z = LT 00 (u) (as
this implies that the least common ancestors of these two sets are the same).
It is clear that if v ∈ V (T ) is a common ancestor of LT 0 (lcaT 0 (Z)) then it
is also a common ancestor of Z, as Z ⊆ LT 0 (lcaT 0 (Z)). For the converse,
observe that as T 0 = T |X and Z ⊆ X, any label in X descended from lcaT 0 (Z)
in T 0 is also descended from lcaT (Z) in T . This implies LT 0 (lcaT 0 (Z)) ⊆
LT (lcaT (Z)), and so any common ancestor of Z in T is also a common ancestor
of LT 0 (lcaT 0 (Z)).
We are now ready to state and prove Lemma 10
Lemma 10. Suppose that d < dLR (T1 , T2 ) ≤ d0 + d with d0 ≤ d, and that
there are X1 , X2 ⊆ X , and a tree T ∗ such that T1 − X1 = T ∗ − X1 , T2 − X2 =
T ∗ − X2 , |X1 | ≤ d0 , |X2 | ≤ d, and let x ∈ X1 \ X2 . Then, there is a set P of
trees on label set X that satisfies the following conditions:
• for any tree T 0 such that dLR (T 0 , T ∗ ) < dLR (T1 , T ∗ ) and T 0 can be obtained
from T1 by pruning a leaf x and regrafting it, T 0 ∈ P ;
• |P | ≤ 18(d + d0 ) + 8;
• P can be found in time O(n(log n + 18(d + d0 ) + 8)).
The idea behind the proof is as follows: by looking at a subtree common
to T1 and T2 , we can identify the location that T2 “wants” x to be positioned.
This may not be the correct position for x, but we can show that if x is moved
too far from this position, we will create a large number of conflicting triplets
between T2 and the solution T ∗ . As a result, we can create all trees in P by
removing x from T1 and grafting it on one of a limited number of edges.
Proof. For the purposes of this proof, we will treat each tree T as “planted”, i.e.
as having an additional root of degree 1, denoted r(T ), as the parent of what
would normally be considered the “root” of the tree. (That is, r(T ) is the parent
of lcaT (X (T )). Note that trees are otherwise binary. We introduce r(T ) as a
notational convenience to avoid tedious repetition of proofs - grafting a label
above a tree T can instead be represented as grafting it on the edge between
r(T ) and its child. For the purposes of corresponding nodes, if T 0 = T − X then
(r(T 0 ))T = r(T ). This allows us to assume that every node in T is a descendant
of uT for some node u in T 0 .
27

A naive method for constructing a tree in P is the following: Apply an LPR
move (x, e) on T1 , such that x is moved to a position that T2 “wants” x to be in.
There are at least two problems with this method. The first is that, since T1 and
T2 have different structures, it is not clear where in T1 it is that T2 “wants” x
to be. We can partially overcome this obstacle by initially considering a subtree
common to both T1 and T2 . However, because T2 will want to move leafs that
will not be moved in T1 , it can still be the case that even though T2 “agrees”
with T ∗ on x, T2 may want to put x in the “wrong” place, when viewed from
the perspective of T1 . For this reason we have to give a counting argument to
show that if x is moved “too far” from the position suggested by T2 , it will
create too many conflicting triplets, which cannot be covered except by moving
x. We make these ideas precise below.
Let P ∗ be the set of all trees T 0 such that dLR (T 0 , T ∗ ) < dLR (T1 , T ∗ ) and
T can be obtained from T1 by an LPR move on x. Thus, it is sufficient to
construct a set P such that |P | ≤ 18(d + d0 ) + 8 and P ∗ ⊆ P .
We first construct a set Xm ⊆ X such that |Xm | ≤ d + d0 , x ∈ Xm , and
T1 − Xm = T2 − Xm . Note that the unknown set (X1 ∪ X2 ) satisfies these
properties, as T1 − (X1 ∪ X2 ) = T ∗ − (X1 ∪ X2 ) = T2 − (X1 ∪ X2 ), and so such
a set Xm must exist. We can find Xm in time O(n log n) by applying MAST on
(T1 − {x}, T2 − {x}) [5].
Now let Tm be the tree with labelset X \ Xm such that Tm = T1 − Xm =
T2 − Xm . Note that for any T 0 in P ∗ , we have that T 0 − {x} = T1 − {x} and
therefore T 0 − Xm = T1 − Xm = Tm .
Informally, we now have a clear notion of where T2 “wants” x to go, relative
to Tm . There is a unique edge e in Tm such that grafting x on e will give the
tree T2 − (Xm \ {x}). If we assume that this is the “correct” position to add
x, then it only remains to add the remaining labels of Xm back in a way that
agrees with T1 (we will describe how this can be done at the end of the proof).
Unfortunately, grafting x onto the obvious choice e does not necessarily lead to
a graph in P ∗ . This is due to the fact that T2 can be “mistaken” about labels
outside of Xm .
To address this, we have try grafting x on other edges of Tm . There are too
many edges to try them all. We therefore need the following claim, which allows
us to limit the number of edges to try.
0

Claim: In O(n) time, we can find y ∈ V (Tm ) and Z ⊆ V (Tm ), |Z| ≤ 4,
such that:
S
• For any T 0 in P ∗ , x ∈ LT 0 (yT 0 ) \ z0 ∈Z LT 0 (zT0 0 )
S
• |LTm (y) \ z0 ∈Z LTm (z 0 )| ≤ 8(d + d0 )
Informally, the claim identifies a node y and set of nodes Z in Tm , such that x
should be added as a descendant of y but not of any node in Z, and the number
of such positions is bounded. Algorithm 4 describes the formal procedure to
produce y and Z. The proof of the claim takes up most of the remainder of our
proof; the reader may wish to skip it on their first readthrough.
28

Algorithm 4 FPT algorithm to restrict possible locations of x given
(Tm , T1 , T2 , x, d, d0 )
1:

2:
3:
4:
5:

6:
7:
8:
9:
10:
11:
12:
13:

procedure location-restriction(Tm , T2 , Xm , x, d, d0 )
T1 , T2 are two trees, Tm is a common subtree of T1 and T2 such that Tm =
T2 − Xm , x is a label that cannot be moved in T2 (but must be moved in
T1 ), d is the maximum number of leaves we can remove in a tree, d0 is the
maximum number of leaves we can move in T1 . Output is a pair (y, Z) with
y ∈ V (Tm ), Z ⊆ V (Tm ), such that we may assume x is a descendant of y
but not a descendant of any z 0 ∈ Z, and the number of labels like this in
Tm is O(d). For this pseudocode, every tree T has a degree-1 root r(T ).
0
= T2 − (Xm \ {x})
Set Tm
0
0
0 (z) \ x| ≥ d + d , or
such that |LTm
Set z = lowest ancestor of x in Tm
0
return (r(Tm ), ∅) if no such z exists.
0
0
0 (y) \ LT 0 (z)| ≥ d + d ,
Set y = lowest ancestor of z in Tm
such that |LTm
m
0
or r(Tm ) if no such ancestor exists.
. Find sets Z = Z1 ∪ Z2 of nodes that cover all but a
bounded number of the descendants of y, and such that we can rule out x
being descended from any z 0 in Z.
0
Let z1 , z2 be the children of z such that x is descended from z1 in Tm
0
0
0
0
0
Set Z1 = {z descended from z2 : |LTm (z )| ≥ d + d and |LTm (z2 ) \
0
0
0
0 (z )| ≥ d + d , and this does not hold for any ancestor of z }
LTm
0
Let y1 , y2 be the children of y such that x is descended from y1 in Tm
0
0
0
0
0
Set Z2 = {y descended from y2 : |LTm (y )| ≥ d + d and |LTm (y2 ) \
0
0
0
0 (y )| ≥ d + d , and this does not hold for any ancestor of y }
LTm
. Note that |Z1 | ≤ 2, |Z2 | ≤ 2.
0
Set y ∗ = node of Tm for which y is the corresponding node in Tm
Set Z = {z ∗ in Tm : z 0 ∈ Z1 ∪ Z2 is the node corresponding to z ∗ in Tm }
Return (y ∗ , Z)

29

0
0
Proof. Let Tm
= T2 − (Xm \ {x}). Note that Tm
− {x} = Tm . We will use the
0
presence of x in Tm to identify the node y and set Z. (Technically, this means
0
the nodes we find are nodes in Tm
rather than Tm . However, we note that apart
the parent of x and x itself, neither of which will be added to {y} ∪ Z, every
0
0 corresponding to some node v in Tm . For the sake
node in Tm
is the node vTm
0
of clarity, we ignore the distinction and write v to mean vTm
throughout this
proof. The nodes in {y} ∪ Z should ultimately be replaced with the nodes in
Tm to which they correspond.)
We first identify two nodes z, y of Tm as follows:
0
0
0 (z)\{x}| ≥ d+d . If no
• Let z be the least ancestor of x in Tm
such that |LTm
0
0
0
such x exists, then X (Tm ) ≤ d + d and we may return y = r(Tm ), Z = ∅.
0
0
0 (y)\LT 0 (z)| ≥ d+d .
such that |LTm
• Let y be the least ancestor of z in Tm
m
0
If no such y exists, set y = r(Tm ).

Using this definition, we will show that x must be a descendant of yT 0 for
any T 0 ∈ P ∗ . We first describe a general tactic for restricting the position of x
in T 0 , as this tactic will be used a number of times.
Suppose that for some T 0 ∈ P ∗ there is a set of d+d0 triplets in conf set(T 0 , T2 )
whose only common element is x. Then let X 0 ⊆ X be a set of labels such that
T 0 − X 0 = T ∗ − X 0 and |X 0 | = dLR (T 0 , T ∗ ) ≤ dLR (T1 , T ∗ ) − 1 ≤ d0 − 1.
Note that T2 − (X 0 ∪ X2 ) = T ∗ − (X 0 ∪ X2 ) = T 0 − (X 0 ∪ X2 ), and therefore (X 0 ∪ X2 ) is a hitting set for conf set(T 0 , T2 ). As |X 0 ∪ X2 | ≤ d + d − 1
and there are d + d0 triplets in conf set(T 0 , T2 ) whose only common element
is x, it must be the case that x ∈ X 0 ∪ X2 . As x ∈
/ X2 , we must have
x ∈ X 0 . But this implies that T1 − X 0 = T 0 − X 0 = T ∗ − X 0 and therefore
dLR (T1 , T ∗ ) ≤ |X 0 | = dLR (T 0 , T ∗ ) ≤ dLR (T1 , T ∗ ) − 1, a contradiction. Thus we
may assume that such a set of triplets does not exist.
We now use this idea to show that x ∈ LT 0 (yT 0 ), for any T 0 ∈ P ∗ . Indeed,
0
suppose x ∈
/ LT 0 (yT 0 ). We may assume y 6= r(Tm
) as otherwise yT 0 = r(T 0 ) by
0
definition and so LT 0 (yT 0 ) = X (T ). Then let z1 , . . . , zd+d0 be d + d0 labels in
0
0 (z) \ {x}. Let y1 , . . . , yd+d0 be d + d labels in LT 0 (y) \ LT 0 (z). Observe
LTm
m
m
0
0
that for each i ∈ [d + d ], Tm (and therefore T2 ) contains the triplet (zi x|yi ),
but T 0 contains the triplet (zi yi |x). Therefore conf set(T 0 , T2 ) contains d + d0
sets whose only common element is x. As this implies a contradiction, we must
have x ∈ LT 0 (yT 0 ).
0 (y)| maybe be very large.
Note however that |LTm
In order to provide a
bounded range of possible
positions
for
x,
we
still
need
to
find a set Z of nodes
S
0
0 (y) \
0 (z ))| is bounded, and such that we can show
such that |LTm
L
0
T
z ∈Z
m
x∈
/ LT 0 (zT0 0 ) for any z 0 ∈ Z.
We now construct a set Z1 of descendants of z as follows:
0
• Let z1 , z2 be the children of z in Tm
such that x is descended from z1 .
0
0 (z2 )| ≤ 3(d + d ) then set Z1 = ∅.
• If |LTm

30

• Otherwise, let Z1 be the set of highest descendants z 0 of z2 , such that
0
0
0
0
0 (z )| ≥ d + d
0 (z2 ) \ LT 0 (z )| ≥ d + d
|LTm
and |LTm
(i.e. by highest
m
0
00
descendant we mean such that z has no ancestor z with the same properties).
0
0 (z1 )| ≤ d+d by our choice of z. It follows that if |LT 0 (z2 )| ≤
Note that |LTm
m
0
0
0 (z)| ≤ 4(d + d ). If on the other hand |LT 0 (z2 )| > 3(d +
3(d + d ) then |LTm
m
d0 ) then Z1 is non-empty. Indeed, let z 0 be a lowest descendant of z2 with
0
0
0
0
0
0 (z )| ≥ d + d , and observe that |LT 0 (z )| ≤ 2(d + d ). Then either z ∈ Z1 ,
|LTm
m
0
0
0
0
0
0
0
or |LTm (z2 ) \ LTm (z )| ≤ d + d , in which case |LTm (z2 )| ≤ |LTm (z2 ) \ LTm (z 0 )| +
0
0
0
0
0 (z )| ≤ d + d + 2(d + d ) = 3(d + d ).
|LTm
We also have that |Z1 | ≤ 2. Indeed, let z10 , z20 , z30 be three distinct nodes in
0
Z1 , and suppose without loss of generality that (z10 z20 |z30 ) ∈ tr(Tm
). Then setting
0
0
0
0
0
0
0
0 (z )| ≥
z = lcaTm (z1 , z2 ), we have that z is an ancestor of z1 such that |LTm
0
0
0
0
0
0
0
d+d and |LTm (z2 )\LTm (z )| ≥ |LTm (z3 )| ≥ d+d , a contradiction by minimality
of z1 .
S
0
0
0 (z) \
0
We have that |LTm
z 0 ∈Z1 LTm (z ))| ≤ 4(d + d ). Indeed, if Z1 = ∅ then
0
0
|LTm (z)| ≤ 4(d + d ) as described above. Otherwise, let z 0 be an element of Z1
0
0
0
0 (zp )| ≥ |LT 0 (z )| ≥ d + d ,
. Clearly |LTm
and zp its parent, zs its sibling in Tm
m
0
0
0 (z2 ) \ LT 0 (zp )| < d + d . If |LT 0 (zs )| ≥ d + d
and so as zp ∈
/ Z1 we have |LTm
m
m
0
0
0
0
0
0
then
z
∈
Z
(since
|L
(z
)
\
L
(z
)|
≥
|L
(z
)|
≥
d
+
d
),
and
so
|L
(z)
\
s
1
Tm 2
Tm s
Tm
Tm
S
0
0
0 (z ))| ≤ |LT 0 (z1 )| + |LT 0 (z2 ) \ LT 0 (zp )| ≤ 2(d + d ). Otherwise,
z 0 ∈Z1 LTm
m
m
m
S
0
0 (z) \
0
0
0
0
0
|LTm
z 0 ∈Z1 LTm (z ))| ≤ |LTm (z1 )| + |LTm (z2 ) \ LTm (zp )| + |LTm (zs )| ≤
3(d + d0 ).
S
0
0 (z) \
0
We have now shown that |Z1 | ≤ 2 and that |LTm
z 0 ∈Z1 LTm (z ))| ≤
4(d + d0 ). The final property of Z1 we wish to show is that for any z 0 ∈ Z1 and
any T 0 ∈ P , x ∈
/ LT 0 (zT0 0 ).
0 (z2 ) \
So suppose x ∈ LT 0 (zT0 0 ). Let ẑ1 , . . . , ẑd+d0 be d + d0 labels in LTm
0
0
0 (z ). Also, z1 and z2 were already taken. Let w1 , . . . , wd+d0 be d + d labels
LTm
0
0
0
0 (z ). Then for each i ∈ [d + d ], T
in LTm
m (and therefore T2 ) contains the triplet
(ẑi wi |x), but T 0 contains the triplet (xwi |ẑi ). Therefore conf set(T 0 , T2 ) contains
d + d0 sets whose only common element is x. As this implies a contradiction,
we must have x ∈
/ LT 0 (zT0 0 ).

We now define a set Z2 of descendants of y:
0
• If y = r(Tm
), set Z2 = ∅.
0
• Otherwise, let y1 , y2 be the children of y in Tm
such that z is descended
from y1 .
0
0 (y2 )| ≤ 3(d + d ) then set Z2 = ∅.
• If |LTm

• Otherwise, let Z2 be the set of highest descendants y 0 of y2 , such that
0
0
0
0
0
0 (y )| ≥ d + d and |LT 0 (y2 ) \ LT 0 (y )| ≥ d + d (i.e. such that y has
|LTm
m
m
00
no ancestor y with the same properties).

31

In a similar way S
to the proofs for Z1 , we can show that |Z2 | ≤ 2, that
0
0
0 (y) \ LT 0 (z)) \
0
|(LTm
/ LT 0 (yT0 0 ) for
y 0 ∈Z2 LTm (y ))| ≤ 4(d + d ), and that x ∈
m
0
0
∗
any y ∈ Z2 and any T ∈ P .
0
0 (y1 ) \ LT 0 (z)| ≤ d + d by our choice of y. It follows that
Note that |LTm
m
0
0
0 (y2 )| ≤ 3(d + d ) then |LT 0 (y) \ LT 0 (z)| ≤ 4(d + d ). If on the other
if |LTm
m
m
0
0
0 (y2 )| > 3(d + d ), then Z2 is non-empty. Indeed, let y be a lowest
hand |LTm
0
0
0
0
0 (y )| ≥ d + d , and observe that |LT 0 (y )| ≤ 2(d + d ).
descendant of y2 with |LTm
m
0
0
0
0 (y2 ) \ LT 0 (y )| ≤ d + d , in which case |LT 0 (y2 )| ≤
Then either y ∈ Z2 , or |LTm
m
m
0
0
0
0
0
0 (y2 ) \ LT 0 (y )| + |LT 0 (y )| ≤ d + d + 2(d + d ) = 3(d + d ).
|LTm
m
m
We also have that |Z2 | ≤ 2. Indeed, let y10 , y20 , y30 be three distinct nodes
0
in Z2 , and suppose without loss of generality that (y10 y20 |y30 ) ∈ tr(Tm
). Then
0
0
0
0
0
0 (y , y ), we have that y
setting y = lcaTm
is
an
ancestor
of
y
such
that
1 2
1
0
0
0
0
0
0 (y )| ≥ d + d and |LT 0 (y2 ) \ LT 0 (y )| ≥ |LT 0 (y )| ≥ d + d , a contradiction
|LTm
3
m
m
m
by minimality of y1 .
S
0
0
0 (y) \ LT 0 (z)) \
0
We have that |(LTm
y 0 ∈Z2 LTm (y ))| ≤ 4(d + d ). Indeed, if
m
0
0
0 (ŷ) \ LT 0 (z)| < d + d for any ancestor ŷ of
y = r(Tm ) then by construction |LTm
m
0
) rather than
z (noting that otherwise there would be no reason to set y as r(Tm
0
0
0
0 (y)\LT 0 (z)| < d+d . If y 6= r(T
the child of r(Tm )), and so in particular |LTm
m)
m
0
0 (y)\LT 0 (z)| ≤ 4(d+d ) as described above. Otherwise, let
and Z2 = ∅ then |LTm
m
0
0 (yp )| ≥
. Clearly |LTm
y 0 be an element of Z2 and yp its parent, ys its sibling in Tm
0
0
0
0 (y )| ≥ d + d , and so as yp ∈
0 (y2 ) \ LT 0 (yp )| < d + d . If
|LTm
/ Z2 we have |LTm
m
0
0
0
0 (ys )| ≥ d+d then ys ∈ Z2 (since |LT 0 (y2 )\LT 0 (ys )| ≥ |LT 0 (y )| ≥ d+d ),
|LTm
m
m
m
S
0
0 (y) \ LT 0 (z)) \
0
0
0 (z)| + |LT 0 (y2 ) \
and so |(LTm
Tm
y 0 ∈Z2 LTm (y ))| ≤ |LTm (y1 ) \ LS
m
m
0
0
0 (yp )| ≤ 2(d + d ).
0 (y) \ LT 0 (z)) \
0
LTm
Otherwise, |(LTm
y 0 ∈Z2 LTm (y ))| ≤
m
0
0 (y1 ) \ LT 0 (z)| + |LT 0 (y2 ) \ LT 0 (yp )| + |LT 0 (ys )| ≤ 3(d + d ).
|LTm
m
m
m
m
S
0
0 (y)\LT 0 (z))\
0
We have now shown that |Z2 | ≤ 2 and |(LTm
y 0 ∈Z2 LTm (y ))| ≤
m
0
0
4(d + d ). The final property of Z2 we wish to show is that for any y ∈ Z2 and
any T 0 ∈ P ∗ , we have that x ∈
/ LT 0 (yT0 0 ).
0
0 (y2 ) \
So suppose x ∈ LT 0 (yT 0 ). Let ŷ1 , . . . , ŷd+d0 be d + d0 labels in LTm
0
0
0
0
0 (y ). Let w1 , . . . , wd+d0 be d+d labels in LT 0 (y ). Then for each i ∈ [d+d ],
LTm
m
0
0
Tm (and therefore T2 ) contains the triplet (ŷi wi |x), but T contains the triplet
(xwi |ŷi ). Therefore conf set(T 0 , T2 ) contains d + d0 sets whose only common
element is x. As this implies a contradiction, we must have x ∈
/ LT 0 (yT0 0 ).
Now that Z1 and Z2 have been constructed, let Z = Z1 ∪ Z2 . Note that
|Z| ≤ 4. Algorithm 4 describes the construction of y and Z formally (see
Figure 5).
We have shown above that for any T 0 ∈ P ∗ , x isSdescended from yT 0 in T 0 and
0
0
0
0 (z) \
not
any z 0 ∈ Z, and so x ∈ LT 0 (yT 0 ) \ z0 ∈Z
|LTm
S from zT 0 for
S LT (zT 0 ). As
0
0
0
0
0
0
0
L
(z
))|
≤
4(d
+
d
)
and
|(L
(y)
\
L
(z))
\
L
(y
))|
≤
4(d +
Tm
Tm
z 0 ∈Z1 Tm
y 0 ∈Z2 Tm
S
0
0
0 (y) \
0
d0 ), we have |LTm
L
(z
))|
≤
8(d
+
d
).
0
z ∈Z Tm
0 (u)|
To analyze the complexity, note that we can calculate the value of |LTm
for all u in O(n) time using a depth-first search approach, together with the
0 (u)| = |LT 0 (u1 )| + |LT 0 (u2 )| for any node u with children u1 , u2 .
fact that |LTm
m
m
Then we can find z in O(n) time, and once we have found z we can find y, and
thence z1 , z2 , y1 , y2 , in O(n) time. Similarly, once these nodes are found we can

32

y
y1
z
z1

y2

Z2

z2
Z1

x
Figure 5: Construction of y and Z = Z1 ∪ Z2 , see Algorithm 4. Dashed edges
represent parts of the tree that were omitted. Triangles represent parts of the
tree that may contain more than d + d0 leaves.
find the members of Z in O(n) time.
Using the claim, we may now construct a set P 0 of O ≤ 16(d+d0 )+8 trees on
X \(Xm \{x}), such for any T 0 ∈ P ∗ , P 0 contains the tree T 00 = T 0 −(Xm \{x}).
Indeed, letSF be the set of arcs uv in Tm thatSexist on a path from y to a node in
(LTm (y) \ z∈Z LTm (z 0 )) ∪ Z. As |LTm (y) \ z0 ∈Z LTm (z 0 )| ≤ 8(d + d0 ), |Z| ≤ 4
and Tm is a binary tree, we have |F | ≤ 16(d + d0 ) + 8. For each e ∈ F , let Te be
the tree obtained from Tm by grafting x onto the arc e . Let P 0 = {Te : e ∈ F }.
Let T 0 be a tree in P ∗ and consider T 00 = T 0 − (Xm \ {x}). Note that
00
T − {x} = T 0 − Xm = Tm . Therefore uT 00 is well-defined for every node
u ∈ V (Tm ), and every node in T 00 is equal to uT 00 for some u ∈ V (Tm ), except
for x and its parent in T 00 . So let w be the parent of x in T 00 , uT 00 the parent
of w in T 00 , and vT 00 the child of w in T 00 that is not x. Observe that T 00 can
be obtained from Tm by grafting x onto the arc uv. Then it is enough to show
that uv ∈ F .
To see that uv ∈ F , first note that for each z 0 ∈ {y} ∪ Z, zT0 00 is well-defined
and (zT0 00 )T 0 = zT0 0 (see Lemma 9). Then as x is descended from (yT 00 )T 0 = yT 0 in
T 0 , x is descended from yT 00 in T 00 (Lemma 8). Similarly, as x is not descended
from (zT0 00 )T 0 = zT0 0 inST 0 for any z 0 ∈ Z, x is not descended from zT 00 in T 00 .
Thus x ∈ LT 00 (yT 00 ) \ z0 ∈Z LT 00 (zT0 00 ). It follows that uT 00 is a descendant of
yT 00 in T 00 (note that yT 00 6= w, as w is not the least common ancestor of any set
0
of labels
S in X (Tm )). Also, vT 00 is not a descendant of zT 00 for any z ∈ Z, unless
00
00
00
vT ∈ z∈Z zT , as otherwise x would be a descendant
of such a zT . SThus, vT 00
S
is either a member or an ancestor of (LT 00 (yT 00 ) \ z0 ∈Z LT 00 (zT0 00 ))) ∪ z0 ∈Z zT0 00 .
It follows using
is a descendant in Tm of y, and v is an ancestor
S Lemma 8 that uS
of (LTm (y) \ z0 ∈Z LTm (z 0 ))) ∪ z0 ∈Z z 0 . Then uv ∈ F , as required.
Now that we have constructed our set P 0 , it remains to find, for each Te ∈ P 0 ,
every tree T 0 on X such that T 0 − (Xm \ {x}) = Te and T 0 − {x} = T1 − {x}.

33

This will give us our set P , as for every T 0 ∈ P ∗ , T 0 − (Xm \ {x}) is a tree Te
in P 0 , and T 0 − {x} = T1 − {x}.
Let e = uv, where u, v ∈ V (Tm ), and let T1e be the subtree of T1 − {x}
whose root is v, and has as its label set v together with all labels in Xm \ {x}
descended from u but not v. Then we have to try every way of adding x into this
tree. If T1e contains t labels from Xm , then there are 2t − 1 places to try adding
x. Therefore P will have at most 2|Xm | ≤ 2(d + d0 ) additional trees compared
to P 0 , and so |P | ≤ 18(d + d0 ) + 8. Algorithm 5 gives the full procedure to
construct P .
Algorithm 5 FPT algorithm to find candidate trees for (T1 , Ti , x)
1:

2:
3:
4:
5:

6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

procedure candidate-trees(T1 , T2 , x, d, d0 )
T1 , T2 are two trees, x is a label that cannot be moved in T2 (but must be
moved in T1 ), d is the maximum number of leaves we can remove in a tree, d0
is the maximum number of leaves we can move in T1 . For this pseudocode,
every tree T has a degree-1 root r(T ).
0
0
0
= (T2 −
| ≤ d0 + d − 1 and (T1 − {x}) − Xm
such that |Xm
Find Xm
0
{x}) − Xm
0
∪ {x}
Set Xm = Xm
Set Tm = T1 − Xm
Set (y, Z) = location-restriction(Tm , T2 , Xm , x, d, d0 )
. y, Z are
nodes in Tm such that roughly speaking, we may assume x must become a
descendant of y but not of any z 0 ∈ Z.
Set U = {u ∈ V (Tm ) : u ∈ Z or u is a leaf descended from y but not
from any z 0 ∈ Z}
Set F = {uv ∈ E(Tm ) : uv is on a path from y to U } . F is the set of
edges we could graft x onto.
Set P = ∅
. Given F we now begin constructing P .
Set T10 = T1 − {x}
for e = uv ∈ F with u the parent of v do
. Try grafting x on e
Set uT10 = the node in T10 corresponding to u
Set vT10 = the node in T10 corresponding to v
Set Xe = set of labels l in Xm \ {x} for which l has an ancestor v 0 in
T10 with v 0 descended from uT10 , vT10 descended from v 0
. Xe is the set of leaves of T1 for which we have to subdivide e.
Set U = vT10 ∪ Xe
Set Ee = {u0 v 0 ∈ E(T10 ) : u0 v 0 is on a path from uT10 to U }
for u0 v 0 ∈ Ee do
Constuct T 0 from T10 by grafting x on u0 v 0
Set P = P ∪ {T 0 }
Return P

To analyze the complexity, recall that we find Xm , and therefore construct
0
Tm and Tm
, in O(n log n) time. As shown above, we can find the node y and
set Z in O(n) time. Given y and Z, the set of arcs F can be found in O(n)
34

time using a depth-first search approach. For each e ∈ F it takes O(n) time to
construct Te , and so the construction of P 0 takes O(|F |n) = O((16(d+d0 )+8)n)
time. Finally, the construction of of P from P 0 takes O(|P |n) = O((18(d + d0 ) +
8)n) time. Putting it all together, we have that the construction of P takes
O(n(log n + 18(d + d0 ) + 8)) time.
We will call the set of trees P described in Lemma 10 the set of candidate
trees for (T1 , T2 , x).
We are finally ready to give the proof of Theorem 6
Theorem 6 (restated). AST-LR-d can be solved in time O(cd d3d (n3 +tn log n)),
where c is a constant not depending on d or n.
Proof. The outline for our algorithm is as follows. We employ a branch-andbound algorithm, in which at each step we attempt to modify the input tree
T1 to become close to a solution. We keep track of an integer d0 , representing
the maximum length of an LPR sequence between T1 and a solution. Initially
set d0 = d. At each step, if dLR (T1 , Ti ) ≤ d for each Ti ∈ T then T1 is a
solutioon, and we are done. Otherwise, there must exist sime Ti for which
dLR (T1 , Ti ) ≥ d + d0 . In this case, we calculate the (d + d0 ) disagreement kernel
S between T1 and Ti (using the procedure of Lemma 7), and for each x ∈ S,
attempt to construct a set P of trees as in Lemma 10. For each T 0 ∈ P , we try
replacing T1 with T 0 , reducing d0 by 1, and repeating the procedure. Algorithm 6
describes the full procedure formally.
We claim that Algorithm 6 is a correct algorithm for AST-LR-d, and runs in
time O(cd d3d (n2 + tn log n)), for some constant c not depending on n or d.
First notice that if, in a leaf node of the branch tree created by Algorithm 6,
a tree T ∗ is returned, this occurs at line 3 in which case it has been verified that
T ∗ is indeed a solution. As an internal node of the branch tree returns a tree if
and only if a child recursive call also returns a tree (the for loop on line 9), this
shows that when the algorithm outputs a tree T ∗ , it is indeed a solution.
We next show that if a solution exists, then Algorithm 6 will return one.
Suppose that T admits a solution, and let T ∗ be a solution that minimizes
d1 := dLR (T1 , T ∗ ), with d1 ≤ d0 . We show that one leaf of the branch tree
created by the algorithm returns T ∗ (and thus the root of the branch tree also
returns a solution, albeit not necessarily T ∗ ). This is done by proving that in
one of the recursive calls made to mastrl-distance on line 13, the tree T 0
obtained from T1 satisfies dLR (T 0 , T ∗ ) = d1 − 1. By applying this argument
inductively, this shows that the algorithm will find T ∗ at some node of depth
d1 in the branch tree of the algorithm.
First notice that since dLR is a metric, for each Ti ∈ T , dLR (T1 , Ti ) ≤
dLR (T1 , T ∗ )+dLR (T ∗ , Ti ) ≤ d0 +d, and so the algorithm will not return F ALSE
on line 5.
If T1 isn’t a solution, then there is a tree of T , say T2 w.l.o.g., such that
dLR (T1 , T2 ) > d. Notice that in this case, all the conditions of Lemma 6 are
satisfied, i.e. dLR (T1 , T2 ) > d, and there are sets X1 , X2 ⊆ X both of size at
most d such that T1 − X1 = T ∗ − X1 , T2 − X2 = T ∗ − X2 . Thus there is a
35

minimal disagreement X between T1 and T2 , |X| ≤ d0 + d, and x ∈ X such that
x ∈ X1 \ X2 . By Lemma 3, there is an LPR sequence L = (x1 , . . . , xk ) turning
T1 into T ∗ , where {x1 , . . . , xk } = X1 . As x ∈ X1 , by Lemma 4, the leaves
appearing in L can be reordered, and we may assume that x = x1 . Finally by
Lemma 10, if T 0 satisfies dLR (T 0 , T ∗ ) ≤ d1 − 1 and T 0 can be obtained from T1
by an LPR move on x, then T 0 ∈ P . As we are making one recursive call to
mastrl-distancefor each tree in P , this proves that one such call replaces T1
by T 0 such that dLR (T 0 , T ∗ ) = d1 − 1.
As for the complexity, recall from Lemma 7 that the (d + d0 )-disagreement
kernel S computed in line 8 contains at most 8d2 labels.Therefore when Algorithm 6 enters the ’for’ loop of line 9, it branches into at most 8d2 cases, one
for each x ∈ S. Within each of these cases, the algorithm enters at most |P |
recursive calls, each of which decrements d0 . As |P | ≤ 18(d+d0 )+8 ≤ 36d+8 by
Lemma 10, a single call of the algorithm splits into at most 8d2 (36d+8) = O(d3 ),
each of which decrements d0 . Therefore, the branching tree created by the algorithm has degree at most cd3 (for some constant c) and depth at most d, and
so O(cd d3d ) cases are considered.
As dLR (T1 , Ti ) can be calculated in O(n log n) time for each Ti , a single call
of lines 2-5 of the algorithm takes O(tn log n) time. A single call of lines 6-8
takes O(n2 ) time by Lemma 10. Thus the total time for all calls of lines 2-8 is
O(cd d3d n(n2 + t log n). Each call of line 10 occurs just before a recursive call to
the algorithm, as so line 10 is called at most O(cd d3d ) times. A single call of line
10 takes O(n(log n+18(d+d0 )+8)) = O(n(log n+36d)) time by Lemma 10, and
so the total time for all calls of line 10 is O(cd d3d n(log n + 36d)). Thus in total,
we have that the running time of the algorithm is O(cd d3d (n2 + n(t log n + 36d)).
As we may assume d ≤ n, this simplifies to O(cd d3d (n2 + tn log n)).

36

Algorithm 6 FPT algorithm for parameter d.
1:

2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

procedure mastrl−distance(T = (T1 , T2 , . . . , Tt ), d, d0 )
T is the set of input trees (represented as a sequence to distinguish T1 from
the other trees), d is the maximum number of leaves we can remove in a
tree, d0 is the maximum number of leaves we can move in T1 , which should
be initially set to d.
if dLR (T1 , Ti ) ≤ d for each Ti ∈ T then
Return T1
else if there is some Ti ∈ T such that dLR (T1 , Ti ) > d0 + d then
Return FALSE #handles the d0 ≤ 0 case
else
. here we ‘guess’ a leaf prune-and-regraft move on T1
Choose Ti ∈ T such that dLR (T1 , Ti ) > d
Set S = disagreement-kernel(d + d0 , T1 , Ti )
for x ∈ S do . we are ‘guessing’ that x should go where Ti wants
it.
Set P = candidate-trees(T1 , Ti , x, d, d0 )
T ∗ = F ALSE
for T ∈ P do
T 0 = mastrl−distance((T, T2 , . . . , Tt ), d, d0 − 1)
if T 0 is not F ALSE, let T ∗ := T 0
Return T ∗

37

