# 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: [[match|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{cases} \text{OPT}_\text{not}(v) = \displaystyle \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) + \displaystyle \sum_{j\ne i}^k \text{OPT}(v_i) \right\} \end{cases} $ 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) $