Задача про незалежну множину

Структура дерева сама підказує рішення задачі: Позначимо коренем дерева будь-яку вершину і назвемо її ${\displaystyle r}$. Нехай ${\displaystyle I(u)}$ позначає розмір максимальної незалежної множини вершин піддерева, коренем якого є вершина ${\displaystyle u}$. Тоді відповіддю на задачу буде ${\displaystyle I(r)}$.

Неважко бачити, що якщо ми включаємо вершину u в максимальну незалежну множину, то її потужність збільшується на 1, але його дітей ми брати не можемо (так як вони з'єднані ребром з вершиною u); якщо ж ми не включаємо цю вершину, то потужність максимальної незалежної множини дорівнюватиме сумі розмірів незалежних множин дітей цієї вершини. Залишається тільки вибрати максимум з цих двох варіантів, щоб отримати рішення задачі:

${\displaystyle I(u)=\max \left\{1\ +\ \sum _{{\text{grandchild}}\ w\ of\ u}I(w),\ \sum _{{\text{child}}\ w\ of\ u}I(w)\right\},}$

де grandchild позначає всякого «онука» вершини, а child позначає всякого нащадка вершини.

Вважаємо, що у вершині u зберігається ${\displaystyle I(u)}$:

  function get_independent_set(Node u)
  {       
      якщо I(u) вже пораховане, то повернути I(u)
      //потужність множини, яку можна отримати, якщо не брати вершину u
      children_sum = 0
      //потужність множини, яку можна отримати, якщо взяти вершину u
      grandchildren_sum = 0
      //цикл по всім дітям
      for i := 1 to child_num do
         children_sum = children_sum + get_independent_set(children[i])
      //цикл по всіх онукам
      for i:= 1 to grandchildren_num
         grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
      //запам'ятовуємо, щоб не перераховувати ще раз
      I(u) = max(1 + grandchildren_sum, children_sum)
     повернути I(u)
  }

Виклик get_independent_set(r) дасть відповідь на завдання. Час виконання алгоритму, очевидно, O(|V| + |E|).