Независимое множество максимального веса в дереве

Множество вершин в графе независимо (independent), если никакая пара вершин в нём не соединена ребром.

Дано дерево, каждая вершина $v$ которого имеет вес $w_{v}$. Необходимо найти независимое множество максимального суммарного веса.

✍️ Невзвешенная версия этой задачи (все веса равны единице) решается жадным алгоритмом.

Динамическое программирование по поддеревьям

Выберем любую вершину $r$ в качестве корня дерева. Теперь каждой вершине дерева $v$ соответствует подзадача поиска независимого множества максимального веса в поддереве этой вершины; обозначим искомое множество за $I_{v}$. Как выразить решение подзадачи для вершины $v$ через подзадачи попроще? Если сама вершина $v$ не входит в $I_{v}$, то $I_{v}$ объединение $I_{u}$ по всем $u$ - детям $v$. Если же $v$ входит в $I_{v}$, то никто из детей $v$ в $I_{v}$ входить не может. В этом случае $I_{v}$ - объединение $I_{u}$ по всем $u$ - “внукам” $v$ - детям детей $v$.

Пусть

$$ I[v]=\sum_{u \in I_{v}} w_{u} $$

Удобно также ввести вспомогательную величину

$$ J[v]=\sum_{u-\text { ребёнок } v} I[u] . $$

Из рассуждений выше получаем

$$ I[v]=\max \left(J[v], w_{v}+\sum_{u-\text { ребёнок } v} J[u]\right) . $$

Теперь все значения $I$, $J$ легко вычислить, запустив поиск в глубину из $r$. Получаем решение за $O(V+E)$.

1
2
3
4
5
6
7
8
9


dfs(v, parent):
    I[v] = w[v], J[v] = 0
    for u in to[v]:
        if u == parent:
            continue
        dfs(u, v)
        I[v] += J[u], J[v] += I[u]
    I[v] = max(I[v], J[v])
dfs(0, -1) # r = 0

Восстановление ответа

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


# skip = True, если вершина v точно не входит в ответ
restoreSet(v, parent, skip):
    childSkip = False
    if (not skip) and I[v] > J[v]: # v входит в ответ
        res.push_back(v)
        childSkip = True # дети v в ответ не входят
    for u in to[v]:
        if u == parent:
            continue
        restoreSet(u, v, childSkip)
restoreSet(0, -1, False)