Was ist ein Algorithmus, um eine minimale Scheitelpunktabdeckung in einem zweigeteilten Graphen mit gewichteten Scheitelpunkten zu finden?

10

Ich weiß, dass ich für einen ungewichteten zweigliedrigen Graphen die minimale Scheitelpunktabdeckung finden kann, indem ich zuerst die maximale Übereinstimmung finde und sie unter Verwendung des Königschen Theorems in eine Scheitelpunktabdeckung verwandle. Gibt es eine Modifikation, die verwendet werden könnte, wenn die Knoten gewichtet werden?

ds.algorithms graph-theory Andrey Fedorov
quelle
1
Obwohl die von Shiva Kintali gegebene Lösung Ihr Problem löst, möchte ich nur eine kurze Bemerkung hinzufügen: König's Theorem dreht sich alles um Kardinalität. Sie könnten Gewichte hinzufügen und eine minimale zweigliedrige Übereinstimmung mit minimalen Kosten finden (es gibt Algorithmen für diese mit Kantengewichten; stattdessen einfach zu verwendende Knotengewichte), aber Sie würden immer noch nur die minimale minimale Scheitelpunktabdeckung für minimale Kosten erhalten - was möglicherweise nicht der Fall ist die Min-Cost-Vertex-Abdeckung (dh die aus mehr Knoten bestehen könnte). Ein Min-Cost-Matching ohne Kardinalitätsbeschränkungen / -optimierung wäre einfach leer (für positive Gewichte)…
Magnus Lie Hetland

Antworten:

18

Das Problem der gewichteten Scheitelpunktabdeckung kann als ganzzahliges Programm formuliert werden (siehe http://en.wikipedia.org/wiki/Vertex_cover ). Wenn der Eingabediagramm zweiteilig ist, ist die Einschränkungsmatrix dieser IP völlig unimodular. Daher kann diese IP in Polynomzeit gelöst werden.

Weitere Einzelheiten zu unimodularen Gesamtmatrizen und den entsprechenden Algorithmen finden Sie im ausgezeichneten (dreibändigen) Buch von Alexander Schrijver .

Shiva Kintali
quelle
6
Genauer gesagt kann die IP durch einfaches Lösen der LP-Relaxation gelöst werden. Darüber hinaus kann man feststellen, dass das Dual der LP eine Verallgemeinerung der Anpassung ist (mit Kapazitäten, die den Gewichten der Scheitelpunkte in der Scheitelpunktabdeckungsinstanz entsprechen) und durch Reduzieren auf den maximalen Fluss auf die übliche Weise gelöst werden kann.
Chandra Chekuri
@ChandraChekuri Peudo-Code der maximalen Durchflussreduzierung finden Sie in Abbildung 4 in Inkrementelle Berechnung von Ressourcenumschlägen in Produzenten-Konsumenten-Modellen
xuhdev