Istnieje słynna i elegancka redukcja od maksymalnego problemu dwustronnego dopasowania do problemu maksymalnego przepływu: tworzymy sieć z węzłem źródłowym , węzłem końcowym i jednym węzłem dla każdego elementu, który ma być dopasowany, a następnie dodajemy odpowiednie krawędzie.
Z pewnością istnieje sposób na ograniczenie maksymalnego przepływu do maksymalnego dopasowania dwustronnego w czasie wielomianowym, ponieważ oba z nich można rozwiązać indywidualnie w czasie wielomianowym. Czy jednak istnieje „ładna” redukcja czasu wielomianu od maksymalnego przepływu (na ogólnych wykresach) do maksymalnego dopasowania dwustronnego?
reductions
network-flow
bipartite-matching
templatetypedef
źródło
źródło
Odpowiedzi:
O dziwo, taka redukcja nie jest znana. Jednak w ostatnim artykule, Madry (FOCS 2013), pokazał, jak ograniczyć maksymalny przepływ na wykresach wydajności jednostkowej do (logarytmicznie wielu przypadków) maksymalnego dopasowywania na grafach dwustronnych.b
Jeśli nie jesteś zaznajomiony z problemem maksymalnego dopasowania , jest to uogólnienie dopasowania, zdefiniowane w następujący sposób: dane wejściowe to wykres (w naszym przypadku wykres dwustronny), i a zbiór wymagań całkowitych dla każdego wierzchołka, przy czym żądanie wierzchołka oznaczone jest przez . Celem jest znalezienie możliwie największego zestawu krawędzi tak aby żaden wierzchołek nie miał więcej niż krawędzi w incydencie na . Jest to proste ćwiczenie, aby uogólnić redukcję z dopasowania dwustronnego na maksymalne przepływy i wykazać podobną redukcję z dwustronnego dopasowaniab G=(V,E) v bv S v bv S v b - dopasowanie do maksymalnych przepływów. (Jednym z) zaskakujących rezultatów pracy Madry'ego jest to, że w pewnym sensie problemy te są równoważne, dając prostą redukcję, która zmniejsza maksymalny przepływ na wykresach wydajności jednostkowej (ogólnie wykresy, na których suma pojemności, jest liniowy pod względem liczby krawędzi, ) do problemu dopasowania na wykresie z węzłami , wierzchołkami i sumą wymagań.|u|1 m b O(m)
Jeśli interesują Cię szczegóły, zobacz sekcję 3, aż do Twierdzenia 3.1 i sekcji 4 (oraz dowód poprawności w Załączniku C) wersji ArXiv artykułu Madry'ego, tutaj . Jeśli terminologia nie jest oczywista, zapoznaj się z rozdziałem 2.5 dotyczącym problemu dopasowania i pamiętaj, że to pojemność krawędzi w oryginalnej instancji maksymalnego przepływu.b ue e
źródło
Oto próba odpowiedzi na twoje pytanie:
Twierdzenie Koniga o dwustronnych dopasowaniach zostało udowodnione i w konsekwencji zredukowane za pomocą twierdzenia Max-Flow Min-Cut. Twierdzenie Koniga stwierdza, co następuje. Jeśli G jest grafem dwustronnym, to max {| M | : M jest dopasowaniem} = min {| C | : C to okładka}. Dowód. Część max {| M |} ≤ {| C |} jest trywialna. Niech P i Q będą klasami dwudzielnymi G. Dodajemy dwa wierzchołki, r i s do G, i łuki rp dla każdego i qs dla każdego , i bezpośrednią krawędź pq od do . To jest wykres . Definiujemy pojemności u (rp) = 1, u (pq) = , u (qs) = 1. Niech x będzie możliwym do wykonania całkowym przepływem x, a następnie x (e) = 0 lub 1, abyśmy mogli zdefiniować M = { : x (e) = 1}. M jest dopasowaniem do | M | =p∈P q∈Q p∈P q∈Q G∗ ∞ e∈E fx . Następnie dopasowanie M w G daje możliwy do uzyskania całkowity przepływ x w o wartości przepływu = | M | następująco. Zdefiniuj x (pq) = 1, jeśli , x (rp) = 1, jeśli p jest padające na krawędź w M, x (qs) = 1, jeśli q jest padane na krawędź w M, we wszystkich pozostałych przypadkach x (e) = 0. Zatem maksymalny rozmiar dopasowany M w G odpowiada maksymalnemu przepływowi w , którego rozmiar jest równy rozmiarowi minimalnego cięcia według twierdzenia Max-Flow Min-Cut. Weź pod uwagę minimalne cięcie r - s δ (R). Ma skończoną pojemność, więc nie zawiera łuku pq. Wtedy każda krawędź G jest incydentowana z elementem C = (P \ R) , to znaczy C jest przykryciem. Ponadto u (C) = | P \ R | +i tak C jest okładką o rozmiarze | M |.G∗ fx pq∈M G∗ ∪(Q∩R) |Q∩R|
Mam na myśli, że to wszystko, moim zdaniem, zadałeś w pytaniu i to jest moja potencjalna odpowiedź :).
źródło