Counting k‐component forests of a graph
Wendy J. Myrvold · Networks · 1992
Abstract We describe an algorithm for computing the number of k‐component spanning forests of a graph G that runs in polynomial time for fixed k. The algorithm is based on earlier work by Liu and Chow. Our contributions are a simpler graph‐theoretic proof of their formula and a demonstration of how Jacobi's Theorem can be applied to improve the asymptotic time complexity. By matroid duality, the number of connected spanning subgraphs of cyclomatic number c of a planar graph equals the number of c + 1‐component forests in the dual. Thus, one application of this research is an algorithm for counting connected spanning unicyclic subgraphs of a planar graph. We show this can be done in time O(M(n)), where M(n) is the time complexity of multiplying together two n by n matrices.