Julien Baste
email: baste@lirmm.fr

Christophe Paul
email: paul@lirmm.fr

Ignasi Sau
email: sau@lirmm.fr

Celine Scornavacca
email: celine.scornavacca@umontpellier.fr

Ecient FPT algorithms for (strict) compatibility of unrooted phylogenetic trees

Keywords: Phylogenetics, compatibility, unrooted phylogenetic trees, parameterized complexity, FPT algorithm, dynamic programming

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 rst 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 dened 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 xed-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 rst explicit dynamic programming algorithms for solving these problems, both running in time 2 O(k 2 ) • n, where n is the total size of the input.

Introduction

A central goal in phylogenetics is to clarify the relationships of extant species in an evolutionary context. Evolutionary relationships are commonly represented 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 dened 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 dier from the species tree depicting the evolution of the species containing the gene for a number of reasons [START_REF] Maddison | Reconstructing character evolution on polytomous cladograms[END_REF]. 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 [START_REF] Felsenstein | Inferring Phylogenies[END_REF] for a detailed review of how to infer phylogenetic trees), and nally combine the trees in a unique tree that maximizes the concordance with the given gene trees. The rationale underlying this approach is the condence that, using several genes, the species signal will prevail and emerge from the conicting gene trees. If the gene trees are all dened on the same label set, we are in the consensus setting; otherwise the trees are dened 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 [START_REF] Bininda-Emonds | Phylogenetic supertrees: combining information to reveal the tree of life[END_REF][START_REF] Bininda-Emonds | The (super) tree of life: procedures, problems, and prospects[END_REF][START_REF] Scornavacca | Supertree methods for phylogenomics[END_REF] for a review), and they dier in the way the concordance is dened.

In this paper, we focus on a problem that arises in the supertree setting: given a set of gene trees T = {T 1 , . . . , T k } on label sets {X 1 , . . . , X k }, respectively, does there exist a species tree on X := ∪ k i=1 X i 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 dened 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 dened 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 [START_REF] Aho | Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions[END_REF][START_REF] Ng | Reconstruction of rooted trees from subtrees[END_REF]. In the general case, both problems are NP-complete [START_REF] Steel | The complexity of reconstructing trees from qualitative characters and subtrees[END_REF] and xed-parameter tractable in the number of trees k [START_REF] Bryant | Compatibility of unrooted phylogenetic trees is FPT[END_REF][START_REF] Scornavacca | The agreement problem for unrooted phylogenetic trees is fpt[END_REF]. The xed-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 [START_REF] Bryant | Compatibility of unrooted phylogenetic trees is FPT[END_REF][START_REF] Scornavacca | The agreement problem for unrooted phylogenetic trees is fpt[END_REF] contain 4 alternate quantiers, implying by [START_REF] Frick | The complexity of rst-order and monadic second-order logic revisited[END_REF] 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 dened quite some time ago [START_REF] Gordon | Consensus supertrees: the synthesis of rooted trees containing overlapping sets of labeled leaves[END_REF], 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 ll this lack and we prove the following two theorems.

Theorem 1. The Compatibility of Unrooted Phylogenetic Trees problem can be solved in time 2 O(k 2 ) • 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 can be solved in time 2 O(k 2 ) • 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 [START_REF] Bryant | Compatibility of unrooted phylogenetic trees is FPT[END_REF][START_REF] Scornavacca | The agreement problem for unrooted phylogenetic trees is fpt[END_REF], 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 dene the problems under study. In Section 3 we present our algorithm for the Compatibility of Unrooted Phylogenetic Trees problem. Due to space limitations, its proof of correctness and the analysis of its running time are given in Appendix A and Appendix B, respectively. The algorithm for the Agreement of Unrooted Phylogenetic Trees problem is entirely deferred to Appendix C. Finally, we provide some directions for further research in Section 4.

Preliminaries

Basic denitions. 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 2 S 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 [START_REF] Diestel | Graph Theory[END_REF] 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 dened 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 , φ ) are isomorphic if there exists an isomorphism α from T to T satisfying that if

v ∈ L(T ) then φ (α(v)) = φ(v).
The three graph operations dened 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 identied are either both unlabeled or both with the same label. In the latter case, the newly created vertex inherits the label of the identied 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 = {(T 1 , φ 1 ), (T 2 , φ 2 ), . . . , (T k , φ 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], (T i , φ 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], (T i , φ 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 denitions 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 dened 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 T is a compatible supertree of T . Then, according to the definition of minor, for every i ∈ [k], every vertex v ∈ V (T i ) can be mapped to a subtree of T , 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 denition of the upt-contraction operation, the vertex-model of a leaf is a singleton. Hereafter, we denote by ϕ(v) the subset of vertices belonging to the vertex-model of v. Moreover, if u, v ∈ V (T i ) are two adjacent vertices in T i , then there is exactly one edge in T that connects the vertex-model of u to the vertex-model of v. We call such an edge of T the edge-model of {u, v} ∈ E(T i ). Observe that a vertex of T may belong to several vertex-models, but then these vertex-models correspond to vertices from dierent trees of T . Also, an edge of T may be the edge-model of edges of dierent trees of T .

Similarly, if T is a strictly compatible supertree of T , then according to the denition of topological minor, for every i ∈ [k], every vertex v ∈ V (T i ) can be mapped to a vertex of T , 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 (T i ) are two adjacent vertices in T i , then there is exactly one path in T that connects the vertex-model of u to the vertex-model of v called the edgemodel of {u, v} ∈ E(T i ). 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 = {B t | B t ⊆ V, t ∈ V (T)} such that • t∈V (T) B t = V , • for every edge {u, v} ∈ E there is a t ∈ V (T) such that {u, v} ⊆ B t , • B i ∩ B k ⊆ B j
for all {i, j, k} ⊆ V (T) such that j lies on the unique path from i to k in T, and

• max t∈V (T) |B t | = 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. [START_REF] Bodlaender | An O(c k n) 5-Approximation Algorithm for Treewidth[END_REF]). Let G be a graph and k be an integer.

In time 2 O(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 t r is nice if the following conditions are fullled:

• B tr = ∅ and this is the only empty bag,

• each node has at most two children,

• for each leaf t ∈ V (T), |B t | = 1, • if t ∈ V (T) has exactly one child t , then either • B t = B t ∪ {v} for some v ∈ B t and t is called an introduce-vertex node, or • B t = B t \ {v} for some v ∈ B t and t is called a forget-vertex node, or • B t = B t , t is associated with an edge {x, y} ∈ E(G) with x, y ∈ B t , 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

B t = B t = B t .
Then t is called a join node.

Note that we follow closely the denition of nice tree-decomposition given in [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF], which slightly diers from the usual one [START_REF] Kloks | Computations and Approximations[END_REF]. Given a tree-decomposition, then we can build a nice tree-decomposition of G with the same width in polynomial time [START_REF] Cygan | Solving connectivity problems parameterized by treewidth in single exponential time[END_REF][START_REF] Kloks | Computations and Approximations[END_REF].

Let (T, B) be a nice tree-decomposition of a graph G. For each node t ∈ V (T), we dene the graph G t = (V t , E t ) where V t is the union of all bags corresponding to the descendant nodes of t, and E t is the set of all edges introduced by the descendant nodes of t. Observe that the graph G t may be disconnected.

The display graph. Let T = {(T 1 , φ 1 ), (T 2 , φ 2 ), . . . , (T k , φ k )} be a collection of unrooted phylogenetic trees. The display graph D T = (V D , E D ) 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 L D the set of vertices of D T resulting from these identications. The elements of L D are called the labeled vertices. Observe that every vertex of V D \ L D (resp. every edge of E D ) is also a vertex (resp. an edge) of some tree T i ∈ T . If v is a vertex of L D , then we will say, with a slight abuse of notation, that v is a vertex of T i if it results from the identication of some leaf of T i . Finally, the display graph D T is equipped with a coloring function c :

V D ∪ E D → {0, . . . , k} dened as follows. If v ∈ L D , then we set c(v) = 0; if v ∈ (V D \ L D ) ∪ E D belongs to the tree T i , we set c(v) = i. Observe that if a vertex v ∈ L D is incident to
an edge e such that c(e) = i, then v belongs to T i . Suppose that T is a (strictly) compatible supertree of T . Then we extend the denition of vertex-model and edge-model for the vertices and edges of the T i 's to the vertices and edges of the display graph D T .

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 [START_REF] Bryant | Compatibility of unrooted phylogenetic trees is FPT[END_REF]).

Let T = {(T 1 , φ 1 ), (T 2 , φ 2 ), . . . , (T k , φ 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.

Compatibility version

This section provides a proof of Theorem 1. Let D = (V D , E D ) be the display graph of a collection T = {(T 1 , φ 1 ), (T 2 , φ 2 ), . . . , (T k , φ 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 t r be the root of T, and recall that B tr = ∅.

Our objective is to build a compatible supertree T 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 T 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 rst describe the data structure used by the algorithm along with a succinct intuition behind the dened objects, and then we proceed to the description of the dynamic programming algorithm itself.

Description of the data structure. Before dening the dynamic-programming table associated with every node t of (T, B), we need a few more denitions.

Denition 1. Given a node t of (T, B), its graph G t = (V t , E t ), and a subset

Z ⊆ V t , a (Z, t)-supertree is a tuple T = (T, ϕ, ψ, ρ) such that • T is a tree containing at most |B t | + |Z| vertices, • ϕ : Z → 2 V (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} ∈ E t such that u, v ∈ Z, then the unique edge e between ϕ(u) and ϕ(v) exists in T and satises c({u, v}) ∈ ψ(e).

For a node t of (T, B), we dene a B t -supertree as a (B t , t)-supertree and a V t -supertree as a (V t , t)-supertree.

To give some intuition on why (Z, t)-supertrees capture partial solutions of our problem, let us assume that T is a compatible supertree of T and consider a node t of (T, B). Then we can dene a B t -supertree T = (T, ϕ, ψ, ρ) as follows:

• For every vertex v ∈ B t , ρ(v) can be chosen as any element in the set ϕ(v),

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

The edge-model function ψ introduced in Denition 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) in T of some vertex v ∈ V D 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 T project to the current bag, namely B t , 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 denitions. Denition 2. A tuple T s = (T s , ϕ s , ψ s , ρ s ) is called a shadow B t -supertree if there exists a B t -supertree T = (T, ϕ, ψ, ρ) such that • T s 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(T s ), while the original ones, that is, V (T s ) \ S(T s ), are denoted by O(T s ),

• for every

v ∈ B t , ϕ s (v) is a subset of V (T s ) such that T s [ϕ s (v)] is connected and such that ϕ(v) = ϕ s (v) ∩ O(T s )
, where we licitly consider the vertices in

ϕ(v) as a subset of O(T s ). Furthermore, if u, v ∈ B t with c(u) = c(v), then ϕ s (u) ∩ ϕ s (v) = ∅,
• ψ s : E(T s ) → 2 [k] such that for every s ∈ S(T s ), if x and y are the neighbors of s in T s , then ψ s ({x, s}) = ψ s ({s, y}) = ψ({x, y}), and

• ρ s : B t → V (T s ) such that for every v ∈ B t , ρ s (v) = ρ(v).
We say that T s is a shadow of T. Note that T may have more than one shadow satisfying Denition 2. Denition 3. Let T = (T, ϕ, ψ, ρ) be a (Z, t)-supertree. The restriction of T to a subset of vertices Y ⊆ V t is dened as the (Y, t)-supertree T| Y = ( T , φ, ψ, ρ), where

• T = T | Z , where Z = {ρ(v) | v ∈ Y }, • for every v ∈ Y , φ(v) = ϕ(v) ∩ V (T | Y ),
• for every e ∈ E( T ), ψ(e) = f ∈E(Pe) ψ(f ), where P e 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 B t ⊆ Z, we dene a shadow restriction of T to B t as a shadow of T| Bt , and we denote it by T| s Bt .

Denition 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).
Every node t of (T, B) is associated with a set R t of pairs (T, γ), called colored shadow B t -supertrees, where T = (T, ϕ, ψ, ρ) is a shadow B t -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 B t -supertree (T = (T, ϕ, ψ, ρ), γ) belongs to R t if and only if there exists a valid V t -supertree T ps = (T ps , ϕ ps , ψ ps , ρ ps ) such that

(1) T T ps | s Bt ,

(2) for every a ∈ V (T ), a color i ∈ γ(a) if and only if there exists u ∈ V t 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 ∈ V t with c(u) = i and x, y ∈ ϕ ps (u) such that the unique path between x and y in T ps uses at least one vertex of ϕ ps (u).

Intuitively, condition [START_REF] Bininda-Emonds | Phylogenetic supertrees: combining information to reveal the tree of life[END_REF] 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 V t \ B t . On the other hand, condition (3) of The congurations 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 ).

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 [START_REF] Bininda-Emonds | Phylogenetic supertrees: combining information to reveal the tree of life[END_REF] and (3), we say that γ is consistent with T ps .

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 ∈ R tr . Indeed, for t = t r we have that B tr = ∅ and V tr = V D . In that case, the only condition imposed by Invariant 1 is the existence of a valid V Dsupertree. Then, by Denition 1, the existence of such a supertree is equivalent to the existence of a compatible supertree T of T in which the vertex-models and edge-models are given by the functions ϕ and ψ, respectively. Finally, note that the rst condition of Denition 1, namely that | T | ≤ |B tr | + |V tr | = |V D |, 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 R t for every node t ∈ T. For that, we will assume inductively that, for every descendant t of t, we have at hand the set R t that has been correctly built. We distinguish several cases depending on the type of node t:

1. t is a leaf with B t = {v}: R t = {((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 R t , we add to R t the elements of the form (T = (T, ϕ, ψ, ρ), γ) that can be built according to one of the following four cases. For all of them, we dene the vertexrepresentative function such that ρ(v) = a for some vertex a ∈ V (T ), and for every u ∈ B t , ρ(u) = ρ (u). The dierent cases depend on this vertex a.

(i) ρ(v) = a such that a ∈ V (T ) and c(v) ∈ γ (a). See Figure 1(i) for an example. We dene T = T . Let us dene ϕ, ψ, and γ.

• Denition of the vertex-model function: T [ϕ(v)] is connected, contains a, and for every z ∈ ϕ(v), c(v) ∈ γ (z). For every u ∈ B t , ϕ(u) = ϕ (u).

• Denition of the edge-model function: For every e ∈ E(T ), ψ(e) = ψ (e).

• Denition 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) ∈ ψ ({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 dene ϕ, ψ, and γ.

• Denition of the vertex-model function:

T [ϕ(v)] is connected, con- tains a, and for each z ∈ ϕ(v), c(v) ∈ γ (z). For each u ∈ B t , T [ϕ(u)] is connected, ϕ (u) ⊆ ϕ(u) ⊆ ϕ (u) ∪ {a} ∪ S(T ), and if u is unlabeled, then ϕ(u) = ϕ (u). For each u, u ∈ B t with c(u) = c(u ), ϕ(u) ∩ ϕ(u ) = ∅.
• Denition 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}).

• Denition of the coloring function: (iii) ρ(v) = a with a / ∈ V (T ) and a is connected to a vertex x ∈ V (T ).

For each z ∈ O(T ) \ {a}, γ(z) = γ (z) ∪ {c(v) | z ∈ ϕ(v)}. γ(a) = {i | ∃u ∈ B t : c(u) = i
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 dene ϕ, ψ, and γ.

• Denition of the vertex-model function:

T [ϕ(v)] is connected, con- tains a, and for each z ∈ ϕ(v), c(v) ∈ γ (z). For each u ∈ B t , T [ϕ(u)] is connected, ϕ (u) ⊆ ϕ(u) ⊆ ϕ (u) ∪ {a} ∪ S(T ), and if u is unlabeled, then ϕ(u) = ϕ (u). For each u, u ∈ B t with c(u) = c(u ), ϕ(u) ∩ ϕ(u ) = ∅.
• Denition of the edge-model function: For each e ∈ E(T )\{{a, s}, {s, x}}, ψ(e) = ψ (e), and ψ({a, s}) = ψ({s, x}) = ∅.

• Denition 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 ∈ B t : 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 s 1 , s 2 ∈ S(T ), and ve edges {x, s 1 }, {s 1 , b}, {b, y}, {a, s 2 }, and {s 2 , b}. Let us dene ϕ, ψ, and γ.

• Denition of the vertex-model function:

T [ϕ(v)] is connected, con- tains a and, for every z ∈ ϕ(v), c(v) ∈ γ (z). For each u ∈ B t , T [ϕ(u)] is connected, ϕ (u) ⊆ ϕ(u) ⊆ ϕ (u)∪{a, b}∪S(T ), and if u is unlabeled, then ϕ(u) = ϕ (u). For each u, u ∈ B t with c(u) = c(u ), ϕ(u) ∩ ϕ(u ) = ∅.
• Denition of the edge-model function: For each edge e ∈ E(T ) \ {{a, s 2 }, {s 2 , b}, {x, s 1 }, {s 1 , b}, {b, y}}, ψ(e) = ψ (e). ψ({x, s 1 }) = ψ({s 1 , b}) = ψ({b, y}) = ψ ({x, y}), and ψ({a, s 2 }) = ψ({s 2 , b}) = ∅.

• Denition of the coloring function: For every z ∈ O(T ) \ {a, b},

γ(z) = γ (z) ∪ {c(v) | z ∈ ϕ(v)}. For every z ∈ {a, s 2 }, γ(z) = {i | ∃u ∈ B t : c(u) = i and z ∈ ϕ(u)}. For every z ∈ {b, s 1 }, γ(z) = {i | ∃u ∈ B t : c(u) = i and z ∈ ϕ(u)} ∪ ψ ({x, y}). For every z ∈ S(T ), γ(z) = γ (z) ∪ {i | ∃u ∈ B t : c(u) = i and z ∈ ϕ(u)}.
ϕ(v) = {a} and γ(v) = {i ∈ [k] | v ∈ L(T i ), T i ∈ 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 R t such that there exist a ∈ ϕ (v) and b ∈ ϕ (w) such that {a, b} ∈ E(T ) and i ∈ ψ ({a, b}). We construct (T = (T, ϕ, ψ, ρ), γ) as an element of R t as follows:

T = T . For every v ∈ B t , ϕ(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 R t . We construct (T = (T, ϕ, ψ, ρ), γ) as an element of R t as follows:

T = T | z B t
. 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 ∈ B t : a ∈ ϕ (u))}.

6. t is a join node: Let (T = (T, ϕ, ψ , ρ), γ ) be an element of R t and let (T = (T, ϕ, ψ , ρ), γ ) be an element of R t 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 R t as follows: For every e ∈ E(T ), ψ(e) = ψ (e) ∪ ψ (e), and for every z ∈ V (T ), γ(z) = γ (z) ∪ γ (z).

Further research

In this paper we give the rst 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 [START_REF] Delsuc | Phylogenomics and the reconstruction of the tree of life[END_REF]. 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 function 2 O(k 2 ) 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 [START_REF] Lokshtanov | Lower bounds based on the exponential time hypothesis[END_REF].

A Correctness of the algorithm for the compatibility version

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 R t (that is, that they satisfy Invariant 1) and, on the other hand, that all the elements of the set R t 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 R t is the following. We distinguish again the cases of the algorithm. For each of them,

the assumption that R t has been correctly built for every descendant t of t guarantees the existence, for every element (T , γ ) of R t , of the corresponding certicate T ps that implies by Invariant 1 that (T , γ ) ∈ R t . We will then use T ps to prove, for each of the elements (T, γ) constructed by the algorithm, that there exists a certicate T ps implying that (T, γ) ∈ R t . We would like to stress that, in order to prove that (T, γ) ∈ R t , we only need to worry about the existence of such a certicate T ps , 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 certicates T ps of R t to get the certicates T ps of R t , within the same running time of the algorithm.

We now proceed to distinguish the dierent cases of the dynamic programming algorithm presented in Section 3:

1. t is a leaf with B t = {v}: T ps 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 R t with the corresponding certicate T ps , we distinguish the dierent cases of the algorithm that create elements of the form (T, γ), and we dene for each case a certicate T ps of T, which implies that (T, γ) ∈ R t .

(i) ρ(v) = a such that a ∈ V (T ) and c(v) ∈ γ (a). Then T ps = T ps . Let us dene ρ ps , ϕ ps , and ψ ps .

• Denition of the vertex-representative function: * ρ ps (v) = ρ(v) = a and * for every u ∈ V t , ρ ps (u) = ρ ps (u).

• Denition of the vertex-model function: * T ps [ϕ ps (v)] is connected and contains a, ϕ(v) ∩ O(T ) = ϕ ps (v) ∩ O(T ), * for every u ∈ B t , ϕ ps (u) = ϕ ps (u), and * for every u, u ∈ V t with c(u) = c(u ), ϕ ps (u) ∩ ϕ ps (u ) = ∅.

• Denition 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) ∈ ψ ({x, y}). T ps is obtained from T ps by removing an edge {x ps , y ps } on the path between x and y, and adding a vertex a and two edges {x ps , a} and {a, y ps }. Let us dene ρ ps , ϕ ps , and ψ ps .

• Denition of the vertex-representative function: * for every u ∈ V t , T ps [ϕ 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 ∈ B t , ϕ(u) ∩ O(T ) = ϕ ps (u) ∩ O(T ), * for every u, u ∈ V t with c(u) = c(u ), ϕ ps (u) ∩ ϕ ps (u ) = ∅, and * for every {u, u } ∈ E t , there exist w ∈ ϕ ps (u) and w ∈ ϕ ps (u ) such that {w, w } ∈ E(T ps ).

• Denition of the edge-model function: * for every e ∈ E(T ) \ {{a, b}, {x ps , b}, {b, y ps }}, ψ(e) = ψ (e), * ψ ps ({x ps , b}) = ψ ps ({b, y ps }) = ψ ps ({x ps , y ps }), and * ψ ps ({a, b}) = ∅.

• ϕ ps (v) = {a} and • γ ps (v) = {i ∈ [k] | v ∈ L(T i ), T i ∈ T }.
In the next two cases, let (T , γ ) be the element of R t from which the algorithm has started, let T ps be a certicate of (T , γ ), and let (T, γ) be the element created by the algorithm. In both cases, we construct a certicate T ps of (T, γ ) showing that (T, γ) ∈ R t .

4. t in an introduce-edge node for an edge {v, w} with c({v, w}) = i: We construct T ps = (T ps , ϕ ps , ψ ps , ρ ps ) as follows:

• T ps = T ps ,

• for every v ∈ V t , ϕ ps (v) = ϕ ps (v),

• for every e ∈ E(T ) \ {{a, b}}, ψ ps (e) = ψ ps (e), and • ψ ps ({a, b}) = ψ ps ({a, b}) ∪ {i}.

5. t is a forget-vertex node for a vertex v: In this case, we just dene T ps = T ps .

6. t is a join node: Let (T , γ ) be the element of R t and let (T , γ ) be the element of R t from which the algorithm has started, and let T ps = (T ps , ϕ ps , ψ ps , ρ ps ) and T ps = (T ps , ϕ ps , ψ ps , ρ ps ) be their certicates, respectively. We dene T ps = (T ps , ϕ ps , ψ ps , ρ ps ), that is, a certicate of (T, γ)

showing that (T, γ) ∈ R t , just by setting, for every e ∈ E(T ), ψ ps (e) = ψ ps (e) ∪ ψ ps (e). Note that T ps , ϕ ps , and ρ ps are those given by (T , γ ) (or by (T , γ )).

Finally, let us argue that all the elements of the set R t are indeed constructed by the algorithm. Let (T, γ) be an element of R t , 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 denition of the set R t , there exists a valid V t -supertree T ps such that T = T ps | s Bt and such that γ is consistent with T ps . Let T ps = T ps | V t . It can be easily checked that T ps is a valid V t -supertree. Let T = T ps | s B t and let γ be the coloring function consistent with T ps . Then, as Invariant 1 is satised, (T , γ ) is an element of R t . Note that T = T| B t . As the sets B t and B t dier by just one vertex, the elements T and T are quite close to each other. Indeed, the way they dier 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 dierent 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 R t , as we wanted to show.

B Running time analysis of the algorithm for the compatibility version

Let us now discuss the running time of the dynamic programming algorithm described in Section 3. 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 R t as follows. Each element in R t is of the form (T = (T, ϕ, ψ, ρ), γ). Note that T has at most 3w nodes, and that there are at most (3w) 3w-2 = 2 O(k log k) distinct trees on 3w vertices [START_REF] Cayley | A theorem on trees[END_REF]. There are at most 2

|V (T )|•|Bt| ≤ 2 3w•w possible functions ϕ, 2 |E(T )|•k ≤ 2 3w•k possible functions ψ, |V (T )| |Bt| ≤ (3w) w possible functions ρ, and 2 |V (T )|•k ≤ 2 3w•k possible functions γ. Thus, it holds that |R t | = 2 O(k 2 )
for every node t of (T, B).

Concerning the complexity of computing R t , 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 R t can be clearly computed in time polynomial in |R t |, where t is the child of t. Finally, in Case 6, that is, when t is a join node, the set R t can also be clearly computed in time polynomial in |R t | and |R t |, where t and t are the two children of t. Finally, as we can assume that |V (T)| = O(n) [START_REF] Kloks | Computations and Approximations[END_REF], the running time claimed in Theorem 1 follows.

C 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.

The algorithm follows closely the one described in Section 3 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 redene the notions of vertex-model and edgemodel 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 rst proceed to partially redene 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 R t store again elements of the form (T, γ) satisfying the same invariant as in Section 3, namely Invariant 1, the dierence is that we update some denitions of the data structure. Namely, the vertex-model function in the denition of (Z, t)-supertree, cf. Denition 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) = ϕ(v),

We also modify slightly the denition of valid supertrees and say that a (Z, t)supertree (T, ϕ, ψ, ρ) is valid if

• for every {u, v} ∈ E t such that u, v ∈ Z, every edge e on the path between ϕ(u) and ϕ(v) in T satises c({u, v}) ∈ ψ(e) and • if i ∈ ψ(e) for some i ∈ [k], then there exists a unique pair {u, v} ∈ E t 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 satises that, for every vertex v ∈ Z, ϕ(v) = ρ(v), and therefore the vertexrepresentative function ρ becomes superuous. 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 simplication 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 Section 3 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:

4. t in an introduce-edge node for an edge {v, w} with c({v, w}) = i: Let (T = (T , ϕ , ψ , ρ ), γ ) be an element of R t such that for each e ∈ P v,w , i ∈ ψ (e), where P v,w = {e ∈ E(T ) | e lies on the path between ϕ(v) and ϕ(w)}. We construct (T = (T, ϕ, ψ, ρ), γ) as an element of R t as follows:

• T = T ,

• for every v ∈ B t , ϕ(v) = ϕ (v),

• for every e ∈ E(T ) \ P v,w , ψ(e) = ψ (e),

• for every e ∈ P v,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 Appendix A. Finally, note that the analysis of the running time carried out in Appendix B 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 Section 3.

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 by the overall running time of the algorithm, namely 2 O(k 2 ) • n.

Fig. 1 .

 1 Fig.1. The four possible cases (i-iv) in the dynamic programming algorithm.

  and a ∈ ϕ(u)} ∪ ψ ({x, y}). For each z ∈ S(T ), γ(z) = γ (z) ∪ {i | ∃u ∈ B t : c(u) = i and z ∈ ϕ(u)}. Finally, γ(s) = {i | ∃u ∈ B t : c(u) = i and s ∈ ϕ(u)} ∪ ψ ({x, y}).

  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: