Algorytm Karger'a losowy minimalnego podziału

Co to jest podział i dlaczego najmniejszy ma znaczenie

Podziałem niekierowanego grafu nazywamy dowolne podzielenie jego wierzchołków na dwa niepuste grupy. Krawędzie, które mają końce w różnych grupach, są powialinkowane przez ten podział i usuwanie ich rozdziela graf na te dwie części. Rozmiar podziału to prosto liczba krawędzi powialinkowanych (lub cała masa, jeśli mówimy o grafie ważonym). Jako że problem najmniejszego globalnego podziału nie definiuje wczesniej źródła ani ujścia jak w klasycznym problemie minimalnego s-t podziału z teorii przepływów, pyta on o bardziej ogólne pytanie: wśród wszystkich możliwych sposobów podzielenia wierzchołków na dwie grupy, który podział ma najmniejszą liczbę powialinkowanych krawędzi? Ta różnica ma niezwykle duży wpływ na sposób rozwiązania problemu. Algorytmy typu maksymalnego przepływu minimalny podział, takie jak Ford-Fulkerson lub metody push-relabel, są oparte na ustalonej parze źródła i ujścia i muszą być uruchamiane dla każdej pary wierzchołków, lub co najmniej dla n minus jednej dokładnie wybranej pary, aby znaleźć prawdziwy globalny minimum. Algorytm Karger'a unika potrzeby ustalonego źródła ani ujścia. Traktuje graf symetrycznie i pozwala losowościowi eksplorować przestrzeń możliwych podziałów bezpośrednio. Dlaczego warto się martwić o najmniejszy globalny podział? Znajduje on zastosowanie jako miara odporności sieci: rozmiar najmniejszego podziału mówi, ile najmniejszych połączeń musi zacząć działać lub być atakowane, aby rozdzielić sieć komunikacyjną, siatkę elektryczną czy graf społeczny na niezwiązane komponenty. Mały rozmiar podziału oznacza słabej zapewniający brzeg; duży rozmiar sugeruje dobrze połączoną, odporną strukturę. Znajduje on również zastosowanie w grupowaniu i segmentacji obrazów, gdzie mały podział często odpowiada naturalnej granicy między dwiema gęstymi społecznościami wierzchołków.

Krok po kroku procedury kontrakcji

Algorytm Karger'a działa na wielokrawędziowym grafie, dlatego musi tolerować krawędzie paralelne między tymi samymi wierzchołkami, ponieważ proces kontrakcji naturalnie tworzy je. Procedura jest zintegrowana i minimalna. Na początku, dopóki pozostaje więcej niż dwa wierzchołki, wybieramy jedno krawędź losowo z wszystkich obecnych krawędzi, w tym paralelnych kopii. Drugim krokiem jest kontrakcja wybranej krawędzi: łączenie jej dwóch końcowych wierzchołków w pojedynczy nowy węzeł połączony. Każda krawędź, która dotyka wcześniej jednego z tych wierzchołków, teraz dotyka nowego połączonego węzła, co oznacza, że te krawędzie przeżywają jako paralelne, a nie są usuwane. Trzecim krokiem jest usunięcie wszystkich pętli wynikających z kontrakcji, czyli krawędzi, które teraz łączą połączony węzeł ze sobą, ponieważ pętle nigdy nie mogą być częścią podziału oddzielającego dwa pozostające superwierzchołki. Powtarzamy ten cykl wybierania i kontrakcji aż zostaną dokładnie dwa superwierzchołki. Wszystkie krawędzie, które nadal łączą te końcowe dwa superwierzchołki, wszystkie paralelne wynikające z procesu kontrakcji, tworzą wyjściowy podział algorytmu. Zauważ something crucial: wybieranie krawędzi losowo z aktualnej mulitzbiór krawędzi nie jest tym samym co wybieranie losowo między oryginalnymi parami wierzchołków. Wierzchołki, które przyjęły wiele kontrakcji i mają więc wysoki stopień, są bardziej prawdopodobne do wybrania na kolejny krok, ponieważ przyczyniają się do większej liczby paralelnych krawędzi w puli. Ta losowość ważona stopniem nie jest przypadkiem ani blem; to dokładnie mechanizm, który sprawia, że analiza prawdopodobieństwa działa korzystnie dla zachowania małych podziałów, ponieważ krawędzie należące do małego minimalnego podziału tworzą porównywalnie niewielką część ogólnej puli krawędzi na każdym etapie, szczególnie wczesnym, gdy graf nadal jest duży i bogato łączony.

Dlaczego pojedyncze wykonanie może nie powiedzieć się, i dlaczego to zwykle nie dzieje się

Jeśli prawdziwe globalne minimum cut ma dokładnie k przekraczających krawędzi, algorytm po jednym wykonaniu nie znajdzie tego exact cut dokładnie wtedy, gdy podczas sekwencji kompresji pewna z tych k specjalnych krawędzi zostanie przypadkowo wybrana i spakowana. Spakowywanie krawędzi minimum cut łączy dwie wierzchołki, które prawdziwe minimum cut zamierza pozostawić na przeciwległych stronach, co trwale zniszcza możliwość odzyskania tego konkretnego cuta w późniejszej fazie wykonania. Cała kwestia sukcesu czy niepowodzenia sprowadza się więc do: jakie jest prawdopodobieństwo, że wszystkie kroki kompresji unikną wszystkich tych k krawędzi minimum cut? Oto kluczowa strukturalna fakt, który pozwala na analizę: jeśli globalne minimum cut ma rozmiar k, to każdy wierzchołek grafu musi mieć stopień co najmniej k. Dlaczego? Ponieważ izolujący tylko ten jeden wierzchołek od wszystkiego innego jest również prawidłowym cutem, jego rozmiar, czyli stopień tego wierzchołka, nie może być mniejszy niż globalne minimum, czyli k nie mogłoby być prawdziwym minimum. Ponieważ każdy wierzchołek ma stopień co najmniej k, graf o n wierzchołkach musi mieć co najmniej nk/2 krawędzi w sumie, zgodnie z relacją patszyfrowania między stopniem a liczbą krawędzi. To oznacza, że na każdym etapie, gdy pozostaje m wierzchołków, graf obecny ma co najmniej mk/2 krawędzi, podczas gdy tylko k z nich należy do śledzonego cutu. Zatem szansa, że losowo wybrana krawędź trafia na jedną z tych k niebezpiecznych krawędzi, wynosi co najwyżej k podzielone przez mk/2, które proste się uproszcza do 2/m. Ta granica zachodzi na każdym etapie kompresji, a mnożenie prawdopodobieństw przeżycia po wszystkich etapach od n wierzchołków do 2 powoduje znane wyniki, że pojedyncze wykonanie zakończy się sukcesem z prawdopodobieństwem co najmniej 2 podzielone przez n razy n minus jeden, które jest około 2 podzielone przez n kwadrat.

Algorytmy Monte Carlo: Trading Certyfikacji za Prostotę i Szybkość

Algorytm Karger jest klasyksem algorytmów Monte Carlo, czyli zmiennych losowych, które zawsze działają w ograniczonym czasie, ale są tylko gwarantowane na podanie poprawnej odpowiedzi z pewnym prawdopodobieństwem. W przeciwieństwie do algorytmów Las Vegas, które zawsze dają poprawną odpowiedź, ale mają losowy czas wykonania. Jest to istotnie inny kontrakt niż ten, który oferują algorytmy deterministyczne. Algorytm deterministyczny minimalnego podziału, na przykład oparty na powtarzanych obliczeniach maksymalnej przepływności, zawsze na każdym uruchomieniu wydaje dokładną poprawną odpowiedź bez wyjątków. Algorytm Karger nie daje takiej gwarancji dla żadnego pojedynczego uruchomienia; prawdopodobieństwo sukcesu około 2 podzielone przez n do kwadratu oznacza, że na grafie z kilkudziesięcioma wierzchołkami pojedyncze uruchomienie rzeczywiście jest prawie pewne, że zwróci podział większy niż prawdziwy minimum. To, co sprawia, że ta transakcja jest akceptowalna, nawet atrakcyjna, to to, że zdarzenia niepowodzenia po wielu niezależnych powtórzeniach są samodzielne, ponieważ każda próba odświeża swoje własne losowe wybory od nowa. Wykonanie całego procesu kontrakcji T razy niezależnie i zachowanie najmniejszego podziału znalezionego po wszystkich tych próbach zakończy się tylko wtedy, gdy każda z tych T prób się nie powiedzie, a ponieważ prawdopodobieństwo niepowodzenia na pojedynczym uruchomieniu jest co najwyżej 1 minus 2 podzielone przez n do kwadratu, prawdopodobieństwo, że wszystkie T próby zakończą się niepowodzeniem jednocześnie, zmniejsza się około jak e podniesione do potęgi minus 2T podzielone przez n do kwadratu. Wybieranie T proporcjonalne do n do kwadratu razy logarytm n sprowadza ogólny poziom niepowodzeń poniżej jednego podzielonego przez n, lub jakikolwiek inny docelowy próbkę wielomianową, podczas gdy cała praca pozostaje wielomianowa w n. To jest kluczowe zaprzysłowie Monte Carlo: przyjmowanie ograniczonej, mierzonej szansy na błąd w zamian za algorytm, który jest znacznie prostszy do zdefiniowania, implementacji i rozważania niż jego odpowiedniki deterministyczne, a następnie eliminacja prawdopodobieństwa błędu prawie całkowicie przez powtarzanie tanich niezależnych prób i zachowanie najlepszego wyniku.

Czas wykonania i praktyczne ulepszenia

Każde pojedyncze złączenie może być realizowane efektywnie za pomocą struktury danych typu union-find, czyli zbioru rozłącznego, do śledzenia, które wierzchołki oryginalne zostały połączone w super-wierzchołek, co pozwala na wykonanie pojedynczego kroku złączenia w bliskiej do stałej amortyzowanej czasie. Całe złączenie n minus 2 razy zajmuje około O(m) czasu, gdzie m to liczba krawędzi, dominującym czynnikiem jest koszt skanowania i wybierania krawędzi. Powtarzanie całego procesu n kwadrat log n razy do osiągnięcia prawdopodobieństwa wysokiego poprawności prowadzi do oczekiwanej złożoności czasowej rzędu O(n kwadrat m log n), która, choć wielomianowa i zatem teoretycznie efektywna, może być wolna w praktyce na dużych grafach w porównaniu do specjalizowanych algorytmów deterministycznych, takich jak algorytm Stoer-Wagner dla minimalnej krawędziowej rozdzielczości, który znajduje dokładne rozwiązanie deterministycznie w czasie O(n m) plus O(n kwadrat log n), korzystając z zupełnie innej strategii połączenia wierzchołków na fazach bez żadnej losowości. To jest miejsce, gdzie piękne ulepszenie opracowane przez Davida Karger'a razem z Cliffordem Steinem znacznie poprawia sytuację. Ich podejście, często nazywane algorytmem rekurencyjnym złączenia, obserwuje, że wczesne złączenia, gdy graf jest duży, są bardzo bezpieczne, ponieważ prawdopodobieństwo przeżycia 2 over m pozostaje bliskie 1, podczas gdy późniejsze złączenia, gdy graf sięga do kilku wierzchołków, są zagrożone. Zamiast złączyć wszystko do dwóch wierzchołków w jednym przejściu i potem od nowa, ulepszony algorytm złącza do około n over pierwiastek z 2 wierzchołków, a następnie ramuje się do dwóch niezależnych prób rekurencyjnych z tego bezpiecznego stanu intermedyjnego, przyjmując lepszy z tych dwóch wyników. Ramowanie rekurencyjne zmniejsza ostateczny czas wykonania do O(n kwadrat log n) podczas zachowywania tej samej gwarancji prawdopodobieństwa wysokiego poprawności, ilustrując, jak idea Monte Carlo podstawowa może być warstwowana zintużystycznionym alokowaniem zasobów, gdy zrozumiesz dokładnie, gdzie skupia się ryzyko niepomyślnego wyniku.

Często zadawane pytania