Dopasowanie maksymalnej masy i funkcje podmodularne

10

Biorąc pod uwagę dwudzielny wykres G=(UV,E) z dodatnimi wagami, niech f:2UR z f(S) równym maksymalnemu dopasowaniu masy na wykresie .G[SV]

Czy to prawda, że jest funkcją podmodularną?f

George Octavian Rabanca
źródło
3
Co myślisz? Próbowałeś to udowodnić / obalić?
Yuval Filmus
Intuicyjnie wydaje się, że to powinna być prawda, ale nie mogłem tego udowodnić. Myślę też, że jeśli to prawda, powinien to być dobrze znany wynik, ale nie mogłem znaleźć referencji.
George Octavian Rabanca
2
Dotyczy to przypadku nieważonego, ponieważ można go zredukować do minimalnych cięć. Nie jest oczywiste, jak udowodnić ważoną wersję ...
Chao Xu
Rozważ z obciążnikami krawędzi 1,1,1,2. K2,2
András Salamon
1
@ AndrásSalamon Wygląda na to, że w ostatnim kroku zakładasz, że jest addytywny, co nie jest prawdą. Dopasowanie Maksymalnie S T może wykorzystać wierzchołki zostały użyte zarówno dopasowanie S , T i T S . Mam na to dowód, ale zdecydowanie jestem bardziej zaangażowany niż to. fSTSTTS
George Octavian Rabanca

Odpowiedzi:

1

Definicja . Dla danego zbioru skończonego funkcja zbioru f : 2 AR jest submodularna, jeśli dla dowolnego XAf:2AR utrzymuje, że: f ( X ) + f ( Y ) f ( X Y ) + f ( X Y ) .X,YA

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

Lemat Biorąc pod uwagę dwudzielny wykres z dodatnimi wagami krawędzi, niech f : 2 AR + będzie funkcją, która odwzorowuje S A na wartość maksymalnego dopasowania masy w G [ S B ] . Zatem f jest podmodularny.G=(AB,E)f:2AR+SAG[SB]f

Dowód. Napraw dwa zestawy i niech M i M będą dwoma dopasowaniami dla wykresów G [ ( X Y ) B ]X,YAMMG[(XY)B] i . Aby udowodnić lemat, wystarczy pokazać, że można podzielić krawędzie w M i M na dwa rozłączne dopasowania M X i M YG[(XY)B]MMMXMYodpowiednio dla wykresów i G [ Y B ] .G[XB]G[YB]

Krawędzie M i tworzą zbiór naprzemiennych ścieżek i cykli. Niech C oznacza tę kolekcję i obserwować, że żaden cykl C zawiera wierzchołki z X Y lub Y X . Dzieje się tak, ponieważ M nie pasuje do tych wierzchołków.MCCXYYXM

Pozwolić jest zestaw ścieżek C z co najmniej jednym wierzchołkiem wXYi pozwolić P Y jest zestaw ścieżek C z co najmniej jednym wierzchołkiem wYX. Dwie takie ścieżki są przedstawione na poniższym rysunku.PXCXYPYCYX

wprowadź opis zdjęcia tutaj

Zastrzeżenie 1. . PXPY=

Załóżmy, że w przeciwieństwie, że istnieje ścieżka . Niech x będzie wierzchołkiem w X Y na ścieżce P i podobnie niech y będzie wierzchołkiem w Y PPXPYxXYPy na ścieżce P . Zauważyć, że ponieważ ani X ani y należące do X. Y nie należą one do dopasowania M z definicji, a więc są to punkty końcowe drogi P . Ponadto, ponieważ zarówno x, jakiYXPxyXYMPx znajdują się w A , ścieżka P ma równą długość, a ponieważ jest to ścieżka naprzemienna, pierwsza lub ostatnia krawędź należy do M . Dlatego M odpowiada albo x, albo y , co jest sprzeczne z definicją i potwierdza twierdzenie.yAPMMxy

Niech i M Y = ( P XM ) ( ( CP X ) M ) . Oczywiste jest, że M XM Y = M M

MX=(PXM)((CPX)M)
MY=(PXM)((CPX)M).
MXMY=MM i . Aby udowodnić twierdzenie, pozostaje wykazać, że M X i M Y są prawidłowymi dopasowaniami odpowiednio dla G [ X B ] i G [ Y B ] . Aby zobaczyć, że M X jest prawidłowym dopasowaniem dla G [ X B ] , zauważ najpierw, że żaden wierzchołek Y X nie jest dopasowany przez MMXMY=MMMXMYG[XB]G[YB]MXG[XB]YX ponieważ P X nie przecina Y X według zastrzeżenia 1, a M nie przecina Y X z definicji. W związku z tym, M X wykorzystuje tylko wierzchołki X B . Po drugie zauważ, że każdy wierzchołek x X jest dopasowany co najwyżej jedną krawędzią M X, ponieważ w przeciwnym razie x należy do dwóch krawędzi M lub dwóch krawędzi M , co jest sprzeczne z definicją. Dowodzi to, że M XMXPXYXMYXMXXBxXMXxMMMXjest poprawnym dopasowaniem dla ; wykazanie, że M Y jest prawidłowym dopasowaniem dla G [ Y B ] jest podobne.G[XB]MYG[YB]
George Octavian Rabanca
źródło
To wygląda świetnie! Jako drobna sugestia: definicje i M Y nie są symetryczne, więc twoje ostateczne twierdzenie, że „ M Y ... jest podobny” nie jest natychmiastowe. Jest bardziej jasne (myślę), jeśli pozwolisz C CP XP Y oznaczać połączone komponenty nie dotykające żadnego wierzchołka w X Δ Y , a następnie ustaw M XMXMYMYCCPXPYXΔY i M Y są takie same z X i Y zamienionymi, a następnie ostatnie M zmieniono na M . MX=(PXM)(PYM)(CM)MYXYMM
Andrew Morgan,