Maximale Gewichtsanpassung und submodulare Funktionen

10

Bei einem zweigeteilten Graphen mit positiven Gewichten sei f : 2 UR mit f ( S ) gleich der maximalen Gewichtsanpassung im Graphen G [ S V ] .G=(UV,E)f:2URf(S)G[SV]

Stimmt es, dass eine submodulare Funktion ist?f

George Octavian Rabanca
quelle
3
Was denken Sie? Haben Sie versucht, es zu beweisen / zu widerlegen?
Yuval Filmus
Intuitiv scheint es wahr zu sein, aber ich konnte es nicht beweisen. Ich denke auch, dass es ein bekanntes Ergebnis sein sollte, wenn es wahr ist, aber ich konnte keine Referenz finden.
George Octavian Rabanca
2
Dies gilt für ungewichtete Fälle, da diese auf Kleinigkeiten reduziert werden können. Es ist nicht offensichtlich, wie man die gewichtete Version beweist ...
Chao Xu
Betrachten Sie mit den Kantengewichten 1,1,1,2. K2,2
András Salamon
1
@ AndrásSalamon Es scheint, als ob Sie im letzten Schritt annehmen, dass additiv ist, was nicht wahr ist. Die maximale Übereinstimmung von S T kann Eckpunkte verwenden, die bereits durch die Übereinstimmung von S T und T S verwendet wurden . Ich habe jetzt einen Beweis dafür, bin aber definitiv mehr involviert. fSTSTTS
George Octavian Rabanca

Antworten:

1

Definition . Für eine gegebene endliche Menge ist eine Mengenfunktion f : 2 AR submodular, wenn für jedes X , Y A gilt: f ( X ) + f ( Y ) f ( X Y ) + f ( X. Y ) .Af:2ARX,YA

f(X)+f(Y)f(XY)+f(XY).

Lemma Bei einem zweigeteilten Graphen mit positiven Kantengewichten sei f : 2 AR + die Funktion, die S A auf den Wert der maximalen Gewichtsübereinstimmung in G [ S B ] abbildet. . Dann ist f submodular.G=(AB,E)f:2AR+SAG[SB]f

Beweis. Fixiere zwei Mengen und sei M und M zwei Übereinstimmungen für die Graphen G [ ( X Y ) B ] bzw. G [ ( X Y ) B ] . Der Beweis des Lemmas reicht aus, um zu zeigen, dass es möglich ist, die Kanten in M und M in zwei disjunkte Übereinstimmungen M X und M Y zu unterteilenX,YAMMG[(XY)B]G[(XY)B]MMMXMYfür die Graphen bzw. G [ Y B ] .G[XB]G[YB]

Die Kanten von und M bilden eine Sammlung alternierender Pfade und Zyklen. Lassen C diese Sammlung bezeichnen und beobachten , dass kein Zyklus von C enthält Vertices aus X Y oder Y X . Dies gilt, weil M nicht mit diesen Eckpunkten übereinstimmt.MMCCXYYXM

PXCXYPYCYX

Geben Sie hier die Bildbeschreibung ein

PXPY=

PPXPYxXYPyYXPxyXYMPxyAPMMxy

MX=(PXM)((CPX)M)
MY=(PXM)((CPX)M).
MXMY=MMMXMY=MMMXMYG[XB]G[YB]MXG[XB]YXMXPXYXMYXMXXBxXMXxMMMXG[XB]MYG[YB]
George Octavian Rabanca
quelle
MXMYMYCCPXPYXΔYMX=(PXM)(PYM)(CM)MYXYMM