В графе найти подмножество несмежных вершин наибольшего веса

[Grom1]

Добрый день.

Возникла такая задача - имеется граф, у которого вершины помечены натуральными числами (целыми положительными). Необходимо найти множество попарно несмежных вершин такое, что сумма меток была бы максимально возможной.

Если граф оказывается двудольным (изначально множество вершин на доли не разбито), то решение довольно простое - каждую компоненту связности разбиваем на доли (поиском в ширину - множество вершин четных и нечетных фронтов), выбираем доли с максимальной суммой меток, плюс добавляем изолированные вершины.

Как решить в общем случае - не могу понять. Может быть, можно попробовать каким-то хитрым образом выделять двудольные подграфы (выкидывая ребра) и искать максимум среди таких подграфов (но тут нужно еще и следить, чтобы не выкинуть ребро, инцидентное двум вершинам из доли с максимальной суммой, что мне представляется малореальным). Очень хотелось бы, чтобы алгоритм был полиномиальным и реализация работала достаточно быстро на числе вершин в пределах нескольких десятков (до сотни) и числе ребер в пределах тысячи.

[NSKuber]

Grom1 в сообщении #1112263 писал(а):

Очень хотелось бы, чтобы алгоритм был полиномиальным

Многим хотелось бы...
Потому что, найдя такой, вы докажете, что $P=NP$ и станете богатым и знаменитым
(https://ru.wikipedia.org/wiki/Задача_о_независимом_множестве)
Так что придётся вам пока довольствоваться неполиномиальными алгоритмами.

[Grom1]

Спасибо за ссылку! Похоже, мой случай - это в точности The Maximum-Weight Independent Set Problem. Вообще говоря, мне хватит и приближенного решения, а может у меня окажется граф специального вида, для которого существуют хорошие алгоритмы. Теперь, по крайней мере, знаю где искать.