Geodesic
On Low Treewidth Graphs and Supertrees
Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 325-343.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00361
Keywords: phylogenetic tree, unrooted compatibility, supertree, display graph, treewidth 
@article{JGAA_2015_19_1_a15,
     author = {Alexander Grigoriev and Steven Kelk and Nela Leki\'c},
     title = {On {Low} {Treewidth} {Graphs} and {Supertrees}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {325--343},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2015},
     doi = {10.7155/jgaa.00361},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00361/}
}
TY  - JOUR
AU  - Alexander Grigoriev
AU  - Steven Kelk
AU  - Nela Lekić
TI  - On Low Treewidth Graphs and Supertrees
JO  - Journal of Graph Algorithms and Applications
PY  - 2015
SP  - 325
EP  - 343
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00361/
DO  - 10.7155/jgaa.00361
LA  - en
ID  - JGAA_2015_19_1_a15
ER  - 
%0 Journal Article
%A Alexander Grigoriev
%A Steven Kelk
%A Nela Lekić
%T On Low Treewidth Graphs and Supertrees
%J Journal of Graph Algorithms and Applications
%D 2015
%P 325-343
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00361/
%R 10.7155/jgaa.00361
%G en
%F JGAA_2015_19_1_a15
Alexander Grigoriev; Steven Kelk; Nela Lekić. On Low Treewidth Graphs and Supertrees. Journal of Graph Algorithms and Applications, Tome 19 (2015) no. 1, pp. 325-343. doi : 10.7155/jgaa.00361. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00361/

Cité par Sources :