zbMATH — the first resource for mathematics

Compatibility of unrooted phylogenetic trees is FPT. (English) Zbl 1086.68097
Summary: A collection of \(T_{1},T_{2},\cdots,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 \(\Omega(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.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0207.01701
[2] Aho, A.V.; Sagiv, T.G.; Szymanski, T.G.; Ullman, J.D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM J. comput., 10, 3, 405-421, (1981) · Zbl 0462.68086
[3] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. algorithms, 12, 2, 308-340, (1991) · Zbl 0734.68073
[4] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernet., 11, 1-21, (1993) · Zbl 0804.68101
[5] Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 6, 1305-1317, (1996) · Zbl 0864.68074
[6] Bryant, D.; Steel, M., Extension operations on sets of leaf-labelled trees, Adv. appl. math., 16, 425-453, (1995) · Zbl 0863.92012
[7] Courcelle, B., The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Inform. comput., 85, 1, 12-75, (1990) · Zbl 0722.03008
[8] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[9] Gordon, A.D., Consensus supertrees: the synthesis of rooted trees containing overlapping sets of labeled leaves, J. classification, 3, 335-348, (1986) · Zbl 0623.62051
[10] Semple, C.; Steel, M., Phylogenetics, (2003), Oxford University Press Oxford · Zbl 1043.92026
[11] Steel, M., The complexity of reconstructing trees from qualitative characters and subtrees, J. classification, 9, 91-116, (1992) · Zbl 0766.92002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.