Counting consistent phylogenetic trees is \#P-complete
type: Item
instance of: scholarly article
title: Counting consistent phylogenetic trees is \#P-complete
zbMATH Open document ID: 1053.05029
author: Magnus Bordewich
author: Charles Semple
author: John Talbot
published in: Advances in Applied Mathematics
publication date: 2004-10-12T00:00:00Z
review text: The paper studies the complexity of counting rooted phylogenetic (super)trees consistent to a set of (possibly overlapping) rooted phylogenetic trees, and shows that it (similarly to two other related problems) is \#P-complete. The proof works through reducing the problem \(\#\)-\texttt{MON-2-SAT} to the problem at hand.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92D15
zbMATH DE Number: 2107235
zbMATH Keywords: \#P complete counting
zbMATH Keywords: NP-complete decision problem
zbMATH Keywords: \(\#\)-\texttt{MON-2-SAT} problem
reviewed by: Péter L. Erdős
MaRDI profile type: Publication
full work available at URL: j.aam.2003.08.006
OpenAlex ID: W2145844324
cites work: Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
cites work: Phylogenetic supertrees. Combining information to reveal the tree of life
cites work: Counting linear extensions
cites work: An efficient algorithm for supertrees
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Reconstruction of rooted trees from subtrees
cites work: Q4792088
cites work: The complexity of reconstructing trees from qualitative characters and subtrees
cites work: The Complexity of Enumeration and Reliability Problems
cites work: Q3140234
DOI: 10.1016/J.AAM.2003.08.006
Recommended article: Counting trees in a phylogenetic network is \#P-complete
Recommended article: Counting trees in a graph is \(\# \text{P}\)-complete
Recommended article: Enumeration of binary trees compatible with a perfect phylogeny
Recommended article: On the combinatorics of rooted binary phylogenetic trees
Recommended article: Q3347902
Recommended article: Counting Unlabelled Subtrees of a Tree is #P-complete
Recommended article: Neighborhoods of Phylogenetic Trees: Exact and Asymptotic Counts
Recommended article: Finite phylogenetic complexity and combinatorics of tables
Recommended article: Counting General Phylogenetic networks
Recommended article: On the number of vertices of each rank in phylogenetic trees and their generalizations
description: scientific article; zbMATH DE number 2107235