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.

发表评论

电子邮件地址不会被公开。 必填项已用*标注