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.

Counting independent sets in O(1.619^n) time》上有1条评论

  1. Roundgod

    Actually, after sorting the vertices by decreasing order of degrees. when we encounter a leaf, we can solve the case in constant time. Therefore the recurrence becomes $T(n)\leq T(n-1)+T(n-3)$, which is so-called Narayana’s Cow Sequence and is bounded by $O(1.46558^n)$.

    回复

发表评论

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