Oblicz maksymalny przepływ z minimalnego cięcia

Wiemy, że obliczenie maksymalnego przepływu lub. minimalne ograniczenie sieci o przepustowości jest równoważne; por. twierdzenie o maksymalnym przepływie min. cięcie .

Mamy (mniej lub bardziej wydajne) algorytmy obliczania maksymalnych przepływów, a obliczanie minimalnego cięcia przy maksymalnym przepływie nie jest ani trudne, ani drogie.

Ale co na odwrót? Biorąc pod uwagę minimalne cięcie, jak możemy określić maksymalny przepływ? Oczywiście bez rozwiązania Max-Flow od zera, a najlepiej też szybciej .

Kilka myśli:

Od minimalnego cięcia znamy maksymalną wartość przepływu. Nie widzę, w jaki sposób te informacje pomagają standardowi w podejściu do ścieżki rozszerzania i zmiany etykiety, chociaż dostosowanie tej drugiej wydaje się nieco bardziej prawdopodobne.
Nie możemy użyć minimalnego cięcia, aby podzielić sieć na dwie części i powtórzyć, ponieważ nie zmniejszy to problemu w najgorszym przypadku (jeśli jedna partycja jest singletonem); również nie mielibyśmy minimalnego cięcia mniejszych instancji.
Czy znajomość wartości maksymalnego przyspieszenia przyspiesza rozwiązanie Max-Flow LP, być może poprzez uzupełniające się warunki luzu?

algorithms graphs network-flow

— Raphael
źródło

Powiązane pytanie: czy znamy algorytmy obliczania minimalnych cięć (które nie używają algorytmów maksymalnego przepływu)?

— Raphael

Zdecydowanie tak, randomizowany algorytm Kargera jest bardzo popularny i do tego potrzebujesz zerowej wiedzy na temat maksymalnych przepływów.

— Juho,

Jeśli nie chcesz algorytmów losowych, algorytm Stoer-Wagnera jest bardzo prosty, również bez technik przepływu.

— Juho,

Dobry towar! Tutaj jest kolejne wyzwanie. Znając tylko przenośniki do cięcia minimalnego

bitów informacji (w większości), ponieważ każde cięcie jest izomorficzny podgrupie

. Jednak maksymalny przepływ może wymagać znacznie więcej niż

fragmenty informacji do przedstawienia (szczególnie, jeśli pojemności są duże). Tak więc, teoretycznie informacje, nie możesz liczyć na algorytm, który patrzy tylko na wycięcie i wypluwa przepływ; musiałby też spojrzeć na wykres i wykonać dodatkowe obliczenia. (Zdaję sobie sprawę, że to nie jest wielka przeszkoda.)

| V |

$|V|$

V

$V$

| V |

$|V|$

— DW

Odpowiedzi:

W najgorszym przypadku samo cięcie minimalne nie przekazuje wielu informacji o maksymalnym przepływie. Rozważmy wykres w którym minimum -cut ma wartość . Jeśli przedłużę , dodając nowy wierzchołek i krawędź o wadze , minimalne -cut na nowym wykresie składa się tylko z krawędzi $G=(V,E)$ $s,t$ $w$ $G$ $s'$ $(s',s)$ $w$ $s',t$ $(s', s)$ ale to nie daje żadnych informacji o tym, jak uzyskać jednostek przepływu od do . $w$ $s$ $t$

W rzeczywistości minimalne cięcie mówi o wartości przepływu, ale nie o tym, jak go osiągnąć. Oznacza to, że znajomość minimalnego cięcia może przyspieszyć znalezienie przepływu co najwyżej przez czynnik logarytmiczny, ponieważ moglibyśmy przeprowadzić wyszukiwanie binarne, aby znaleźć wartość cięcia.

— Tom van der Zanden
źródło

Ale ten czynnik logarytmiczny byłby związany z rozmiarem przedziału wartości potencjalnego przepływu, a zatem nieporównywalny z istniejącymi górnymi granicami przy rozwiązywaniu maksymalnego przepływu, które zależą tylko od wielkości wykresu. To powiedziawszy, nawet logarytmiczne przyspieszenie byłoby interesujące. Nie jestem przekonany, że znajomość wartości maksymalnego przepływu wcale nie pomaga.

— Raphael

-2

Z pewnością istnieją algorytmy, które pozwalają obliczyć minimalne cięcie przed obliczeniem maksymalnego przepływu. Dwa takie algorytmy to „push push” i pseudoprzepływowe algorytmy, które są ze sobą ściśle powiązane. Ten ostatni jest bardziej wydajny. Oba te algorytmy wykorzystują specjalne właściwości wykresu resztkowego, które iteracyjnie poprawiają, aby uzyskać maksymalny przepływ z minimalnego cięcia. Aby uzyskać szczegółowe informacje, zdecydowanie polecam przeczytanie kodu i dokumentów.

Aby rozwinąć przypadek etykiety push push, gdy algorytm nie może przepchnąć więcej przepływu do zlewu, gwarantuje się, że obliczył minimalne cięcie. Ta część algorytmu nazywa się fazą 1 z powodu braku lepszej nazwy. Faza 2 jest bardziej wydajnym etapem, w którym przekształca minimalne cięcie w maksymalny przepływ poprzez iteracyjne anulowanie cykli na wykresie resztkowym za pomocą pierwszego wyszukiwania z jedną głębokością i wypychanie nadmiaru z powrotem do źródła. Uważam, że faza 2 może być bezobjawowo bardziej wydajna niż faza 1.

— pies
źródło

Przeczytaj ponownie pytanie; to nie ten, na który odpowiedziałeś.

— Raphael

Podany przeze mnie przykład PR zakłada, że podczas obliczania skrótu obliczałeś inne informacje po drodze. Twoje pierwotne pytanie nie określało, czy możesz zachować inne informacje wraz z minimalnym cięciem, aby ułatwić późniejsze obliczenie maksymalnego przepływu. Czy słusznie jest podać swoje pierwotne pytanie jako „Biorąc pod uwagę minimalne cięcie i brak innych informacji , w jaki sposób możemy ustalić maksymalny przepływ?”.

— pies

Powiedziałem: „biorąc pod uwagę A, obliczyć B”. Jedynym rozsądnym założeniem jest to, że otrzymujesz tylko A, w przeciwnym razie mówienie o problemach obliczeniowych byłoby bardzo rozmytą sprawą.

— Raphael

Pozwolę sobie być innego zdania. Z praktycznego punktu widzenia nigdy nie obliczalibyście skrawka minimalnego bez obliczenia dodatkowych informacji (takich jak w algorytmie PR). Z teoretycznego punktu widzenia fajnie byłoby rozważyć rzeczy w izolacji, jak mówisz. Kontekst jest tutaj kluczowy.

— pies