max-independent-set

Maximum Independent Set

• Select a set of vertices from a graph to maximize the sum of weights selected, no two vertices are connected.
• NP-complete in general case, but linear time in a tree.
• Similarly: matching problem, in which edges are selected.
• Need to consider three values for one node
  • ${\text{OPT}}_{\text{inc}}(v)$: optimal matching of subtree at $v$, $v$ included
  • ${\text{OPT}}_{\text{not}}(v)$: $v$ not included.
  • $\text{OPT}(v)=\max \{{\text{OPT}}_{\text{inc}}(v),{\text{OPT}}_{\text{not}}(v)\}$

$$\{\begin{array}{l}{\text{OPT}}_{\text{not}}(v)=\sum _{i=1}^k\text{OPT}(v_i)\\ {\text{OPT}}_{\text{inc}}(v)=\max \left\{w(v,v_i)+{\text{OPT}}_{\text{not}}(v_i)+\sum _{j\ne i}^k\text{OPT}(v_i)\right\}\end{array}$$

To simplify the calculation of the second term, we have

$$S={\text{OPT}}_{\text{not}}(v)=\sum _{i=1}^k\text{OPT}(v_i)$$

so that ${\text{OPT}}_{\text{inc}}(v)$ can be expressed as

$$S-\text{OPT}(v_i)+w(v,v_i)+{\text{OPT}}_{\text{not}}(v_i)$$