Ograniczenie maksymalnego przepływu do dopasowania dwustronnego?

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.$s$$t$

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?

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 dopasowania$b$$G=(V,E)$$v$$b_v$$S$$v$$b_v$$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$$u_e$$e$

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\in P$$q \in Q$$p\in P$$q\in Q$$G_{∗}$$\infty$$e \in E$$f_{x}$ . 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_{∗}$$f_{x}$$pq \in M$$G_{∗}$$\cup (Q \cap R)$$|Q \cap R|$

Mam na myśli, że to wszystko, moim zdaniem, zadałeś w pytaniu i to jest moja potencjalna odpowiedź :).