An Exact Algorithm for Counting the Number of Independent Sets of a Graph

For a graph G of a degree greater than or equal to 3, counting the number of independent sets (denoted as i (G) ) is a classical #P-complete problem. Here, we establish a new worst-case upper bound time complexity for computing i (G) for any non-constraint undirected graph. Our proposal applies the vertex division rule i (G) =i (G−x) +i (G−Nx) over a vertex x which satisfies some conditions, and considers cactus and outerplanar graphs as basic subgraphs. Our algorithm establishes a leading worst-case upper bound of O* (1. 2321n), where n is the number of vertices in the graph and O* omits polynomial terms in n.