# Counting independent sets in O(1.619^n) time

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)

1. If $$G$$ contains multiple connected components, count the independent sets of each component and multiply the numbers.
2. If $$G$$ contains only one vertex, return 1.
3. 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.