Что такое алгоритм для нахождения минимального покрытия вершин на двудольном графе со взвешенными вершинами?

Я знаю, что для невзвешенного двудольного графа я могу найти минимальное покрытие вершин, сначала найдя максимальное совпадение и превратив его в покрытие вершин, используя теорему Кенига. Можно ли использовать модификацию, если узлы взвешены?

ds.algorithms graph-theory Андрей Федоров
источник

Хотя решение, данное Шивой Кинтали, решает вашу проблему, я просто хотел бы добавить небольшое замечание: теорема Кенига о кардинальности. Вы могли бы добавить веса, найдя минимальное двойное максимальное соответствие, состоящее из двух частей (для этого есть алгоритмы с весами ребер; вместо этого легко использовать веса узлов), но вы все равно просто получите минимальное минимальное покрытие вершин - что может и не быть покрытие вершин минимальной стоимости (то есть, которое может состоять из большего количества узлов). Соответствие минимальной стоимости без ограничений / оптимизации количества элементов будет просто пустым (для положительных весов)…

Магнус Ли Хетланд

Ответы:

Взвешенная проблема покрытия вершин может быть сформулирована как целочисленная программа (см. Http://en.wikipedia.org/wiki/Vertex_cover ). Когда входной граф является двудольным, матрица ограничений этого IP является полностью унимодулярной. Следовательно, этот IP может быть решен за полиномиальное время.

Для получения более подробной информации об общих унимодулярных матрицах и соответствующих алгоритмах см. Превосходную (трехтомную) книгу Александра Шрайвера .

Шива Кинтали
источник

Чтобы быть более точным, IP можно решить простым решением релаксации LP. Кроме того, можно заметить, что дуал LP является обобщением сопоставления (с емкостями, соответствующими весам вершин в экземпляре покрытия вершин) и может быть решен путем сведения к максимальному потоку обычным способом.

Чандра Чекури

@ChandraChekuri peudo-код максимального сокращения потока может быть найден на рисунке 4 в Постепенном вычислении ресурсов-

xuhdev