Counting Unlabelled Subtrees of a Tree is #P-complete

DOI10.1112/S1461157000000243MaRDI QIDQ4504966zbMATH OpenFDO

Authors Leslie Ann Goldberg, Mark Jerrum

Publication date 25 September 2000

Published in LMS Journal of Computation and Mathematics (Search for Journal in Brave)

Full work available at URL http://www.lms.ac.uk/jcm/3/lms1999-029/

zbMATH Keywords

counting unlabelled subtrees

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Counting trees in a graph is \(\# \text{P}\)-complete
• Counting unlabeled \(k\)-trees
• A REFINED ENUMERATION OF p-ARY LABELED TREES
• Counting consistent phylogenetic trees is \#P-complete
• On the number of subtrees for almost all graphs
• The (p,q)-total labeling problem for trees
• The (p,q)-total Labeling Problem for Trees
• Counting labelled trees with given indegree sequence
• The challenges of unbounded treewidth in parameterised subgraph counting problems

Cites work

• Complexity Results for Bandwidth Minimization
• Efficient Planarity Testing
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• PP is as Hard as the Polynomial-Time Hierarchy
• The Complexity of Enumeration and Reliability Problems
• The complexity of harmonious colouring for trees

Cited in

(9)

• The complexity of counting homeomorphs
• Counting trees in a graph is \(\# \text{P}\)-complete
• Counting consistent phylogenetic trees is \#P-complete
• Parameterized counting of partially injective homomorphisms
• Counting unlabeled \(k\)-trees
• Counting restricted homomorphisms via Möbius inversion over matroid lattices
• Algorithms for four variants of the exact satisfiability problem
• Exact counting of subtrees with diameter no more than d in trees: a generating function approach
• Counting the number of group orbits by marrying the Burnside process with importance sampling

This page was built for publication: Counting Unlabelled Subtrees of a Tree is #P-complete

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