@inproceedings{04bee27f3d02410f969bb855d60754ca,
title = "Embedding Phylogenetic Trees in Networks of Low Treewidth",
abstract = "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 2O(t2) |N| time and space.",
keywords = "display graph, embedding, fixed-parameter tractability, phylogenetic network, phylogenetic tree, tree containment, treewidth",
author = "{Van Iersel}, Leo and Mark Jones and Mathias Weller",
year = "2022",
doi = "10.4230/LIPIcs.ESA.2022.69",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "69:1--69:14",
editor = "Shiri Chechik and Gonzalo Navarro and Eva Rotenberg and Grzegorz Herman",
booktitle = "30th Annual European Symposium on Algorithms, ESA 2022",
note = "30th Annual European Symposium on Algorithms, ESA 2022 ; Conference date: 05-09-2022 Through 09-09-2022",
}