Counting Unlabelled Subtrees of a Tree is #P-complete

Leslie Ann Goldberg, Mark Jerrum

Type: Article

Publication Date: 2000-01-01

Citations: 14

DOI: https://doi.org/10.1112/s1461157000000243

Abstract

Abstract The problem of counting unlabelled subtrees of a tree (that is, sub-trees that are distinct up to isomorphism) is #P-complete, and hence equivalent in computational difficulty to evaluating the permanent of a 0,1-matrix.

Locations

LMS Journal of Computation and Mathematics - View - PDF
CiteSeer X (The Pennsylvania State University) - View - PDF
Warwick Research Archive Portal (University of Warwick) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Counting trees in a graph is #P-complete	1994	Mark Jerrum
+ PDF Chat	Enumeration of Unordered Forests	2021	Florian Ingels Romain Azaïs
+ PDF Chat	Enumeration of Unordered Forests	2020	Florian Ingels Romain Azaïs
+ PDF Chat	Enumeration of Unordered Forests	2021	Florian Ingels Romain Azaïs
+ PDF Chat	Enumeration of irredundant forests	2022	Florian Ingels Romain Azaïs
+	Enumeration of subtrees of trees	2006	YanWeigen YehYeong-Nan
+	Enumeration of Trees	1963	O. Wing
+	Unranking of Labelled Combinatorial Structures	2000	Conrado Martı́nez Xavier Molinero
+	Combinatorial Aspects of Leaf-Labelled Trees	2008	Peter Humphries
+	The $μ$-permanent, a new graph labeling, and a known integer sequence	2016	Milica Anðelić Carlos M. da Fonseca António Pereira
+	Combinatorial polynomials and enumeration of trees	2022	A.A. Balagura О. В. Кузьмін
+	Counting Labelled Trees with Given Indegree Sequence	2007	Rosena R. X. Du Jingbin Yin
+	Trees	2012	R. Balakrishnan K. Ranganathan
+ PDF Chat	The Complexity of L(p, q)-Edge-Labelling	2022	Gaétan Berthe Barnaby Martin Daniël Paulusma Siani Smith
+	The Complexity of L(p, q)-Edge-Labelling	2023	Gaétan Berthe Barnaby Martin Daniël Paulusma Siani Smith
+	Permutation representation of k-ary trees	1985	Prakash Ramanan C.L. Liu
+ PDF Chat	Finding and Counting Vertex-Colored Subtrees	2010	Sylvain Guillemot Florian Sikora
+ PDF Chat	Finding and Counting Vertex-Colored Subtrees	2011	Sylvain Guillemot Florian Sikora
+ PDF Chat	Finding and counting vertex-colored subtrees	2010	Sylvain Guillemot Florian Sikora
+	Disjoint permutation matrices in complements of trees	1979	Richard A. Brualdit

Works That Cite This (6)

Action	Title	Year	Authors
+	A Complete Bibliography of the LMS Journal of Computation and Mathematics	2015	Nelson H. F. Beebe
+ PDF Chat	Dichotomy Theorems for Homomorphism Polynomials of Graph Classes	2015	Christian Engels
+ PDF Chat	Parameterized Counting of Partially Injective Homomorphisms	2021	Marc Roth
+ PDF Chat	Optimal Value of Information in Graphical Models	2009	Andreas Krause Carlos Guestrin
+	Inference on the History of a Randomly Growing Tree	2020	Harry Crane Min Xu
+	Counting rooted forests in a network	2013	Oliver Knill

Works Cited by This (4)

Action	Title	Year	Authors
+	Complexity: Knots, Colourings and Counting	1993	Dominic Welsh
+	The Complexity of Enumeration and Reliability Problems	1979	Leslie G. Valiant
+	Graphical Enumeration	1973
+	Complexity: Knots, Colourings and Countings	1993	Dominic Welsh