Given a graph \(G=(V, E)\), an independent set \(I\) of \(G\) is a subset of \(V\), such that every two vertices in \(I\) are not adjacent. We give an algorithm to count the number of independent sets of a given graph on \(n\) vertices. The main idea of the algorithm is divide and conquer.
Counting independent sets of \(G\): CIS(G)
- If \(G\) contains multiple connected components, count the independent sets of each component and multiply the numbers.
- If \(G\) contains only one vertex, return 1.
- Otherwise, arbitrarily select a vertex \(v\). Remove \(v\) and count the number of independent sets of the remaining graph. Remove \(v\) and its neighbors and count the number of independent sets of the remaining graph. Return the sum of two.
To see the O(1.619^n) running time, note that in step 3, removing \(v\) decreases the number of vertices by one, while removing \(v\) and its neighbors decreases the number of vertices by at least two. The recurrent is identical to Fibonacci sequence.