An Exact Algorithm for Counting the Number of Independent Sets of a Graph
Abstract
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.
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Advanced Combinatorial Mathematics
Publication details
- Journal / source
- Mathematics
- Volume
- 14
- Issue
- 2
- Pages
- 275–275
- Publication date
- 12 January 2026
- Language
- EN