2026-07-23T21:50:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1357 2024-03-06T10:33:00Z ddc:004 open_access

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees Hoang, Viet Tung Sung, Wing-Kin Maximum agreement supertree maximum compatible supertree Consider a set of labels $L$ and a set of trees ${mathcal T} = { {mathcal T}^{(1), {mathcal T}^{(2), ldots, {mathcal T}^{(k) $ where each tree ${mathcal T}^{(i)$ is distinctly leaf-labeled by some subset of $L$. One fundamental problem is to find the biggest tree (denoted as supertree) to represent $mathcal T}$ which minimizes the disagreements with the trees in ${mathcal T}$ under certain criteria. This problem finds applications in phylogenetics, database, and data mining. In this paper, we focus on two particular supertree problems, namely, the maximum agreement supertree problem (MASP) and the maximum compatible supertree problem (MCSP). These two problems are known to be NP-hard for $k geq 3$. This paper gives the first polynomial time algorithms for both MASP and MCSP when both $k$ and the maximum degree $D$ of the trees are constant. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Viet Tung Hoang and Wing-Kin Sung 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1357 urn:nbn:de:0030-drops-13579 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1357 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode