The agreement problem for unrooted phylogenetic trees is FPT

Abstract

A collection T of k unrooted phylogenetic trees on different leaf sets is said to be strictly compatible or in agreement if there exists a tree T such that each tree in T can be obtained from T by deleting leaves and suppressing degree-2 vertices. The problem of determining if a set of unrooted trees is in agreement has been proved NP-hard in 1992. Here, we show that an f(k) ·n algorithm exists, for some computable function f of k, proving that strict compatibility of unrooted phylogenetic trees is fixed-parameter tractable with respect to the number k of trees. Designing a practical FPT algorithm remains an open problem.