Computing the numbers of independent sets and matchings of all sizes for graphs with bounded treewidth

摘要

In the theory and applications of graphs, it is a basic problem to compute the numbers of independent sets and matchings of given sizes. Since the problem of computing the total number of independent sets and that of matchings of graphs is #P-complete, it is unlikely to give efficient algorithms to find the numbers of independent sets and matchings of given sizes. In this paper, for graphs with order n and treewidth at most p, we present two dynamic algorithms to compute the numbers of independent sets of all sizes with runtime O(2p · pn3) and the numbers of matchings of all sizes with runtime O(22p · pn3), respectively. By the algorithms presented in this paper, for graphs with small treewidths, the numbers of independent sets and matchings of all possible sizes can be computed efficiently.