On Low Treewidth Graphs and Supertrees

Authors

  • Alexander Grigoriev
  • Steven Kelk
  • Nela Lekić

DOI:

https://doi.org/10.7155/jgaa.00361

Keywords:

phylogenetic tree , unrooted compatibility , supertree , display graph , treewidth

Abstract

Compatibility of unrooted phylogenetic trees is a well studied problem in phylogenetics. It asks to determine whether for a set of k input trees T1,...,Tk there exists a larger tree (called a supertree) that contains the topologies of all k input trees. When any such supertree exists we call the instance compatible and otherwise incompatible. It is known that the problem is NP-hard and FPT, although a constructive FPT algorithm is not known. It has been shown that whenever the treewidth of an auxiliary structure known as the display graph is strictly larger than the number of input trees, the instance is incompatible. Here we show that whenever the treewidth of the display graph is at most 2, the instance is compatible. Furthermore, we give a polynomial-time algorithm to construct a supertree in this case. Finally, we demonstrate both compatible and incompatible instances that have display graphs with treewidth 3, highlighting that the treewidth of the display graph is (on its own) not sufficient to determine compatibility.

Downloads

Download data is not yet available.

Downloads

Published

2015-01-01

How to Cite

Grigoriev, A., Kelk, S., & Lekić, N. (2015). On Low Treewidth Graphs and Supertrees. Journal of Graph Algorithms and Applications, 19(1), 325–343. https://doi.org/10.7155/jgaa.00361

Issue

Section

Articles

Categories