Efficient FPT algorithms for (strict) compatibility
of unrooted phylogenetic trees⋆
Julien Baste1 , Christophe Paul1 , Ignasi Sau1 , and Celine Scornavacca2

arXiv:1604.03008v1 [] 11 Apr 2016

1

2

CNRS, LIRMM, Université de Montpellier, Montpellier, France.
{baste, paul, sau}@lirmm.fr
Institut des Sciences de l’Evolution (Université de Montpellier, CNRS, IRD,
EPHE), Montpellier, France.
celine.scornavacca@umontpellier.fr

Abstract. In phylogenetics, a central problem is to infer the evolutionary relationships between a set of species X; these relationships are often
depicted via a phylogenetic tree – a tree having its leaves univocally labeled by elements of X and without degree-2 nodes – called the “species
tree”. One common approach for reconstructing a species tree consists
in first constructing several phylogenetic trees from primary data (e.g.
DNA sequences originating from some species in X), and then constructing a single phylogenetic tree maximizing the “concordance” with the
input trees. The so-obtained tree is our estimation of the species tree
and, when the input trees are defined on overlapping – but not identical – sets of labels, is called “supertree”. In this paper, we focus on
two problems that are central when combining phylogenetic trees into
a supertree: the compatibility and the strict compatibility problems for
unrooted phylogenetic trees. These problems are strongly related, respectively, to the notions of “containing as a minor” and “containing as
a topological minor” in the graph community. Both problems are known
to be fixed-parameter tractable in the number of input trees k, by using
their expressibility in Monadic Second Order Logic and a reduction to
graphs of bounded treewidth. Motivated by the fact that the dependency
on k of these algorithms is prohibitively large, we give the first explicit
dynamic programming algorithms for solving these problems, both run2
ning in time 2O(k ) · n, where n is the total size of the input.
Keywords: Phylogenetics; compatibility; unrooted phylogenetic trees;
parameterized complexity; FPT algorithm; dynamic programming.

1

Introduction

A central goal in phylogenetics is to clarify the relationships of extant species in
an evolutionary context. Evolutionary relationships are commonly represented
⋆

An extended abstract of this work will appear in the Proceedings of the 11th International Conference on Algorithmic Aspects of Information and Management
(AAIM), Bergamo, Italy, July 2016.

2

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

via phylogenetic trees, that is, acyclic connected graphs where leaves are univocally labeled by a label set X, and without degree-2 nodes. When a phylogenetic
tree is defined on a label set X designating a set of genes issued from a gene
family, we refer to it as a gene tree, while, when X corresponds to a set of extant
species, we refer to it as a species tree. A gene tree can differ from the species
tree depicting the evolution of the species containing the gene for a number of
reasons [15]. Thus, a common way to estimate a species tree for a set of species
X is to choose several gene families that appear in the genome of the species in
X, reconstruct a gene tree per each gene family (see [10] for a detailed review
of how to infer phylogenetic trees), and finally combine the trees in a unique
tree that maximizes the “concordance” with the given gene trees. The rationale
underlying this approach is the confidence that, using several genes, the species
signal will prevail and emerge from the conflicting gene trees. If the gene trees
are all defined on the same label set, we are in the consensus setting; otherwise
the trees are defined on overlapping – but not identical – sets of labels, and we
are in the supertree setting. Several consensus and supertree methods exist in the
literature (see [2, 3, 17] for a review), and they differ in the way the concordance
is defined.
In this paper, we focus on a problem that arises in the supertree setting: given
a set of gene trees T = {T1 , . . . , Tk } on label sets {X1 , . . . , Xk }, respectively, does
there exist a species tree on X := ∪ki=1 Xi that displays all the trees in T ? This is
the so-called Compatibility of Unrooted Phylogenetic Trees problem.
The notion of “displaying” used by the phylogenetic community, which will be
formally defined in Section 2, coincides with that of “containing as a minor” in the
graph community. Another related problem is the Strict Compatibility (or
Agreement) of Unrooted Phylogenetic Trees problem, where the notion
of “displaying” is replaced by that of “strictly displaying”. This notion, again
defined formally in Section 2, coincides with that of “containing as a topological
minor” in the graph community.
Both problems are polynomial-time solvable when the given gene trees are
out-branching (or rooted in the phylogenetic literature), or all contain some
common label [1,16]. In the general case, both problems are NP-complete [19] and
fixed-parameter tractable in the number of trees k [5, 18]. The fixed-parameter
tractability of these problems has been established via Monadic Second Order
Logic (MSOL) together with a reduction to graphs of bounded treewidth. For
both problems, it can be checked that the corresponding MSOL formulas [5, 18]
contain 4 alternate quantifiers, implying by [11] that the dependency on k in
the derived algorithms is given by a tower of exponentials of height 4; clearly,
this is prohibitively large for practical applications. Therefore, even if the notion
of compatibility has been defined quite some time ago [12], at the moment no
“reasonable” FPT algorithms exist for these problems, that is, algorithms with
running time f (k) · p(|X|), with f a moderately growing function and p a lowdegree polynomial. In this paper we fill this lack and we prove the following two
theorems.

FPT algorithms for compatibility of unrooted phylogenetic trees

3

Theorem 1. The Compatibility of Unrooted Phylogenetic Trees prob2
lem can be solved in time 2O(k ) · n, where k is the number of trees and n is the
total size of the input.
Theorem 2. The Agreement of Unrooted Phylogenetic Trees problem
2
can be solved in time 2O(k ) · n, where k is the number of trees and n is the total
size of the input.
Our approach for proving the two above theorems is to present explicit dynamic programming algorithms on graphs of bounded treewidth. As one could
suspect from the fact that the corresponding MSOL formulas are quite involved [5, 18], it turns out that our dynamic programming algorithms are quite
involved as well, implying that we are required to use a technical data structure.
This paper is organized as follows. In Section 2 we provide some preliminaries
and we define the problems under study. In Section 3 we present our algorithm for
the Compatibility of Unrooted Phylogenetic Trees problem, and the
algorithm for the Agreement of Unrooted Phylogenetic Trees problem
is given in Section 4. Finally, we provide some directions for further research in
Section 5.

2

Preliminaries

Basic definitions. Given a positive integer k, we denote by [k] the set of all
integers between 1 and k. If S is a set, we denote by 2S the set of all subsets of
S. A tree T is an acyclic connected graph. We denote by V (T ) its vertex set, by
E(T ) its edge set, and by L(T ) its set of vertices of degree one, called leaves. Two
trees T and T ′ are isomorphic if there is a bijective function α : V (T ) ∪ E(T ) →
V (T ′ ) ∪ E(T ′ ) such that for every edge e = {u, v} ∈ E(T ), α(e) = {α(u), α(v)}.
If T is a tree and S is a subset of V (T ), we denote by T [S] the subgraph of T
induced by S. Suppressing a degree-2 vertex v in a graph G consists in deleting
v and adding an edge between the former neighbors of v, if they are not already
adjacent. Identifying two vertices v and v ′ of a graph G consists in creating a
graph H by removing v and v ′ and adding a new vertex w such that, for each
u ∈ V (G) \ {v, v ′ }, there is an edge {u, w} in E(H) if and only if {u, v} ∈ E(G)
or {u, v ′ } ∈ E(G). Contracting an edge e = {u, v} in G consists in identifying u
and v. A graph H is a minor (resp. topological minor ) of a graph G if H can
be obtained from a subgraph of G by contracting edges (resp. contracting edges
with at least one vertex of degree 2). See [9] for more details about the notions
of minor and topological minor. If Y is a subset of vertices of a tree T , then T |Y
is the tree obtained from the minimal subtree of T containing Y by suppressing
degree-2 vertices. For simplicity, we may sometimes consider the vertices of T |Y
also as vertices of T .
As already mentioned in the introduction, an unrooted phylogenetic tree on
a label set X is defined as a pair (T, φ) with T a tree with no degree-2 vertex
along with a bijective function φ : L(T ) → X. We say that a vertex v ∈ L(T )
is labeled with label φ(v). Two unrooted phylogenetic trees (T, φ) and (T ′ , φ′ )

4

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

are isomorphic if there exists an isomorphism α from T to T ′ satisfying that if
v ∈ L(T ) then φ′ (α(v)) = φ(v).
The three graph operations defined above, namely suppressing a vertex, identifying two vertices, and contracting an edge, can be naturally generalized to
unrooted phylogenetic trees. In this context, two vertices to be identified are
either both unlabeled or both with the same label. In the latter case, the newly
created vertex inherits the label of the identified vertices. Finally, contractions
in unrooted phylogenetic trees are restricted to edges incident to two unlabeled
vertices. In this case, we speak about upt-contraction. If (T, φ) is an unrooted
phylogenetic tree and Y is subset of leaves of L(T ), then (T, φ)|Y is the unrooted
phylogenetic tree (T |Y , φ|Y ) where φ|Y is the restriction of φ to the label set Y .
(Strictly) Compatible supertree. Let T = {(T1 , φ1 ), (T2 , φ2 ), . . . , (Tk , φk )}
be a collection of unrooted phylogenetic trees, not necessarily on the same label
set. We say that an unrooted phylogenetic tree (T, φ) is a compatible supertree of
T if for every i ∈ [k], (Ti , φi ) ∈ T can be obtained from (T, φ)|L(Ti ) by performing
upt-contractions. The phylogenetic tree (T, φ) is a strictly compatible supertree
of T if for every i ∈ [k], (Ti , φi ) ∈ T is isomorphic to (T, φ)|L(Ti ) . If a collection
T of unrooted phylogenetic trees admits a (strictly) compatible supertree, then
we say that T is (strictly) compatible. The two definitions are equivalent when
T contains only binary phylogenetic trees, that is, unrooted trees in which every
vertex that is not a leaf has degree 3. Note that, as mentioned in the introduction,
the notions of “being a compatible supertree” and “being a strictly compatible
supertree” correspond, modulo the conditions on the labels, to the notions of
“containing as a minor” and “containing as a topological minor”, respectively.
In this paper we consider the following problem:
Compatibility of Unrooted Phylogenetic Trees
Instance: A set T of k unrooted phylogenetic trees.
Parameter: k.
Question: Does there exist an unrooted phylogenetic tree (T, φ) that is a compatible supertree of T ?
The Agreement (or Strict Compatibility) of Unrooted Phylogenetic Trees problem is defined analogously, just by replacing “compatible supertree” with “strictly compatible supertree”. For notational simplicity, we may
henceforth drop the function φ from an unrooted phylogenetic tree (T, φ), and
just assume that each leaf of T comes equipped with a label.
Assume that Tb is a compatible supertree of T . Then, according to the definition of minor, for every i ∈ [k], every vertex v ∈ V (Ti ) can be mapped to a
subtree of Tb, in such a way that the subtrees corresponding to the vertices of
the same tree are pairwise disjoint. We call the set of vertices of that subtree the
vertex-model of v. Observe that by the definition of the upt-contraction operation, the vertex-model of a leaf is a singleton. Hereafter, we denote by ϕ(v)
b
the
subset of vertices belonging to the vertex-model of v. Moreover, if u, v ∈ V (Ti )
are two adjacent vertices in Ti , then there is exactly one edge in Tb that connects

FPT algorithms for compatibility of unrooted phylogenetic trees

5

the vertex-model of u to the vertex-model of v. We call such an edge of Tb the
edge-model of {u, v} ∈ E(Ti ). Observe that a vertex of Tb may belong to several
vertex-models, but then these vertex-models correspond to vertices from different trees of T . Also, an edge of Tb may be the edge-model of edges of different
trees of T .
Similarly, if Tb is a strictly compatible supertree of T , then according to
the definition of topological minor, for every i ∈ [k], every vertex v ∈ V (Ti )
can be mapped to a vertex of Tb, called the vertex-model of v, in such a way
that this mapping is injective when restricted to every i ∈ [k]. In this case, if
u, v ∈ V (Ti ) are two adjacent vertices in Ti , then there is exactly one path in
Tb that connects the vertex-model of u to the vertex-model of v called the edgemodel of {u, v} ∈ E(Ti ). Similarly to the vertex-models, the edge-models of the
same tree need to be pairwise disjoint, except possibly for their endvertices.
Treewidth. A tree-decomposition of width w of a graph G = (V, E) is a pair
(T, B), where T is a tree and B = {Bt | Bt ⊆ V, t ∈ V (T)} such that
S
• t∈V (T) Bt = V ,
• for every edge {u, v} ∈ E there is a t ∈ V (T) such that {u, v} ⊆ Bt ,
• Bi ∩ Bk ⊆ Bj for all {i, j, k} ⊆ V (T) such that j lies on the unique path
from i to k in T, and
• maxt∈V (T) |Bt | = w + 1.
To avoid confusion, we speak about the nodes of a tree-decomposition and
the vertices of a graph. The sets of B are called bags. The treewidth of G, denoted
by tw(G), is the smallest integer w such that there is a tree-decomposition of G
of width w.
Theorem 3 (Bodlander et al. [4]). Let G be a graph and k be an integer.
In time 2O(k) · n, we can either decide that tw(G) > k or construct a treedecomposition of G of width at most 5k + 4.
A tree-decomposition (T, B) rooted at a distinguished node tr is nice if the
following conditions are fulfilled:
Btr = ∅ and this is the only empty bag,
each node has at most two children,
for each leaf t ∈ V (T), |Bt | = 1,
if t ∈ V (T) has exactly one child t′ , then either
◦ Bt = Bt′ ∪ {v} for some v 6∈ Bt′ and t is called an introduce-vertex node,
or
◦ Bt = Bt′ \ {v} for some v ∈ Bt′ and t is called a forget-vertex node, or
◦ Bt = Bt′ , t is associated with an edge {x, y} ∈ E(G) with x, y ∈ Bt , and
t is called an introduce-edge node. We add the constraint that each edge
of G labels exactly one node of T .
• and if t ∈ V (T) has exactly two children t′ and t′′ , then Bt = Bt′ = Bt′′ .
Then t is called a join node.

•
•
•
•

6

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

Note that we follow closely the definition of nice tree-decomposition given
in [7], which slightly differs from the usual one [13]. Given a tree-decomposition,
then we can build a nice tree-decomposition of G with the same width in polynomial time [7, 13].
Let (T, B) be a nice tree-decomposition of a graph G. For each node t ∈ V (T),
we define the graph Gt = (Vt , Et ) where Vt is the union of all bags corresponding
to the descendant nodes of t, and Et is the set of all edges introduced by the
descendant nodes of t. Observe that the graph Gt may be disconnected.
The display graph. Let T = {(T1 , φ1 ), (T2 , φ2 ), . . . , (Tk , φk )} be a collection
of unrooted phylogenetic trees. The display graph DT = (VD , ED ) of T is the
graph obtained from the disjoint union of the trees in T by iteratively identifying
every pair of labeled vertices with the same label. We denote by LD the set of
vertices of DT resulting from these identifications. The elements of LD are called
the labeled vertices. Observe that every vertex of VD \ LD (resp. every edge of
ED ) is also a vertex (resp. an edge) of some tree Ti ∈ T . If v is a vertex of LD ,
then we will say, with a slight abuse of notation, that v is a vertex of Ti if it
results from the identification of some leaf of Ti . Finally, the display graph DT
is equipped with a coloring function c : VD ∪ ED → {0, . . . , k} defined as follows.
If v ∈ LD , then we set c(v) = 0; if v ∈ (VD \ LD ) ∪ ED belongs to the tree Ti ,
we set c(v) = i. Observe that if a vertex v ∈ LD is incident to an edge e such
that c(e) = i, then v belongs to Ti . Suppose that Tb is a (strictly) compatible
supertree of T . Then we extend the definition of vertex-model and edge-model
for the vertices and edges of the Ti ’s to the vertices and edges of the display
graph DT .
The following theorem provides a bound on the treewith of the display graph
of a (strictly) compatible family of unrooted phylogenetic trees:
Theorem 4 (Bryant and Lagergren [5]). Let T = {(T1 , φ1 ), (T2 , φ2 ), . . . , (Tk , φk )}
be a collection of (strictly) compatible unrooted phylogenetic trees, not necessarily
on the same label set. The display graph of T has treewidth at most k.

3

Compatibility version

This section provides a proof of Theorem 1. We describe the algorithm in Subsection 3.1, we prove its correctness in Subsection 3.2, and we analyze its running
time in Subsection 3.3.
3.1

Description of the algorithm

Let D = (VD , ED ) be the display graph of a collection T = {(T1 , φ1 ), (T2 , φ2 ), . . . , (Tk , φk )}
of unrooted phylogenetic trees, and let n = |V (D)|. By Theorem 3 and Theorem 4, we may assume that we are given a nice tree-decomposition (T, B) of
D of width at most 5k + 4, as otherwise we can safely conclude that T is not
compatible. Let tr be the root of T, and recall that Btr = ∅.

FPT algorithms for compatibility of unrooted phylogenetic trees

7

Our objective is to build a compatible supertree Tb of T , if such exists. (We
would like to note that there could exist an exponential number of compatible
supertrees; we are just interested in constructing one of them.) As it is usually the
case of dynamic programming algorithms on tree-decompositions, for building
Tb we process (T, B) in a bottom-up way from the leaves to the root, where we
will eventually decide whether a solution exists or not. We first describe the
data structure used by the algorithm along with a succinct intuition behind
the defined objects, and then we proceed to the description of the dynamic
programming algorithm itself.
Description of the data structure. Before defining the dynamic-programming
table associated with every node t of (T, B), we need a few more definitions.
Definition 1. Given a node t of (T, B), its graph Gt = (Vt , Et ), and a subset
Z ⊆ Vt , a (Z, t)-supertree is a tuple T = (T, ϕ, ψ, ρ) such that
• T is a tree containing at most |Bt | + |Z| vertices,
• ϕ : Z → 2V (T ) , called the vertex-model function, associates every v ∈ Z
with a subset ϕ(v) such that
◦ T [ϕ(v)] is connected and if v is a labeled vertex, then |ϕ(v)| = 1, and
◦ if u and v are two vertices of Z such that c(u) = c(v), then ϕ(u)∩ϕ(v) =
∅,
• ψ : E(T ) → 2[k] , called the edge-model function, associates a subset of colors
with every edge of T , and
• ρ : Z → V (T ), called the vertex-representative function, selects, for each
vertex v ∈ Z, a representative ρ(v) in the vertex-model ϕ(v) ⊆ V (T ).
Moreover, we say that a (Z, t)-supertree (T, ϕ, ψ, ρ) is valid if
• for every {u, v} ∈ Et such that u, v ∈ Z, then the unique edge e between ϕ(u)
and ϕ(v) exists in T and satisfies c({u, v}) ∈ ψ(e).
For a node t of (T, B), we define a Bt -supertree as a (Bt , t)-supertree and a
Vt -supertree as a (Vt , t)-supertree.
To give some intuition on why (Z, t)-supertrees capture partial solutions of
our problem, let us assume that Tb is a compatible supertree of T and consider
a node t of (T, B). Then we can define a Bt -supertree T = (T, ϕ, ψ, ρ) as follows:
• For every vertex v ∈ Bt , ρ(v) can be chosen as any element in the set ϕ(v),
b
S
b
ρ(v),
• T = T |Y , where Y =
v∈Bt

• for every vertex v ∈ Bt , ϕ(v) = V (T ) ∩ ϕ(v),
b
where ϕ(v)
b
is the vertex-model
of v in Tb, and
• for every edge e ∈ E(T ), i ∈ ψ(e) if there exist an edge {u, v} ∈ Et , with
c({u, v}) = i, and an edge f ∈ E(Tb) such that f is incident to a vertex of
ϕ(u)
b
and to a vertex of ϕ(v),
b
and f is on the unique path in Tb between the
vertices incident to e.

8

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

The edge-model function ψ introduced in Definition 1 allows to keep track,
for every edge e ∈ E(T ), of the set of trees in T containing an edge having e as
an edge-model. Observe that the size of a vertex-model ϕ(v)
b
in Tb of some vertex
v ∈ VD may depend on n (so, a priori, we may need to consider a number of
vertex-models of size exponential in n). We overcome this problem via the vertexrepresentative function ρ, which allows us to store a tree T of size at most 2k.
This tree T captures how the vertex-models in Tb “project” to the current bag,
namely Bt , of the tree-decomposition of the display graph.
Before we describe the information stored at each node of the tree-decomposition,
we need three more definitions.
Definition 2. A tuple Ts = (Ts , ϕs , ψs , ρs ) is called a shadow Bt -supertree if
there exists a Bt -supertree T = (T, ϕ, ψ, ρ) such that
• Ts is a tree obtained from T by subdividing every edge once, called shadow
tree. The new vertices are called shadow vertices and denoted by S(Ts ), while
the original ones, that is, V (Ts ) \ S(Ts ), are denoted by O(Ts ),
• for every v ∈ Bt , ϕs (v) is a subset of V (Ts ) such that Ts [ϕs (v)] is connected
and such that ϕ(v) = ϕs (v) ∩ O(Ts ), where we licitly consider the vertices in
ϕ(v) as a subset of O(Ts ). Furthermore, if u, v ∈ Bt with c(u) = c(v), then
ϕs (u) ∩ ϕs (v) = ∅,
• ψs : E(Ts ) → 2[k] such that for every s ∈ S(Ts ), if x and y are the neighbors
of s in Ts , then ψs ({x, s}) = ψs ({s, y}) = ψ({x, y}), and
• ρs : Bt → V (Ts ) such that for every v ∈ Bt , ρs (v) = ρ(v).
We say that Ts is a shadow of T. Note that T may have more than one
shadow satisfying Definition 2.
Definition 3. Let T = (T, ϕ, ψ, ρ) be a (Z, t)-supertree. The restriction of T to
a subset of vertices Y ⊆ Vt is defined as the (Y, t)-supertree T|Y = (T̃ , ϕ̃, ψ̃, ρ̃),
where
• T̃ = T |Z , where Z = {ρ(v) | v ∈ Y },
• for every v ∈ Y , ϕ̃(v) = ϕ(v)S∩ V (T |Y ),
• for every e ∈ E(T̃ ), ψ̃(e) = f ∈E(Pe ) ψ(f ), where Pe is the unique path in
T between the vertices incident to e, and
• for every v ∈ Y , ρ̃(v) = ρ(v).
If T is a (Z, t)-supertree and Bt ⊆ Z, we define a shadow restriction of T to Bt
as a shadow of T|Bt , and we denote it by T|sBt .
Definition 4. Two (Z, t)-supertrees T = (T, ϕ, ψ, ρ) and T′ = (T ′ , ϕ′ , ψ ′ , ρ′ ) are
equivalent, and we denote it by T ≃ T′ , if there exists an isomorphism α from
T to T ′ such that
• ∀v ∈ Z, ∀a ∈ ϕ(v), α(a) ∈ ϕ′ (v),
• ∀e ∈ E(T ), ψ(e) = ψ ′ (α(e)), and
• ∀v ∈ Z, α(ρ(v)) = ρ′ (v).

FPT algorithms for compatibility of unrooted phylogenetic trees

9

Every node t of (T, B) is associated with a set Rt of pairs (T, γ), called
colored shadow Bt -supertrees, where T = (T, ϕ, ψ, ρ) is a shadow Bt -supertree
and γ : V (T ) → 2[k] is the so-called coloring function. The dynamic programming
algorithm will maintain the following invariant:
Invariant 1 A colored shadow Bt -supertree (T = (T, ϕ, ψ, ρ), γ) belongs to Rt
if and only if there exists a valid Vt -supertree Tps = (Tps , ϕps , ψps , ρps ) such that
(1) T ≃ Tps |sBt ,
(2) for every a ∈ V (T ), a color i ∈ γ(a) if and only if there exists u ∈ Vt with
c(u) = i such that a ∈ ϕps (u), and
(3) for every z ∈ S(T ) with neighbors x and y in V (T ), a color i ∈ γ(z) if
there exists u ∈ Vt with c(u) = i and x, y 6∈ ϕps (u) such that the unique path
between x and y in Tps uses at least one vertex of ϕps (u).
Intuitively, condition (2) of Invariant 1 guarantees that for every vertex
v ∈ V (T ), we can recover the set of trees for which v has already appeared
in a vertex-model of a vertex of Vt \ Bt . On the other hand, condition (3) of
Invariant 1 is useful for the following reason. When a vertex is forgotten in the
tree-decomposition, we need to keep track of its “trace”, in the sense that the
colors given to the corresponding shadow vertex guarantee that the algorithm
will construct vertex-models appropriately. If γ is a coloring function satisfying
conditions (2) and (3), we say that γ is consistent with Tps .
For Z = ∅, we denote by ⊘ the unique colored shadow (Z, t)-supertree. From
the above description, it follows that the collection T is compatible if and only
if ⊘ ∈ Rtr . Indeed, for t = tr we have that Btr = ∅ and Vtr = VD . In that
case, the only condition imposed by Invariant 1 is the existence of a valid VD supertree. Then, by Definition 1, the existence of such a supertree is equivalent
to the existence of a compatible supertree Tb of T in which the vertex-models
and edge-models are given by the functions ϕ and ψ, respectively. Finally, note
that the first condition of Definition 1, namely that |Tb| ≤ |Btr | + |Vtr | = |VD |, is
not a restriction on the set of solutions, as we may clearly assume that the size
of a compatible supertree is always at most the size of the display graph.
Description of the dynamic programming algorithm. Let (T, B) be a nice
tree-decomposition of the display graph D of T . We proceed to describe how to
compute the set Rt for every node t ∈ T. For that, we will assume inductively
that, for every descendant t′ of t, we have at hand the set Rt′ that has been
correctly built. We distinguish several cases depending on the type of node t:
1. t is a leaf with Bt = {v}: Rt = {((T, ϕ, ψ, ρ), γ)}, where T is a tree with
only one vertex a, ρ(v) = a, ϕ(v) = {a}, ψ : ∅ → 2[k] , and γ(a) = {c(v)}.
2. t is an introduce-vertex node such that the introduced vertex v is
unlabeled: For every element (T′ = (T ′ , ϕ′ , ψ ′ , ρ′ ), γ ′ ) of Rt′ , we add to Rt
the elements of the form (T = (T, ϕ, ψ, ρ), γ) that can be built according

10

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

a

x

y

x

x

a

x

y

x

x

s

a

b
s
a

(i)

(ii)

y

(iii)

s1

y
s2
a

(iv)

Fig. 1. The four possible cases (i-iv) in the dynamic programming algorithm.
The configurations above correspond to T ′ , while the ones below correspond to
T . Full dots correspond to vertices in O(T ), the other ones being in S(T ).

to one of the following four cases. For all of them, we define the vertexrepresentative function such that ρ(v) = a for some vertex a ∈ V (T ), and
for every u ∈ Bt′ , ρ(u) = ρ′ (u). The different cases depend on this vertex a.
(i) ρ(v) = a such that a ∈ V (T ′ ) and c(v) 6∈ γ ′ (a). See Figure 1(i) for an
example. We define T = T ′ . Let us define ϕ, ψ, and γ.
• Definition of the vertex-model function: T [ϕ(v)] is connected, contains a, and for every z ∈ ϕ(v), c(v) 6∈ γ ′ (z). For every u ∈ Bt′ ,
ϕ(u) = ϕ′ (u).
• Definition of the edge-model function: For every e ∈ E(T ), ψ(e) =
ψ ′ (e).
• Definition of the coloring function: For every z ∈ V (T ), γ(z) =
γ ′ (z) ∪ {c(v) | z ∈ ϕ(v)}.
(ii) ρ(v) = a and a subdivides an edge {x, y} of T ′ with c(v) 6∈
ψ ′ ({x, y}). See Figure 1(ii) for an example. Since T ′ is a shadow tree, assume w.l.o.g. that x ∈ O(T ′ ) and y ∈ S(T ′ ). Then T is obtained from T ′
by removing the edge {x, y}, adding two vertices a ∈ O(T ) and s ∈ S(T )
and three edges {x, s}, {s, a}, and {a, y}. Let us define ϕ, ψ, and γ.
• Definition of the vertex-model function: T [ϕ(v)] is connected, contains a, and for each z ∈ ϕ(v), c(v) 6∈ γ ′ (z). For each u ∈ Bt′ ,
T [ϕ(u)] is connected, ϕ′ (u) ⊆ ϕ(u) ⊆ ϕ′ (u) ∪ {a} ∪ S(T ), and if u is
unlabeled, then ϕ(u) = ϕ′ (u). For each u, u′ ∈ Bt with c(u) = c(u′ ),
ϕ(u) ∩ ϕ(u′ ) = ∅.
• Definition of the edge-model function: For each e ∈ E(T )\{{x, s}, {s, a}, {a, y}},
ψ(e) = ψ ′ (e). Also, ψ({x, s}) = ψ({s, a}) = ψ({a, y}) = ψ ′ ({x, y}).
• Definition of the coloring function: For each z ∈ O(T ) \ {a}, γ(z) =
γ ′ (z) ∪ {c(v) | z ∈ ϕ(v)}. γ(a) = {i | ∃u ∈ Bt : c(u) = i and
a ∈ ϕ(u)} ∪ ψ ′ ({x, y}). For each z ∈ S(T ′ ), γ(z) = γ ′ (z) ∪ {i | ∃u ∈
Bt : c(u) = i and z ∈ ϕ(u)}. Finally, γ(s) = {i | ∃u ∈ Bt : c(u) = i
and s ∈ ϕ(u)} ∪ ψ ′ ({x, y}).

FPT algorithms for compatibility of unrooted phylogenetic trees

11

(iii) ρ(v) = a with a ∈
/ V (T ′ ) and a is connected to a vertex x ∈ V (T ′ ).
See Figure 1(iii) for an example. T is obtained from T ′ by adding two
vertices a ∈ O(T ) and s ∈ S(T ) and two edges {a, s} and {s, x}. Let us
define ϕ, ψ, and γ.
• Definition of the vertex-model function: T [ϕ(v)] is connected, contains a, and for each z ∈ ϕ(v), c(v) 6∈ γ ′ (z). For each u ∈ Bt′ ,
T [ϕ(u)] is connected, ϕ′ (u) ⊆ ϕ(u) ⊆ ϕ′ (u) ∪ {a} ∪ S(T ), and if u is
unlabeled, then ϕ(u) = ϕ′ (u). For each u, u′ ∈ Bt with c(u) = c(u′ ),
ϕ(u) ∩ ϕ(u′ ) = ∅.
• Definition of the edge-model function: For each e ∈ E(T )\{{a, s}, {s, x}},
ψ(e) = ψ ′ (e), and ψ({a, s}) = ψ({s, x}) = ∅.
• Definition of the coloring function: For each z ∈ V (T )\{a, s}, γ(z) =
γ ′ (z) ∪ {c(v) | z ∈ ϕ(v)}. For each z ∈ {a, s}, γ(z) = {i | ∃u ∈ Bt :
c(u) = i and z ∈ ϕ(u)}.
(iv) ρ(v) = a with a ∈
/ V (T ′ ) and a subdivides an edge {x, y} of T ′ .
See Figure 1(iv) for an example. Again, we may assume that x ∈ O(T ′ )
and y ∈ S(T ′ ). Then T is obtained from T ′ by removing the edge {x, y},
adding four vertices a, b ∈ O(T ) and s1 , s2 ∈ S(T ), and five edges {x, s1 },
{s1 , b}, {b, y}, {a, s2 }, and {s2 , b}. Let us define ϕ, ψ, and γ.
• Definition of the vertex-model function: T [ϕ(v)] is connected, contains a and, for every z ∈ ϕ(v), c(v) 6∈ γ ′ (z). For each u ∈ Bt′ ,
T [ϕ(u)] is connected, ϕ′ (u) ⊆ ϕ(u) ⊆ ϕ′ (u)∪{a, b}∪S(T ), and if u is
unlabeled, then ϕ(u) = ϕ′ (u). For each u, u′ ∈ Bt with c(u) = c(u′ ),
ϕ(u) ∩ ϕ(u′ ) = ∅.
• Definition of the edge-model function: For each edge e ∈ E(T ) \
{{a, s2 }, {s2 , b}, {x, s1 }, {s1 , b}, {b, y}}, ψ(e) = ψ ′ (e). ψ({x, s1 }) =
ψ({s1 , b}) = ψ({b, y}) = ψ ′ ({x, y}), and ψ({a, s2 }) = ψ({s2 , b}) = ∅.
• Definition of the coloring function: For every z ∈ O(T ) \ {a, b},
γ(z) = γ ′ (z) ∪ {c(v) | z ∈ ϕ(v)}. For every z ∈ {a, s2 }, γ(z) =
{i | ∃u ∈ Bt : c(u) = i and z ∈ ϕ(u)}. For every z ∈ {b, s1 },
γ(z) = {i | ∃u ∈ Bt : c(u) = i and z ∈ ϕ(u)} ∪ ψ ′ ({x, y}). For every
z ∈ S(T ′ ), γ(z) = γ ′ (z) ∪ {i | ∃u ∈ Bt : c(u) = i and z ∈ ϕ(u)}.
3. t is an introduce-vertex node such that the introduced vertex v is
labeled: This case is very similar to Case 2 but, as vertex v is a leaf, only
Case 2(iii) and Case 2(iv) can be applied. In both cases, we further impose
that ϕ(v) = {a} and γ(v) = {i ∈ [k] | v ∈ L(Ti ), Ti ∈ T }.
4. t in an introduce-edge node for an edge {v, w} with c({v, w}) =
i: Let (T′ = (T ′ , ϕ′ , ψ ′ , ρ′ ), γ ′ ) be an element of Rt′ such that there exist
a ∈ ϕ′ (v) and b ∈ ϕ′ (w) such that {a, b} ∈ E(T ) and i 6∈ ψ ′ ({a, b}). We
construct (T = (T, ϕ, ψ, ρ), γ) as an element of Rt as follows: T = T ′ . For
every v ∈ Bt , ϕ(v) = ϕ′ (v). For every e ∈ E(T ) \ {{a, b}}, ψ(e) = ψ ′ (e).
ψ({a, b}) = ψ ′ ({a, b}) ∪ {i}. For every v ∈ V (T ), γ(v) = γ ′ (v).
5. t is a forget-vertex node for a vertex v: Let (T′ = (T ′ , ϕ′ , ψ ′ , ρ′ ), γ ′ ) be
an element of Rt′ . We construct (T = (T, ϕ, ψ, ρ), γ) as an element of Rt as

12

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

follows: T = T′ |zBt′ . For every a ∈ O(T ), γ(a) = γ ′ (a). For every z ∈ S(T ),
if x and y are the neighbors of z in T , then γ(z) = {i | ∃a ∈ V (T ′ ) on the
path between x and y in T ′ : (i ∈ γ ′ (a)) and (∀u ∈ Bt : a 6∈ ϕ′ (u))}.
6. t is a join node: Let (T′ = (T, ϕ, ψ ′ , ρ), γ ′ ) be an element of Rt′ and let
(T′′ = (T, ϕ, ψ ′′ , ρ), γ ′′ ) be an element of Rt′′ such that for every z ∈ V (T ),
γ ′ (z) ∩ γ ′′ (z) = ∅ and for every e ∈ E(T ), ψ ′ (z) ∩ ψ ′′ (z) = ∅. We construct
(T = (T, ϕ, ψ, ρ), γ) as an element of Rt as follows: For every e ∈ E(T ),
ψ(e) = ψ ′ (e) ∪ ψ ′′ (e), and for every z ∈ V (T ), γ(z) = γ ′ (z) ∪ γ ′′ (z).
3.2

Correctness of the algorithm

Let t be a node of (T, B). Our objective is to prove that, on the one hand, the
elements (T, γ) generated by the algorithm indeed belong to the set Rt (that is,
that they satisfy Invariant 1) and, on the other hand, that all the elements of
the set Rt are constructed by the algorithm. We will assume inductively that
both claims are true for every descendant t′ of t.
Our approach for proving that the generated elements belong to Rt is the
following. We distinguish again the cases of the algorithm. For each of them,
the assumption that Rt′ has been correctly built for every descendant t′ of t
guarantees the existence, for every element (T′ , γ ′ ) of Rt′ , of the corresponding
certificate T′ps that implies by Invariant 1 that (T′ , γ ′ ) ∈ Rt′ . We will then use
T′ps to prove, for each of the elements (T, γ) constructed by the algorithm, that
there exists a certificate Tps implying that (T, γ) ∈ Rt .
We would like to stress that, in order to prove that (T, γ) ∈ Rt , we only
need to worry about the existence of such a certificate Tps , and not about how it
can be constructed. However, if we are interested in constructing a compatible
supertree (and not only knowing whether it exists or not), we can easily do it
as well. Indeed, starting from the leaves of the tree-decomposition, by using the
operations described below we can inductively grow the certificates T′ps of Rt′
to get the certificates Tps of Rt , within the same running time of the algorithm.
We now proceed to distinguish the different cases of the dynamic programming algorithm presented in Subsection 3.1:
1. t is a leaf with Bt = {v}: Tps is a tree with only one vertex a, ρps (v) = a,
ϕps (v) = {a}, and ψps : ∅ → 2[k] .
2. t is an introduce-vertex node such that the introduced vertex v
is unlabeled: Given an element (T′ , γ ′ ) of Rt′ with the corresponding certificate T′ps , we distinguish the different cases of the algorithm that create
elements of the form (T, γ), and we define for each case a certificate Tps of
T, which implies that (T, γ) ∈ Rt .
′
(i) ρ(v) = a such that a ∈ V (T ′ ) and c(v) 6∈ γ ′ (a). Then Tps = Tps
. Let
us define ρps , ϕps , and ψps .
• Definition of the vertex-representative function:
∗ ρps (v) = ρ(v) = a and

FPT algorithms for compatibility of unrooted phylogenetic trees

13

∗ for every u ∈ Vt′ , ρps (u) = ρ′ps (u).
• Definition of the vertex-model function:
∗ Tps [ϕps (v)] is connected and contains a, ϕ(v) ∩ O(T ) = ϕps (v) ∩
O(T ),
∗ for every u ∈ Bt′ , ϕps (u) = ϕ′ps (u), and
∗ for every u, u′ ∈ Vt with c(u) = c(u′ ), ϕps (u) ∩ ϕps (u′ ) = ∅.
• Definition of the edge-model function:
′
∗ for every e ∈ E(T ), ψps (e) = ψps
(e).
(ii) ρ(v) = a and a subdivides an edge {x, y} of T ′ with c(v) 6∈
′
ψ ′ ({x, y}). Tps is obtained from Tps
by removing an edge {xps , yps } on
the path between x and y, and adding a vertex a and two edges {xps , a}
and {a, yps}. Let us define ρps , ϕps , and ψps .
• Definition of the vertex-representative function:
∗ ρps (v) = ρ(v) = a and
∗ for every u ∈ Vt′ , ρps (u) = ρ′ps (u).
• Definition of the vertex-model function:
∗ Tps [ϕps (v)] is connected and contains a,
∗ for every u ∈ Vt′ , Tps [ϕps (u)] is connected, ϕ′ps (u) ⊆ ϕps (u) ⊆
ϕ′ps (u) ∪ {a}, and if u is unlabeled, then ϕps (u) = ϕ′ps (u),
∗ for every u ∈ Bt , ϕ(u) ∩ O(T ) = ϕps (u) ∩ O(T ),
∗ for every u, u′ ∈ Vt with c(u) = c(u′ ), ϕps (u) ∩ ϕps (u′ ) = ∅, and
∗ for every {u, u′ } ∈ Et , there exist w ∈ ϕps (u) and w′ ∈ ϕps (u′ )
such that {w, w′ } ∈ E(Tps ).
• Definition of the edge-model function:
′
∗ for every e ∈ E(T ) \ {{xps , a}, {a, yps}}, ψps (e) = ψps
(e) and
′
∗ ψps ({xps , a}) = ψps ({a, yps }) = ψps ({xps , yps }).
(iii) ρ(v) = a with a ∈
/ V (T ′ ) and a is connected to a vertex x ∈ V (T ′ ).
′
Tps is obtained from Tps
by adding a vertex a and an edge {a, x}. Let us
define ρps , ϕps , and ψps .
• Definition of the vertex-representative function:
∗ ρps (v) = ρ(v) = a and
∗ for every u ∈ Vt′ , ρps (u) = ρ′ps (u).
• Definition of the vertex-model function:
∗ Tps [ϕps (v)] is connected and contains a,
∗ for every u ∈ Vt′ , Tps [ϕps (u)] is connected, ϕ′ps (u) ⊆ ϕps (u) ⊆
ϕ′ps (u) ∪ {a}, and if u is unlabeled, then ϕps (u) = ϕ′ps (u),
∗ for every u ∈ Bt , ϕ(u) ∩ O(T ) = ϕps (u) ∩ O(T ),
∗ for every u, u′ ∈ Vt with c(u) = c(u′ ), ϕps (u) ∩ ϕps (u′ ) = ∅, and
∗ for every {u, u′ } ∈ Et , there exist w ∈ ϕps (u) and w′ ∈ ϕps (u′ )
such that {w, w′ } ∈ E(Tps ).
• Definition of the edge-model function:
′
∗ for every e ∈ E(T ) \ {{a, x}}, ψps (e) = ψps
(e) and
∗ ψ({a, x}) = ∅.

14

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

(iv) ρ(v) = a with a ∈
/ V (T ′ ) and b subdivides an edge {x, y} of T ′ . Tps is
′
obtained from Tps by removing an edge {xps , yps } on the path between x
and y, and adding two vertices a and b and three edges {xps , b}, {b, yps},
and {a, b}. Let us define ρps , ϕps , and ψps .
• Definition of the vertex-representative function:
∗ ρps (v) = ρ(v) = a and
∗ for every u ∈ Vt′ , ρps (u) = ρ′ps (u).
• Definition of the vertex-model function:
∗ Tps [ϕps (v)] is connected and contains a,
∗ for every u ∈ Vt′ , Tps [ϕps (u)] is connected, ϕ′ps (u) ⊆ ϕps (u) ⊆
ϕ′ps (u) ∪ {a, b}, and if u is unlabeled, then ϕps (u) = ϕ′ps (u),
∗ for every u ∈ Bt , ϕ(u) ∩ O(T ) = ϕps (u) ∩ O(T ),
∗ for every u, u′ ∈ Vt with c(u) = c(u′ ), ϕps (u) ∩ ϕps (u′ ) = ∅, and
∗ for every {u, u′ } ∈ Et , there exist w ∈ ϕps (u) and w′ ∈ ϕps (u′ )
such that {w, w′ } ∈ E(Tps ).
• Definition of the edge-model function:
∗ for every e ∈ E(T ) \ {{a, b}, {xps, b}, {b, yps}}, ψ(e) = ψ ′ (e),
′
∗ ψps ({xps , b}) = ψps ({b, yps }) = ψps
({xps , yps }), and
∗ ψps ({a, b}) = ∅.
3. t is an introduce-vertex node such that the introduced vertex v is
labeled: As explained in the description of the algorithm, this case is very
similar to Case 2, taking into account that only Case 2(iii) and Case 2(iv)
can be applied, and by adding the following constraints:
• ϕps (v) = {a} and
• γps (v) = {i ∈ [k] | v ∈ L(Ti ), Ti ∈ T }.
In the next two cases, let (T′ , γ ′ ) be the element of Rt′ from which the algorithm
has started, let T′ps be a certificate of (T′ , γ ′ ), and let (T, γ) be the element created
by the algorithm. In both cases, we construct a certificate Tps of (T, γ ′ ) showing
that (T, γ) ∈ Rt .
4. t in an introduce-edge node for an edge {v, w} with c({v, w}) = i: We
construct Tps = (Tps , ϕps , ψps , ρps ) as follows:
′
• Tps = Tps
,
• for every v ∈ Vt , ϕps (v) = ϕ′ps (v),
′
• for every e ∈ E(T ) \ {{a, b}}, ψps (e) = ψps
(e), and
′
({a, b}) ∪ {i}.
• ψps ({a, b}) = ψps
5. t is a forget-vertex node for a vertex v: In this case, we just define
Tps = T′ps .
6. t is a join node: Let (T′ , γ ′ ) be the element of Rt′ and let (T′′ , γ ′′ ) be
the element of Rt′′ from which the algorithm has started, and let T′ps =
′
′′
(Tps , ϕps , ψps
, ρps ) and T′′ps = (Tps , ϕps , ψps
, ρps ) be their certificates, respectively. We define Tps = (Tps , ϕps , ψps , ρps ), that is, a certificate of (T, γ)
showing that (T, γ) ∈ Rt , just by setting, for every e ∈ E(T ), ψps (e) =
′
′′
ψps
(e) ∪ ψps
(e). Note that Tps , ϕps , and ρps are those given by (T′ , γ ′ ) (or by
′′
′′
(T , γ )).

FPT algorithms for compatibility of unrooted phylogenetic trees

15

Finally, let us argue that all the elements of the set Rt are indeed constructed
by the algorithm. Let (T, γ) be an element of Rt , with T = (T, ϕ, ψ, ρ), and our
objective is to show that the algorithm indeed generates this element (T, γ). In
order to do this, we need to consider each case of the algorithm separately. We
will only detail the arguments for Case 2, which is the most involved one, and
the other ones follow by using a similar argumentation.
By definition of the set Rt , there exists a valid Vt -supertree Tps such that
T = Tps |sBt and such that γ is consistent with Tps . Let T′ps = Tps |Vt′ . It can be
easily checked that T′ps is a valid Vt′ -supertree. Let T′ = T′ps |sBt′ and let γ ′ be the
coloring function consistent with T′ps . Then, as Invariant 1 is satisfied, (T′ , γ ′ ) is
an element of Rt′ . Note that T′ = T|Bt′ . As the sets Bt and Bt′ differ by just
one vertex, the elements T and T′ are quite close to each other. Indeed, the way
they differ is mainly given by the value of ρ(v), in the sense that we consider all
the possible ways to add a vertex ρ(v) to a tree T ′ . It appears that there are four
different ways to add ρ(v) to T ′ . Indeed, ρ(v) can either be an already existing
vertex of T ′ , or a new vertex that subdivides an edge, or a new vertex connected
to an already existing vertex, or a new vertex connected to another new vertex
that subdivides an edge. Our algorithm precisely explore these four possibilities
for ρ(v), and then updates T , ϕ, ψ, and γ in all the possible ways such that the
resulting element is still in R. So in particular, the algorithm necessarily created
the element (T, γ) of Rt , as we wanted to show.
3.3

Running time analysis of the algorithm

Let us now discuss the running time of the dynamic programming algorithm
described in Subsection 3.1. Let w be the width of (T, B), so we have that
w ≤ 5k + 4. For each t ∈ V (T), we bound the size of Rt as follows. Each
element in Rt is of the form (T = (T, ϕ, ψ, ρ), γ). Note that T has at most
3w nodes, and that there are at most (3w)3w−2 = 2O(k log k) distinct trees on
3w vertices [6]. There are at most 2|V (T )|·|Bt | ≤ 23w·w possible functions ϕ,
2|E(T )|·k ≤ 23w·k possible functions ψ, |V (T )||Bt | ≤ (3w)w possible functions ρ,
2
and 2|V (T )|·k ≤ 23w·k possible functions γ. Thus, it holds that |Rt | = 2O(k ) for
every node t of (T, B).
Concerning the complexity of computing Rt , we distinguish several cases.
This computation is trivial in Case 1 of the algorithm, that is, when t is a leaf.
In Cases 2, 3, 4, and 5, the set Rt can be clearly computed in time polynomial
in |Rt′ |, where t′ is the child of t. Finally, in Case 6, that is, when t is a join
node, the set Rt can also be clearly computed in time polynomial in |Rt′ | and
|Rt′′ |, where t′ and t′′ are the two children of t. Finally, as we can assume that
|V (T)| = O(n) [13], the running time claimed in Theorem 1 follows.

4

Agreement version

In this section we provide a proof of Theorem 2. Again, by Theorem 3 and
Theorem 4, we may assume that we are given a nice tree-decomposition (T, B)
of D of width at most 5k + 4.

16

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

The algorithm follows closely the one described in Subsection 3.1 for the
compatibility version, so we will just describe the changes to be done to deal
with the agreement version. Intuitively, these changes appear because now we
are looking for a supertree containing each of the trees in T as a topological
minor, instead of a minor, and this forces us to redefine the notions of vertexmodel and edge-model functions. Namely, each vertex-model becomes a single
vertex (instead of a set of vertices), and for guaranteeing the existence of the
appropriate topological minors, we have to keep track of the existence of pairwise
disjoint paths among the vertex-models of each color (instead of just edges).
We first proceed to partially redefine the data structure, and then we will
focus on the changes in the dynamic programming algorithm.
Changes in the data structure. For a node t of the tree-decomposition, our
tables Rt store again elements of the form (T, γ) satisfying the same invariant as
in Subsection 3.1, namely Invariant 1, the difference is that we update some definitions of the data structure. Namely, the vertex-model function in the definition
of (Z, t)-supertree, cf. Definition 1, is updated as follows:
• ϕ : Z → V (T ) is such that if u and v are two vertices of Z with c(u) = c(v),
then ϕ(u) 6= ϕ(v),
We also modify slightly the definition of “valid supertrees” and say that a (Z, t)supertree (T, ϕ, ψ, ρ) is valid if
• for every {u, v} ∈ Et such that u, v ∈ Z, every edge e on the path between
ϕ(u) and ϕ(v) in T satisfies c({u, v}) ∈ ψ(e) and
• if i ∈ ψ(e) for some i ∈ [k], then there exists a unique pair {u, v} ∈ Et with
u, v ∈ Z with c({u, v}) = i such that e lies on the path between ϕ(u) and
ϕ(v).
It is worth noting that the dynamic programming algorithm described below
satisfies that, for every vertex v ∈ Z, ϕ(v) = ρ(v), and therefore the vertexrepresentative function ρ becomes superfluous. Nevertheless, in order for the
notation to deviate as little as possible to that of Section 3, we keep ρ in the
tuple T.
Changes in the dynamic programming algorithm. The fact that the image
of the vertex-model function ϕ is now a single vertex allows us to substantially
simplify the algorithm. In particular, in the subcases of the two cases where t
is an introduce-vertex node (namely, Cases 2 and 3), we do not have to worry
anymore about how the image of ϕ grows when introducing a new vertex, except,
naturally, for this newly introduced vertex. The latter simplification implies that
we do not need to update the coloring function γ either, except again for the
newly introduced vertex. Finally, as the function ρ is now redundant, we may
omit it from the description of the algorithm.
More precisely, Cases 1, 2, 3, 5, and 6 of the algorithm from Subsection 3.1 remain unchanged, just by taking into account that ϕ(v) returns just one element,
namely ϕ(v) = a. The changes occur in Case 4, which becomes as follows:

FPT algorithms for compatibility of unrooted phylogenetic trees

17

4. t in an introduce-edge node for an edge {v, w} with c({v, w}) = i: Let
(T′ = (T ′ , ϕ′ , ψ ′ , ρ′ ), γ ′ ) be an element of Rt′ such that for each e ∈ Pv,w ,
i 6∈ ψ ′ (e), where Pv,w = {e ∈ E(T ) | e lies on the path between ϕ(v) and
ϕ(w)}. We construct (T = (T, ϕ, ψ, ρ), γ) as an element of Rt as follows:
• T = T ′,
• for every v ∈ Bt , ϕ(v) = ϕ′ (v),
• for every e ∈ E(T ) \ Pv,w , ψ(e) = ψ ′ (e),
• for every e ∈ Pv,w , ψ(e) = ψ ′ (e) ∪ {i}, and
• for every v ∈ V (T ), γ(v) = γ ′ (v).
The correctness of the algorithm can be proved analogously to the proof given
in Subsection 3.2. Finally, note that the analysis of the running time carried out
in Subsection 3.3 also applies to this case, as the size of the objects stored in the
tables is upper-bounded by the size of those used in the algorithm of Subsection 3.1. Furthermore, the performed operations incur the same time complexity,
except for the case of an introduce-edge node, for which in the previous algorithm we looked for the existence of an appropriate edge in T , whereas in the
current one we look for the existence of an appropriate path in T , which can be
performed in time O(|V (T )|). This additional running time is clearly dominated
2
by the overall running time of the algorithm, namely 2O(k ) · n.

5

Further research

In this paper we give the first “reasonable” FPT algorithms for the Compatibility and the Agreement problems for unrooted phylogenetic trees. Even
though this is, from a theoretical point of view, a big step further toward solving
this problem in reasonable time, our running times are still prohibitive to be of
any use in real-life phylogenomic studies, where k can go up very quickly [8]. One
possibility to design a practical algorithm is to devise reduction rules to keep k
small. Another possibility would be to design an FPT algorithm with respect
to a parameter that is smaller than the number of gene trees in phylogenomic
studies.
From a more theoretical perspective, a natural question is whether the func2
tion 2O(k ) in the running times of our algorithms can be improved. It would also
be interesting to prove lower bounds for algorithms parameterized by treewidth
to solve these problems, assuming the Exponential Time Hypothesis [14].

References
1. A. V. Aho, Y. Sagiv, T. G. Szymanski, and J. D. Ullman. Inferring a tree from
lowest common ancestors with an application to the optimization of relational
expressions. SIAM Journal of Computing, 10(3):405–421, 1981.
2. O. R. Bininda-Emonds. Phylogenetic supertrees: combining information to reveal
the tree of life, volume 4. Springer Science & Business Media, 2004.

18

Julien Baste, Christophe Paul, Ignasi Sau, and Celine Scornavacca

3. O. R. Bininda-Emonds, J. L. Gittleman, and M. A. Steel. The (super) tree of life:
procedures, problems, and prospects. Annual Review of Ecology and Systematics,
pages 265–289, 2002.
4. H. L. Bodlaender, P. G. Drange, M. S. Dregi, F. V. Fomin, D. Lokshtanov, and
M. Pilipczuk. An O(ck n) 5-Approximation Algorithm for Treewidth. In Proc. of
the IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS),
pages 499–508, 2013.
5. D. Bryant and J. Lagergren. Compatibility of unrooted phylogenetic trees is FPT.
Theoretical Computer Science, 351(3):296–302, 2006.
6. A. Cayley. A theorem on trees. Quarterly Journal of Mathematics, 23:376–378,
1889.
7. M. Cygan, J. Nederlof, M. Pilipczuk, M. Pilipczuk, J. M. M. van Rooij, and J. O.
Wojtaszczyk. Solving connectivity problems parameterized by treewidth in single
exponential time. In Proc. of the IEEE 52nd Annual Symposium on Foundations
of Computer Science (FOCS), pages 150–159, 2011.
8. F. Delsuc, H. Brinkmann, and H. Philippe. Phylogenomics and the reconstruction
of the tree of life. Nature Reviews Genetics, 6(5):361–375, 2005.
9. R. Diestel. Graph Theory, volume 173. Springer-Verlag, 4th edition, 2010.
10. J. Felsenstein. Inferring Phylogenies. Sinauer Associates, Incorporated, 2004.
11. M. Frick and M. Grohe. The complexity of first-order and monadic second-order
logic revisited. Annals of Pure and Applied Logic, 130(1-3):3–31, 2004.
12. A. D. Gordon. Consensus supertrees: the synthesis of rooted trees containing
overlapping sets of labeled leaves. Journal of classification, 3(2):335–348, 1986.
13. T. Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture
Notes in Computer Science. Springer, 1994.
14. D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential
time hypothesis. Bulletin of the EATCS, 105:41–72, 2011.
15. W. Maddison. Reconstructing character evolution on polytomous cladograms.
Cladistics, 5(4):365–377, 1989.
16. M. Ng and N. C. Wormald. Reconstruction of rooted trees from subtrees. Discrete
Applied Mathematics, 69(1-2):19–31, 1996.
17. C. Scornavacca. Supertree methods for phylogenomics. PhD thesis, Université
Montpellier II-Sciences et Techniques du Languedoc, 2009.
18. C. Scornavacca, L. van Iersel, S. Kelk, and D. Bryant. The agreement problem for
unrooted phylogenetic trees is fpt. Journal of Graph Algorithms and Applications,
18(3):385–392, 2014.
19. M. Steel. The complexity of reconstructing trees from qualitative characters and
subtrees. Journal of Classification, 9:91–116, 1992.

