Abstract
A collection of
T
1
,
T
2
,
…
,
T
k
of unrooted, leaf labelled (phylogenetic) trees, all with different leaf sets, is said to be
compatible if there exists a tree
T
such that each tree
T
i
can be obtained from
T
by deleting leaves and contracting edges. Determining compatibility is NP-hard, and the fastest algorithm to date has worst case complexity of around
Ω
(
n
k
)
time,
n
being the number of leaves. Here, we present an
O
(
nf
(
k
)
)
algorithm, proving that compatibility of unrooted phylogenetic trees is
fixed parameter tractable (FPT) with respect to the number
k
of trees.