# Dynamic Programming, Counting Independent Sets My first thought is to make OPT(i, j), where i is n, and j is some condition on the column. But my experience with DP is from knapsack and weighted interval scheduling, but I'm unsure of how to approach this. Any ideas would be great.

## 1 Answer

Let $$OPT_N[i]$$ be the number of independent sets in the graph with $$2i$$ vertices with the additional constraint that neither of the leftmost two vertices can be selected into an independent set.

Let $$OPT_T[i]$$ be the number of independent sets in the graph with $$2i$$ vertices with the additional constraint that the top of the leftmost two vertices must be selected in the independent set.

Let $$OPT_B[i]$$ be the number of independent sets in the graph with $$2i$$ vertices with the additional constraint that the bottom-most of the leftmost two vertices must be selected in the independent set.

According to the above definitions $$OPT_N = OPT_T = OPT_B = 1$$ while, for $$i>1$$: \begin{align*} OPT_N[i] &= OPT_N[i-1] + OPT_T[i-1] + OPT_B[i-1]\\ OPT_T[i] &= OPT_N[i-1] + OPT_B[i-1]\\ OPT_B[i] &= OPT_N[i-1] + OPT_T[i-1] \end{align*}

The number of independent sets on a graph with $$2i$$ vertices is then $$OPT_N[n] + OPT_T[n] + OPT_B[n] = OPT_N[n+1]$$.

You can simplify the above formulas by noticing that you must have $$OPT_T[i] = OPT_B[i]$$.

• A typo fix: in your equations, I think you meant to define each OPT[i] in terms of OPT[i-1], e.g. $OPT_N[i] = OPT_N[i-1] + OPT_T[i-1] + OPT_B[i-1]$. – Sam Westrick May 19 '20 at 19:48
• Oh yeah, obviously. Thank you! – Steven May 19 '20 at 19:50
• Thank you for the thorough response. I am wondering if memoization is necessary in order to reduce the runtime? Since $OPT_{N}[i-1]$ may be computed from $OPT_{N}[i]$, but you wouldn't want to recurse again when computing $OPT_{T}[i]$ on computing $OPT_{N}[i-1]$. – turmond May 19 '20 at 20:19
• It's a dynamic programming algorithm, so you can just iteratively compute (and store) $OPT_T[i]$, $OPT_B[i]$, and $OPT_N[i]$ in increasing order of $i$. Memoization usually refers to recursive algorithms. – Steven May 19 '20 at 20:21