Embedding Phylogenetic Trees in Networks of Low Treewidth

Leo Van Iersel, Mark Jones, Mathias Weller

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)
42 Downloads (Pure)


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.

Original languageEnglish
Title of host publication30th Annual European Symposium on Algorithms, ESA 2022
EditorsShiri Chechik, Gonzalo Navarro, Eva Rotenberg, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages14
ISBN (Electronic)9783959772471
Publication statusPublished - 2022
Event30th Annual European Symposium on Algorithms, ESA 2022 - Berlin/Potsdam, Germany
Duration: 5 Sept 20229 Sept 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference30th Annual European Symposium on Algorithms, ESA 2022


  • display graph
  • embedding
  • fixed-parameter tractability
  • phylogenetic network
  • phylogenetic tree
  • tree containment
  • treewidth


Dive into the research topics of 'Embedding Phylogenetic Trees in Networks of Low Treewidth'. Together they form a unique fingerprint.

Cite this