Algorytm Kargera

Wykres i dwa jego przekroje. Linia przerywana w kolorze czerwonym to cięcie z trzema przecinającymi się krawędziami. Linia przerywana w kolorze zielonym jest minimalnym wycięciem tego wykresu, przecinającym tylko dwie krawędzie.

W informatyce i teorii grafów algorytm Kargera jest losowym algorytmem do obliczania minimalnego przekroju połączonego wykresu . Został wynaleziony przez Davida Kargera i po raz pierwszy opublikowany w 1993 roku.

Idea algorytmu opiera się na koncepcji $}$ krawędzi w grafie nieskierowanym $, mi$ $\ Displaystyle G =$ . Mówiąc nieformalnie, skurcz krawędzi łączy węzły $\$ v $displaystyle v}$ w jeden, zmniejszając całkowitą liczbę węzłów wykresu o jeden. Wszystkie inne krawędzie łączące albo ${\ displaystyle u}$ lub są „ponownie $”$ do scalonego węzła, skutecznie tworząc multigraf . Podstawowy algorytm Kargera iteracyjnie skraca losowo wybrane krawędzie, aż pozostaną tylko dwa węzły; te węzły reprezentują cięcie w oryginalnym wykresie. Powtarzając ten podstawowy algorytm wystarczającą liczbę razy, z dużym prawdopodobieństwem można znaleźć minimalne cięcie .

Globalny problem minimalnego cięcia

Cięcie ${\ Displaystyle (S, T)}$ $\ Displaystyle G = (V, E$ grafie nieskierowanym jest podziałem wierzchołków { $}$ na dwa niepuste, rozłączne zbiory ${\ Displaystyle S \ puchar T = V}$ . Zestaw przekrojów składa się z krawędzi ${\ Displaystyle \ {\ uv \ w E \ dwukropek u \ w S, v \ w T \, \}}$ między dwiema częściami. Rozmiar (lub waga ) przekroju w grafie nieważonym to liczność zestawu fragmentów, tj. liczba krawędzi między dwiema częściami ,

{\ Displaystyle w (S, T) = | \ {\, uv \ w E \ dwukropek u \ w S, v \ w T \, \} |\,.}

Jest ${\ Displaystyle 2 ^ {| V|}}$ sposoby wyboru dla każdego wierzchołka, czy należy on do ${\ displaystyle S}$ czy do ${\ displaystyle T}$ , ale dwa z tych wyborów sprawiają, że ${\ displaystyle S}$ lub ${\ displaystyle T}$ puste i nie powodują cięć. Wśród pozostałych opcji zamiana ról i $displaystyle$ $T}$ nie zmienia cięcia, więc każde cięcie jest liczone dwukrotnie; dlatego jest ${\ Displaystyle 2 ^ {| V | -1} -1}$ wyraźne cięcia. Problem minimalnego cięcia polega na znalezieniu wśród tych cięć cięcia o najmniejszym rozmiarze.

$.$ dodatnimi wagami krawędzi waga cięcia jest sumą wag krawędzi

{\ Displaystyle w (S, T) = \ suma _ {uv \ w E \ dwukropek u \ w S ,v\in T}w(uv)\,,}

co zgadza się z nieważoną definicją dla ${\ displaystyle w = 1}$ .

jest czasami nazywane „cięciem globalnym”, aby odróżnić je od $”$ $dla$ danej pary wierzchołków, które ma dodatkowy wymóg, aby $s \ w S}$ ${\$ i ${\ displaystyle t \ w T}$ . Każde $globalne$ cięcie jest cięciem dla pewnego $}$ $Displaystyle s, t$ . Zatem problem minimalnego cięcia można rozwiązać w $\ displaystyle$ wielomianowym , powtarzając wszystkie wybory i rozwiązując wynikowe minimum $in V }$ $}$ $\$ problem cięcia przy użyciu twierdzenia o maksymalnym przepływie i minimalnym przecięciu oraz wielomianowym algorytmie czasu dla maksymalnego przepływu , takim jak algorytm push-relabel , chociaż takie podejście nie jest optymalne. Lepsze algorytmy deterministyczne dla globalnego problemu minimalnego cięcia obejmują algorytm Stoera – Wagnera , którego czas działania wynosi ${\ Displaystyle O (mn + n ^ {2} \ log n)}$ .

Algorytm skurczu

Podstawowym działaniem algorytmu Kargera jest forma skrócenia krawędzi . Wynikiem skurczenia krawędzi ${\ displaystyle e = \ {u, v \$ nowy węzeł $}$ . każda krawędź ${\ Displaystyle \ {w, u \}}$ lub ${\ Displaystyle \ {w, v \}}$ dla $\}} do$ $u ,$ końcowych skurczonej krawędzi zostaje zastąpione krawędzią nowego węzła Na koniec skurczone węzły $.$ wszystkie ich incydentalne krawędzie $usuwane$ W szczególności wynikowy wykres nie zawiera pętli własnych. Wynik kurczącej się krawędzi $displaystyle$ oznaczony $}$ .

Algorytm skracania wielokrotnie kurczy losowe krawędzie grafu, aż pozostaną tylko dwa węzły, w którym to momencie następuje tylko jedno cięcie.

Kluczową ideą algorytmu jest to, że znacznie bardziej prawdopodobne jest losowe wybranie krawędzi innych niż minimalne niż krawędzie minimalne i utracone w wyniku skurczu, ponieważ krawędzie minimalne są zwykle znacznie przewyższane liczebnie przez krawędzie inne niż minimalne. Następnie jest prawdopodobne, że krawędzie minimalnego cięcia przetrwają całe skrócenie krawędzi, a algorytm poprawnie zidentyfikuje krawędź minimalnego cięcia.

Udane uruchomienie algorytmu Kargera na grafie 10-wierzchołkowym. Minimalny krój ma rozmiar 3.

    
    proceduralny  (  ${\ Displaystyle G = (V, E)}$  ):  podczas gdy  ${$  $}$  \  Displaystyle  $leftarrow$  e  jedyne cięcie w  $G}$  ${\$

Gdy wykres jest reprezentowany za pomocą list sąsiedztwa lub macierzy sąsiedztwa , można zaimplementować operację skrócenia pojedynczej krawędzi z liniową liczbą aktualizacji struktury danych przez całkowity czas działania ${\ Displaystyle O ( |V|^{2})}$ . Alternatywnie procedurę można postrzegać jako wykonanie algorytmu Kruskala do konstruowania minimalnego drzewa rozpinającego na grafie, w którym krawędzie mają wagi ${\ Displaystyle w (e_ {i}) = \ pi (i)}$ zgodnie z losową permutacją ${\ Displaystyle \ pi}$ . Usunięcie najcięższej krawędzi tego drzewa daje w wyniku dwie składowe opisujące cięcie. W ten sposób procedurę skracania można zaimplementować jak algorytm Kruskala w czasie ${\ Displaystyle O (| E | \ log | E |)}$ .

Losowe wybory krawędzi w algorytmie Kargera odpowiadają wykonaniu algorytmu Kruskala na grafie z losowymi rangami krawędzi, aż pozostaną tylko dwa składniki.

Najbardziej znane implementacje wykorzystują $Displaystyle O (| E | \ log |$ $O$ lub czas i przestrzeń ${\ Displaystyle O (| V |)}$ .

Prawdopodobieństwo sukcesu algorytmu kontrakcji

Na $_$ _ ${\ Displaystyle n = | V|}$ wierzchołków, algorytm skracania zwraca minimalne cięcie z wielomianowo małym prawdopodobieństwem ${\ Displaystyle {\ binom {n} {2}} ^ {- 1}}$ . Każdy wykres $($ najwyżej ${\ Displaystyle {\ tbinom {n} {2}}}$ mogą być minimalnymi cięciami. Dlatego prawdopodobieństwo sukcesu tego algorytmu jest znacznie większe niż prawdopodobieństwo losowego wybrania cięcia, które wynosi najwyżej ${\ Displaystyle {\ tbinom {n} {2} }/(2^{n-1}-1)}$ .

$Na$ przykład wykres cyklu na $wybór$ ma dokładnie 2 krawędzi Procedura kontrakcji znajduje każdą z nich z równym prawdopodobieństwem.

$dolną$ granicę prawdopodobieństwa sukcesu, niech oznaczą krawędzie określonego minimalnego cięcia $o$ . Algorytm skracania zwraca $displaystyle C}$ jeśli żadna z losowych krawędzi nie należy do zestawu cięć z do ${$ . szczególności skrócenie pierwszej krawędzi pozwala uniknąć $k$ co dzieje się z prawdopodobieństwem ${\ Displaystyle 1-k / | E |}$ . Minimalny stopień wynosi $wierzchołek$ najmniej (w przeciwnym razie minimalnego stopnia wywołałby mniejsze cięcie, w którym jedna z dwóch partycji zawiera tylko wierzchołek minimalnego stopnia) $,$ ${\ Displaystyle | E | \ geqslant nk/2}$ . Zatem prawdopodobieństwo, że algorytm kontrakcji wybierze krawędź z, ${\ displaystyle C}$ do

{\ Displaystyle {\ Frac {k} {| E |}} \ leqslant {\ Frac {k} {nk / 2}} = {\ Frac {2} {n}}.}

Prawdopodobieństwo ${\ Displaystyle p_ {n} \ geqslant \ lewo (1- {\ Frac {2} {n}} \ prawej) p_ {n-1}}$ że algorytm kontrakcji na wykresie wierzchołków unika $\ displaystyle$ $}$ spełnia $p$ z ${\ Displaystyle p_ {2} = 1}$ , który można rozwinąć jako

{\ Displaystyle p_ {n} \ geqslant \ prod _ {i = 0} ^ {n-3} {\ Bigl (} 1- {\ Frac {2} {ni}} {\ Bigr)} = \ prod _ { i=0}^{n-3}{\frac {ni-2}{ni}}={\frac {n-2}{n}}\cdot {\frac {n-3}{n-1} }\cdot {\frac {n-4}{n-2}}\cdots {\frac {3}{5}}\cdot {\frac {2}{4}}\cdot {\frac {1}{ 3}}={\binom {n}{2}}^{-1}\,.}

Powtarzanie algorytmu skurczu

10 powtórzeń procedury skurczu. 5-te powtórzenie znajduje minimalny krój w rozmiarze 3.

Powtarzając algorytm skrócenia $zwracając najmniejsze$ prawdopodobieństwo Minimalne cięcie to

{\ Displaystyle \ lewo [1- {\ binom {n} {2}} ^ {- 1} \ prawo] ^ {T} \ równoważnik {\ Frac {1} {e ^ {\ ln n}}} = { \frac {1}{n}}\,.}

Całkowity czas pracy dla $\ Displaystyle O(Tm)=O(n^{2}m\log n)}$ $wykresu$ wierzchołkami ${$ krawędziami $)$ O .

Algorytm Kargera-Steina

Rozszerzenie algorytmu Kargera dzięki Davidowi Kargerowi i Cliffordowi Steinowi zapewnia poprawę o rząd wielkości.

Podstawową ideą jest wykonywanie procedury skracania, aż wykres $osiągnie$ .

    
     procedura  (  ${\ Displaystyle G = (V, E)}$  ,  ${\ Displaystyle t}$  ):  podczas  ${\ Displaystyle | V|> t}$  wybierz  ${\ Displaystyle e \ in E}$  $mi {\ Displaystyle G \ leftarrow G / e}$  losowo  powrót  ${\ Displaystyle G}$

Prawdopodobieństwo $}$ określonego cięcia wykresie wierzchołków, wynosi ${\ displaystyle p_ {n,$ $t$

${\ Displaystyle p_ {n, t} \ geq \ prod _ {i = 0} ^ {nt-1} {\ Bigl (} 1- {\ Frac {2} {ni}}} {\ Bigr)} = {\ binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.}$

${2}}$ wyrażenie jest w przybliżeniu staje się mniejsze niż wokół ${2}/n ^$ ${\ displaystyle t = n / {\ sqrt {2}}}$ t . W szczególności prawdopodobieństwo, że krawędź $skrócona,$ pod koniec. Motywuje to pomysł przejścia na wolniejszy algorytm po określonej liczbie kroków skurczu.

    
        procedura  fastmincut (  ${\ Displaystyle G = (V, E)}$  ):  jeśli  ${\ Displaystyle | V | \ równoważnik 6}$  :  return  mincut (  ${\ Displaystyle V}$  )  inaczej  :  ${\ Displaystyle t \ strzałka w lewo \ lceil 1 + | V |/ {\ sqrt {2}} \ rceil}$  ${\ Displaystyle G_ {1} \ strzałka w lewo}$  umowa (  ${\ Displaystyle G}$  ,  ${\ Displaystyle t}$  )  ${\ Displaystyle G_ {2} \ strzałka w lewo}$  umowa (  ${\ Displaystyle G}$  ,  ${\ Displaystyle t}$  )  powrót  min {fastmincut (  ${\ Displaystyle G_ {1}}$  ), fastmincut (  ${\ Displaystyle G_ {2}}$  )}

Analiza

Prawdopodobieństwo, że algorytm znajdzie określony zbiór cięć, ${\ Displaystyle P (n)$ określone przez relację powtarzania się $}$

{\ Displaystyle P (n) = 1- \ lewo (1 - {\ Frac {1} {2}} P \ left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil}\right)\right)^{2}}

z rozwiązaniem ${\ Displaystyle P (n) = \ Omega \ lewo ({\ Frac {1} {\ log n}} \ prawej)}$ . Czas działania fastmincut jest zadowalający

{\ Displaystyle T (n) = 2 T \ lewo ({\ Bigl \ lceil} 1 + {\ Frac {n} {\ sqrt {2}}}{\Bigr \rceil }\right)+O(n^{2})}

z rozwiązaniem ${\ Displaystyle T (n) = O (n ^ {2} \ log n)}$ . Aby osiągnąć prawdopodobieństwo błędu $(\ log n / P (n) )}$ $)$ powtórzyć razy, co daje całkowity czas działania ${\ Displaystyle T (n) \ cdot {\ Frac {\ log n} {P (n)}} = O (n ^ {2}\log ^{3}n)}$ . Jest to poprawa o rząd wielkości w stosunku do oryginalnego algorytmu Kargera.

Ograniczenie poprawy

$.$ każdej krawędzi wykresu, czyli na gęstym wykresie Algorytm min-cut Kargera-Steina przyjmuje czas działania , czyli $n ^ {2} \ ln ^ {O (1)} n)}$ ( bardzo blisko tego.

^ ^a ^b Karger, David (1993). „Globalne minimalne cięcia w RNC i inne konsekwencje prostego algorytmu Mincut” . proc. 4. doroczne sympozjum ACM-SIAM na temat algorytmów dyskretnych .
Bibliografia _ Wagnera, F. (1997). „Prosty algorytm min-cut” . Dziennik ACM . 44 (4): 585. doi : 10.1145/263867.263872 . S2CID 15220291 .
^ Patrignani, Maurizio; Pizzonia, Maurizio (2001), „Złożoność problemu dopasowania dopasowania”, w: Brandstädt, Andreas ; Le, Van Bang (red.), Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Niemcy, 14-16 czerwca 2001, Proceedings , Lecture Notes in Computer Science, tom. 2204, Berlin: Springer, s. 284–295, doi : 10.1007/3-540-45477-2_26 , MR 1905640 .
^ Karger, David R .; Stein, Clifford (1996). „Nowe podejście do problemu minimalnego cięcia” (PDF) . Dziennik ACM . 43 (4): 601. doi : 10.1145/234533.234534 . S2CID 5385337 .

[karger1993-1] Karger, David (1993). „Globalne minimalne cięcia w RNC i inne konsekwencje prostego algorytmu Mincut” . proc. 4. doroczne sympozjum ACM-SIAM na temat algorytmów dyskretnych .

[simplemincut-2] Bibliografia _ Wagnera, F. (1997). „Prosty algorytm min-cut” . Dziennik ACM . 44 (4): 585. doi : 10.1145/263867.263872 . S2CID 15220291 .

[3] Patrignani, Maurizio; Pizzonia, Maurizio (2001), „Złożoność problemu dopasowania dopasowania”, w: Brandstädt, Andreas ; Le, Van Bang (red.), Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Niemcy, 14-16 czerwca 2001, Proceedings , Lecture Notes in Computer Science, tom. 2204, Berlin: Springer, s. 284–295, doi : 10.1007/3-540-45477-2_26 , MR 1905640 .

[faster-4] Karger, David R .; Stein, Clifford (1996). „Nowe podejście do problemu minimalnego cięcia” (PDF) . Dziennik ACM . 43 (4): 601. doi : 10.1145/234533.234534 . S2CID 5385337 .