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−N[x]) 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.