Dopasowanie maksymalnej masy i funkcje podmodularne

Biorąc pod uwagę dwudzielny wykres $G = (U \cup V, E)$ z dodatnimi wagami, niech $f: 2^U \rightarrow \mathbb{R}$ z $f(S)$ równym maksymalnemu dopasowaniu masy na wykresie . $G[S\cup V]$

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

matching submodularity

— George Octavian Rabanca
źródło

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

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.

K_{2, 2}

$K_{2,2}$

— András Salamon

@ AndrásSalamon Wygląda na to, że w ostatnim kroku zakładasz, że

jest addytywny, co nie jest prawdą. Dopasowanie Maksymalnie

może wykorzystać wierzchołki zostały użyte zarówno dopasowanie

. Mam na to dowód, ale zdecydowanie jestem bardziej zaangażowany niż to.

f

$f$

S \cap T

$S\cap T$

S ∖ T

$S \setminus T$

T ∖ S

$T \setminus S$

— George Octavian Rabanca

Definicja . Dla danego zbioru skończonego funkcja zbioru jest submodularna, jeśli dla dowolnego $A$ $f:2^A \rightarrow \mathbb{R}$ utrzymuje, że: $X, Y \subseteq A$

f (X) + f (Y) \geq f (X \cup Y) + f (X \cap Y) .

$f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).$

Lemat Biorąc pod uwagę dwudzielny wykres z dodatnimi wagami krawędzi, niech będzie funkcją, która odwzorowuje na wartość maksymalnego dopasowania masy w . Zatem jest podmodularny. $G = (A \cup B, E)$ $f: 2^A \rightarrow \mathbb{R}^+$ $S\subseteq A$ $G[S \cup B]$ $f$

Dowód. Napraw dwa zestawy i niech i będą dwoma dopasowaniami dla wykresów $X, Y \subseteq A$ $M_\cap$ $M_\cup$ $G[(X\cap Y) \cup B]$ i . Aby udowodnić lemat, wystarczy pokazać, że można podzielić krawędzie w i na dwa rozłączne dopasowania i $G[(X \cup Y) \cup B]$ $M_\cap$ $M_\cup$ $M_X$ $M_Y$ odpowiednio dla wykresów i . $G[X\cup B]$ $G[Y\cup B]$

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

Pozwolić jest zestaw ścieżek z co najmniej jednym wierzchołkiem wi pozwolić jest zestaw ścieżek z co najmniej jednym wierzchołkiem w. Dwie takie ścieżki są przedstawione na poniższym rysunku. $\mathcal{P}_X$ $\mathcal{C}$ $X \setminus Y$ $\mathcal{P}_Y$ $\mathcal{C}$ $Y \setminus X$

Zastrzeżenie 1. . $\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$

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

Niech i Oczywiste jest, że

M_{X} = (P_{X} \cap M_{\cup}) \cup ((C ∖ P_{X}) \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$

M_{Y} = (P_{X} \cap M_{\cap}) \cup ((C ∖ P_{X}) \cap M_{\cup}) .

$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$

M_{X} \cup M_{Y} = M_{\cap} \cup M_{\cup}

$M_X \cup M_Y = M_\cap\cup M_\cup$ i

. Aby udowodnić twierdzenie, pozostaje wykazać, że

są prawidłowymi dopasowaniami odpowiednio dla

. Aby zobaczyć, że

jest prawidłowym dopasowaniem dla

najpierw, że żaden wierzchołek

jest dopasowany przez

M_{X} \cap M_{Y} = M_{\cap} \cap M_{\cup}

$M_X \cap M_Y = M_\cap \cap M_\cup$

M_{X}

$M_X$

M_{Y}

$M_Y$

G [X \cup B]

$G[X\cup B]$

G [Y \cup B]

$G[Y\cup B]$

M_{X}

$M_X$

G [X \cup B]

$G[X\cup B]$

Y ∖ X

$Y \setminus X$

ponieważ

nie przecina

według zastrzeżenia 1, a

nie przecina

z definicji. W związku z tym,

wykorzystuje tylko wierzchołki

. Po drugie zauważ, że każdy wierzchołek

jest dopasowany co najwyżej jedną krawędzią

ponieważ w przeciwnym razie

należy do dwóch krawędzi

lub dwóch krawędzi

, co jest sprzeczne z definicją. Dowodzi to, że

M_{X}

$M_X$

P_{X}

$\mathcal{P}_X$

Y ∖ X

$Y \setminus X$

M_{\cap}

$M_\cap$

Y ∖ X

$Y \setminus X$

M_{X}

$M_X$

X \cup B

$X \cup B$

x \in X

$x\in X$

M_{X}

$M_X$

x

$x$

M_{\cup}

$M_\cup$

M_{\cap}

$M_\cap$

M_{X}

$M_X$ jest poprawnym dopasowaniem dla

; wykazanie, że

jest prawidłowym dopasowaniem dla

jest podobne.

G [X \cup B]

$G[X\cup B]$

M_{Y}

$M_Y$

G [Y \cup B]

$G[Y\cup B]$

— George Octavian Rabanca
źródło

To wygląda świetnie! Jako drobna sugestia: definicje

nie są symetryczne, więc twoje ostateczne twierdzenie, że „

... jest podobny” nie jest natychmiastowe. Jest bardziej jasne (myślę), jeśli pozwolisz

oznaczać połączone komponenty nie dotykające żadnego wierzchołka w

, a następnie ustaw

M_{X}

$M_X$

M_{Y}

$M_Y$

M_{Y}

$M_Y$

C^{'} ≐ C ∖ P_{X} ∖ P_{Y}

$\mathcal{C'} \doteq \mathcal{C} \setminus \mathcal{P}_X \setminus \mathcal{P}_Y$

X Δ Y

$X \Delta Y$

są takie same z

zamienionymi, a następnie ostatnie

zmieniono na

M_{X} = (P_{X} \cap M_{\cup}) \cup (P_{Y} \cap M_{\cap}) \cup (C^{'} \cap M_{\cap})

$M_X = (\mathcal{P}_X \cap M_\cup) \cup (\mathcal{P}_Y \cap M_\cap) \cup (\mathcal{C'} \cap M_\cap)$

M_{Y}

$M_Y$

X

$X$

Y

$Y$

M_{\cap}

$M_\cap$

M_{\cup}

$M_\cup$

— Andrew Morgan,