Counting Trees in a Phylogenetic Network Is \#P-Complete
Simone Linz, Katherine St. John, Charles Semple · SIAM Journal on Computing · 2013
Answering a problem posed by Nakhleh, we prove that counting the number of phylogenetic trees inferred by a (binary) phylogenetic network is \#P-complete. An immediate consequence of this result is that counting the number of phylogenetic trees commonly inferred by two (binary) phylogenetic networks is also \#P-complete.