Ograniczenie maksymalnego przepływu do dopasowania dwustronnego?

9

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.st

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?

templatetypedef
źródło
Czy pytasz o przepływ sieci w grafie dwustronnym lub w grafach ogólnych?
DW
Myślałem o maksymalnym przepływie na ogólnych wykresach.
templatetypedef
1
Redukcje czasu wielopłaszczyznowego w P są nudne: wystarczy rozwiązać instancję i wybrać jedną z dwóch instancji zakodowanych na stałe. Wiem, że nie tego chcesz, ale czy możesz precyzyjniej określić, co to jest?
Raphael
@Raphael Ostatni akapit mojego pytania nawiązywał do tego, o czym wspomniałeś, ponieważ tak, wyraźnie nie jest interesująca redukcja zgodnie z tym, co powiedziałeś. Szukam redukcji, która jest bardziej zgodna z redukcją od dopasowania do maksymalnego przepływu - transformacja strukturalna, która zachowuje podstawowe cechy. Zastanów się nad redukcjami wykonanymi w celu udowodnienia twardości NP, a nie trywialną redukcją „rozwiąż problem i wygeneruj instancję”.
templatetypedef
Czy redukcje gadżetów nie są zwykle liniowe? Właśnie to mam na myśli: spróbuj znaleźć bardziej ograniczoną klasę, która uniemożliwi nam „oszukiwanie”. (Nie jest jasne, co powinno oznaczać „zachowanie zasadniczych cech”).
Raphael

Odpowiedzi:

7

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 dopasowaniabG=(V,E)vbvSvbvSvb- 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|1mbO(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.buee

dwajc
źródło
-2

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 | =pPqQpPqQGeEfx . 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 |.GfxpqMG(QR)|QR|

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

marcincuber
źródło
2
Zauważ, że możesz tutaj używać LaTeXa, aby składać matematykę w bardziej czytelny sposób. Zobacz tutaj krótkie wprowadzenie.
DW
1
Czy możesz wyjaśnić, jak to odpowiada na pytanie? Czy konstruujesz algorytm, aby rozwiązać problem maksymalnego przepływu na ogólnych wykresach, używając algorytmu maksymalnego dopasowania dwustronnego? Jeśli tak, jaki jest algorytm? Wygląda na to, że wszystko, co robisz, to pokazywanie, jak rozwiązać problem maksymalnego przepływu dla specjalnego przypadku grafów dwustronnych w specjalnym przypadku, w którym wszystkie pojemności wynoszą 1 . Ale oczywiście ten problem jest trywialnie równoważny maksymalnemu dopasowaniu, jak już to pytanie wyjaśnia, więc nie rozumiem, jak to dodaje coś nowego. Nie rozumiem też, jak istotne są twierdzenia Koniga lub osłony wierzchołków.
DW
Zmniejszenie w tym przypadku jest kluczem do odpowiedzi na zestaw pytań. I wierzę w to, czego dokładnie szuka @templatetypedef. Nie wierzę, że redukcja czasu wielomianowego od maksymalnego przepływu (na ogólnych wykresach) byłaby inna. Pomyślę o tym jeszcze raz i być może dodam coś dodatkowego, ale nie mogę zrozumieć, dlaczego potrzebujemy różnych przypadków, aby uzyskać bardziej ogólne ograniczenie. Ale słuszne punkty.
marcincuber
Jest to standardowa redukcja podręcznika OD dwustronnego dopasowania DO maksymalnego przepływu. Pytanie dotyczy redukcji w przeciwnym kierunku: od maksymalnego przepływu do dopasowania dwustronnego.
JeffE