Fast exponential-time algorithms for the forest counting in graph classes

摘要

We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O* (1.8494^m) time for 3-regular graphs, and O* (1.9706^m) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.