Czy minimalne cięcie może być łatwiejsze niż przepływ sieci?

18

Dzięki twierdzeniu o maksymalnym przepływie min-cut wiemy, że możemy użyć dowolnego algorytmu do obliczenia maksymalnego przepływu na grafie sieciowym do obliczenia -min-cut. Dlatego złożoność obliczenia minimum -cięcie jest nie większa niż złożoność obliczenia przepływu maksymalnego .(s,t)(s,t)(s,t)

Czy może być mniej? Czy może istnieć algorytm obliczania cięcia minimalnego szybciej niż jakikolwiek algorytm maksymalnego przepływu?(s,t)

Próbowałem znaleźć zmniejszenie zmniejszenie ) -max problemu przepływu do problemu -min-cut, ale nie był w stanie znaleźć. Moją pierwszą myślą było użycie algorytmu „dziel i rządź”: najpierw znajdź minimalne cięcie, które dzieli wykres na dwie części; teraz rekurencyjnie znajdź maksymalny przepływ dla lewej części i maksymalny przepływ dla prawej części i połącz je razem ze wszystkimi krawędziami przecinającymi cięcie. To rzeczywiście działałoby, aby uzyskać maksymalny przepływ, ale jego najgorszy czas działania może być tak długi jak razy większy niż czas działania algorytmu cięcia minimalnego. Czy jest lepsza redukcja?(s,t(s,t)O(|V.|)

Zdaję sobie sprawę, że twierdzenie o maksymalnym przepływie pokazuje, że złożoność obliczenia wartości maksymalnego przepływu jest taka sama, jak złożoność obliczenia wydajności minimalnego cięcia, ale nie o to pytam. Pytam o problem ze znalezieniem maksymalnego przepływu i znalezienia minimalnego cięcia (jawnie).

Jest to bardzo ściśle związane z Obliczaniem maksymalnego przepływu z minimalnego cięcia , z wyjątkiem: (1) Jestem skłonny zezwolić na redukcje Cooka (redukcje Turinga), nie tylko redukcje Karp (redukcje wielokrotne jeden) i (2) być może biorąc pod uwagę , możemy znaleźć wykres taki, że minimalne cięcie ułatwia obliczenie maksymalnego przepływu , co jest czymś, co jest poza zakresem tego drugiego pytania.solsol′sol′sol

complexity-theory reductions network-flow graph-algorithms DW
źródło
2
@AshkanKzme, nie śledzę cię; czy możesz rozwinąć? Jak stwierdzam w czwartym akapicie pytania, twierdzenie o maksymalnym przepływie pokazuje, że wartość maksymalnego przepływu jest równa pojemności min. Cięcia. Podejrzewam, że właśnie o tym myślisz. Jednak znajomość wartości maksymalnego przepływu nie mówi ci o samym maksymalnym przepływie (np. Ile wysłać na poszczególnych krawędziach). To pytanie dotyczy złożoności obliczania samego maksymalnego przepływu w porównaniu do obliczania samego minimalnego cięcia. Moje pytanie jest dokładnie takie, jak podano w drugim akapicie pytania.
DW
2
@AshkanKzme, Nie, nie pomyliłem się. Domyślnie zakładasz, że Ford-Fulkerson jest najszybszym możliwym algorytmem do znalezienia skrótu ... ale o ile mi wiadomo, nikt nigdy tego nie udowodnił i nie wiemy, czy to prawda, czy nie. Wydaje mi się, że popełniasz standardowy błąd w debiucie z dowodami z dolnej granicy: „Nie widzę sposobu, aby rozwiązać ten problem szybciej, więc musi to być niemożliwe”. (PS Mówisz mi o standardowych rzeczach z podręcznika na temat maksymalnego cięcia min-flow. Doceniam twoją próbę pomocy, ale już to wiem ...)
DW
1
Jeśli chodzi o stwierdzenie „Myślę, że można udowodnić, że jeśli masz tylko cięcie minimalne, możesz uzyskać maksymalny przepływ”, cóż, zachęcam do napisania odpowiedzi z dowodem na to - ponieważ to w zasadzie to moje pytanie jest zadawane. Nigdy nie widziałem na to dowodu, ale jeśli tak, mam nadzieję, że to napiszesz!
DW
1
@DW Myślę, że mam teraz trochę lepiej pytanie. Wydaje mi się, że zniechęciło mnie to, że dajesz wielomianową redukcję Turinga. Czy nie potrzebujesz stałej redukcji Turinga, aby udowodnić , a nawet udowodnienie, że taka redukcja nie jest możliwa, nie obala go? fa(n)=Θ(sol(n))
Thomas Bosman,
1
@ThomasBosman, tak, to prawda. [Przepraszam za zamieszanie. Redukcja, którą podałem w pytaniu, dowodzi, że , co jest bardzo słabą dolną granicą. Mam nadzieję, że może nastąpić redukcja, która dowodzi, że f ( n ) = Ω ( g ( n ) ) , ale nie wiem, jak skonstruować taką rzecz.]fa(n)=Ω(sol(n)/n)fa(n)=Ω(sol(n))
DW

Odpowiedzi:

-1

Oto możliwe podejście:

Załóżmy, że znasz przecięcie S, a następnie znalezienie przepływu od do t jest problemem przepływu sieci o minimalnym koszcie przy zerowym koszcie, ponieważ znasz dokładnie odpływ przy każdym wierzchołku w V ∖ S i napływie w t . Załóżmy, że f oznacza przepływ S - t, a A macierz łuku węzłowego (tj. Rząd i , col j ma 1, jeśli i jest ogonem j , -1 jeśli jego głowa, zero w przeciwnym razie), i niech b będzie takie, że A f = b, jeśli fS.tV.∖S.tfaS.-tZAjajotjajotbZAfa=bfazaspokaja podaż / popyt i ochronę przepływu. Następnie z eliminacją gaussa możemy znaleźć realne rozwiązanie w operacje.|V.|3)

Aby znaleźć wycięcie z przepływu, musimy zbudować wykres resztkowy, który zajmuje najwyżej czas, a następnie potencjalnie trawers | V | wierzchołki. |mi||V.|

Tak więc dla kompletnych wykresów i minimalnego cięcia będącego tylko źródłem lub tylko zlewem, redukcja zajmuje tyle samo czasu w obu najgorszych przypadkach. Myślę jednak, że znalezienie realnego rozwiązania dla można zrobić szybciej niż | V | 3)ZAfa=b|V.|3) biorąc pod uwagę specjalną strukturę. Nie jestem jednak pewien, jak to udowodnić.

Thomas Bosman
źródło
Nie rozumiem, jak znaleźć przy użyciu eliminacji Gaussa. Mamy | V | równania liniowe w | E | nieznane. Zwykle | E | > | V | , więc nie będziemy mieć wystarczającej liczby równań, aby jednoznacznie określić nieznane. Czy przeoczam jakiś podstęp? fa|V.||mi||mi|>|V.|
DW
Nie jestem też ekspertem w tej dziedzinie, więc mogę się mylić. Ale fakt, że nie ma unikalnego rozwiązania, wydaje się to ułatwiać. Jeśli zredukujesz go do postaci zredukowanego rzutu, masz niezależne kolumny. Wtedy unikalne rozwiązanie tej submatrix ib , w połączeniu z zerowym przepływem dla wszystkich pozostałych kolumn, dałoby nie unikalne rozwiązanie, co samo w sobie nie stanowi problemu. Problem, który mogę przewidzieć, polega na tym, że f narusza ograniczenia pojemności, ale intuicyjnie powiedziałbym, że istnieje sposób na bezpośrednie obejście tego|V.|bfa
Thomas Bosman,
Af=b
Cholera, to prawda. Możesz dodać ograniczenia (górne i dolne), o których wiesz, że ma rozwiązanie, ale wtedy masz | V | +2 | E | wiersze, aby był wolniejszy niż bezpośrednie obliczenie maksymalnego przepływu.
Thomas Bosman,
Innym problemem jest to, że ograniczenia pojemności są nierównościami (a nie równościami), więc nie można użyć eliminacji Gaussa: trzeba użyć programowania liniowego, co, jak mówisz, nie wydaje się być szybsze niż tylko obliczenie maksymalny przepływ bezpośrednio.
DW