2
$\begingroup$

Question

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.

$\endgroup$
2
$\begingroup$

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[1] = OPT_T[1] = OPT_B[1] = 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]$.

$\endgroup$
4
  • 2
    $\begingroup$ 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]$. $\endgroup$ – Sam Westrick May 19 '20 at 19:48
  • $\begingroup$ Oh yeah, obviously. Thank you! $\endgroup$ – Steven May 19 '20 at 19:50
  • $\begingroup$ 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]$. $\endgroup$ – turmond May 19 '20 at 20:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Steven May 19 '20 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.