2026-08-17T03:42:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17007 2024-03-06T10:58:57Z ddc:004 open_access

Embedding Phylogenetic Trees in Networks of Low Treewidth van Iersel, Leo Jones, Mark Weller, Mathias fixed-parameter tractability treewidth phylogenetic tree phylogenetic network display graph tree containment embedding Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called Tree Containment, arises when validating networks constructed by phylogenetic inference methods. We present the first algorithm for (rooted) Tree Containment using the treewidth t of the input network N as parameter, showing that the problem can be solved in 2^O(t²)⋅|N| time and space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Leo van Iersel and Mark Jones and Mathias Weller 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.69 urn:nbn:de:0030-drops-170070 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.69 eng https://creativecommons.org/licenses/by/4.0/legalcode