Counting trees in a graph is \# P-complete

DOI10.1016/0020-0190(94)00085-9MaRDI QIDQ1332763zbMATH OpenOpenAlexWikidataFDO

Authors Mark Jerrum

Publication date 13 October 1994

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(94)00085-9

zbMATH Keywords

computational complexitycombinatorial enumeration\#P-completeness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30)

Recommendations

• Counting Unlabelled Subtrees of a Tree is #P-complete
• Counting consistent phylogenetic trees is \#P-complete
• The complexity of counting homeomorphs
• Counting trees in a phylogenetic network is \#P-complete
• The complexity of counting in sparse, regular, and planar graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The Complexity of Enumeration and Reliability Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(15)

• A note on a counting problem arising in percolation theory
• scientific article; zbMATH DE number 1834679 (Why is no real title available?)
• Counting feasible solutions of the traveling salesman problem with pickups and deliveries is \#\(P\)-complete
• Approximately counting paths and cycles in a graph
• Counting Unlabelled Subtrees of a Tree is #P-complete
• Counting consistent phylogenetic trees is \#P-complete
• Counting trees in a phylogenetic network is \#P-complete
• Some problems on approximate counting in graphs and matroids
• Parameterized counting of trees, forests and matroid bases
• Parameterized counting of partially injective homomorphisms
• Computational complexity of counting coincidences
• Space-efficient counting in graphs on surfaces
• Models of random subtrees of a graph
• Counting polygon triangulations is hard
• The complexity of counting homeomorphs

This page was built for publication: Counting trees in a graph is \(\# \text{P}\)-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1332763)