Maksymalny niezależny zestaw

Ten artykuł dotyczy kombinatorycznych aspektów maksymalnych niezależnych zbiorów wierzchołków w grafie. Aby zapoznać się z innymi aspektami niezależnych zbiorów wierzchołków w teorii grafów, zobacz Niezależny zbiór (teoria grafów) . Aby zapoznać się z innymi rodzajami zestawów niezależnych, zobacz Zestaw niezależny (ujednoznacznienie) .

Wykres sześcianu ma sześć różnych maksymalnych niezależnych zbiorów (dwa z nich są maksymalne), pokazanych jako czerwone wierzchołki.

W teorii grafów maksymalny zbiór niezależny ( MIS ) lub maksymalny zbiór stabilny jest zbiorem niezależnym , który nie jest podzbiorem żadnego innego zbioru niezależnego. Innymi słowy, poza niezależnym zbiorem nie ma wierzchołka , który mógłby do niego dołączyć, ponieważ jest on maksymalny w odniesieniu do własności niezależnego zbioru.

Na przykład w grafie P ₃ , ścieżce z trzema wierzchołkami a , b i c oraz dwoma krawędziami ab i bc , zbiory { b } i { a , c } są maksymalnie niezależne. Zbiór { a } jest niezależny, ale nie jest maksymalnie niezależny, ponieważ jest podzbiorem większego zbioru niezależnego { a , c }. Na tym samym wykresie maksymalne kliki to zbiory { a , b } i { b , c }.

MIS jest również dominującym zbiorem na grafie, a każdy dominujący zestaw, który jest niezależny, musi być maksymalnie niezależny, więc MIS są również nazywane niezależnymi zbiorami dominującymi .

Dwa górne wykresy P ₃ to maksymalne niezależne zbiory, podczas gdy dwa dolne to niezależne zbiory, ale nie maksymalne. Maksymalny niezależny zestaw jest reprezentowany przez lewy górny róg.

Wykres może zawierać wiele MIS o bardzo różnych rozmiarach; największy lub kilka równie dużych MIS grafu nazywamy maksymalnym niezależnym zbiorem . Grafy, w których wszystkie maksymalne zbiory niezależne mają ten sam rozmiar, nazywamy grafami dobrze pokrytymi .

Wyrażenie „maksymalny zbiór niezależny” jest również używane do opisania maksymalnych podzbiorów niezależnych elementów w strukturach matematycznych innych niż grafy, aw szczególności w przestrzeniach wektorowych i matroidach .

Dwa niezależne zbiory wykresu gwiazdy S ₈ pokazują, jak bardzo różne mogą być dwa maksymalne niezależne zbiory (po prawej stronie maksimum).

Z MIS wiążą się dwa problemy algorytmiczne : znalezienie pojedynczego MIS na danym grafie i zestawienie wszystkich MIS na danym grafie .

Definicja

Dla wykresu $( V , mi ) {\ Displaystyle G =$ zbiór maksymalnym niezależnym zbiorem , jeśli dla $\ Displaystyle v \ in V }$${$ sol } jedno z poniższych zdań jest prawdziwe:

1. ${\ Displaystyle v \ w S}$
2. ${\ Displaystyle N (v) \ czapka S \ neq \ pusty zbiór}$ gdzie ${\ Displaystyle N (v)}$ oznacza sąsiadów ${\ displaystyle v}$

Powyższe można powtórzyć, ponieważ wierzchołek albo należy do zbioru niezależnego, albo ma co najmniej jeden sąsiedni wierzchołek należący do zbioru niezależnego. W rezultacie każda krawędź wykresu ma co najmniej jeden punkt końcowy inny $niż$ . Jednak nie jest prawdą, że każda krawędź wykresu ma co najmniej jeden, a nawet jeden punkt końcowy w ${\ displaystyle S}$

Zauważ, że żaden sąsiad wierzchołka w niezależnym zbiorze $nie$ może znajdować się w $te$ wierzchołki są rozłączne według definicji zbioru niezależnego.

Powiązane zestawy wierzchołków

Jeśli S jest maksymalnym niezależnym zbiorem na pewnym grafie, to jest to maksymalna klika lub maksymalny pełny podgraf w grafie dopełniającym . Klika maksymalna to zbiór wierzchołków, który indukuje pełny podgraf i nie jest podzbiorem wierzchołków żadnego większego pełnego podgrafu. Oznacza to, że jest to zbiór S taki, że każda para wierzchołków w S jest połączona krawędzią i każdemu wierzchołkowi spoza S brakuje krawędzi do co najmniej jednego wierzchołka w S . Wykres może mieć wiele maksymalnych klik o różnych rozmiarach; znalezienie największego z nich jest problemem największej kliki .

Niektórzy autorzy włączają maksymalność jako część definicji kliki i określają maksymalne kliki po prostu jako kliki.

Lewy to maksymalny niezależny zbiór. $.$ klika, na dopełnieniu wykresu Prawo to pokrycie wierzchołków na maksymalnym niezależnym dopełnieniu zbioru.

Dopełnienie maksymalnego zbioru niezależnego, czyli zbioru wierzchołków nienależących do zbioru niezależnego, tworzy minimalne pokrycie wierzchołków . Oznacza to, że dopełnienie jest pokryciem wierzchołków , zbiorem wierzchołków, który zawiera co najmniej jeden punkt końcowy każdej krawędzi i jest minimalny w tym sensie, że żaden z jego wierzchołków nie może zostać usunięty przy zachowaniu właściwości, że jest pokryciem. Minimalne pokrycie wierzchołków badano w mechanice statystycznej w połączeniu z modelem gazu sieciowego twardej kuli , matematyczną abstrakcją przejść płyn-ciało stałe.

Każdy maksymalny niezależny zbiór jest zbiorem dominującym , zbiorem wierzchołków takim, że każdy wierzchołek w grafie albo należy do zbioru, albo do niego przylega. Zbiór wierzchołków jest maksymalnym zbiorem niezależnym wtedy i tylko wtedy, gdy jest niezależnym zbiorem dominującym.

Charakteryzacje rodziny wykresów

Niektóre rodziny grafów zostały również scharakteryzowane pod względem ich maksymalnych klik lub maksymalnych niezależnych zbiorów. Przykłady obejmują nieredukowalne grafy maksymalnej kliki i dziedziczne nieredukowalne grafy maksymalnej kliki. Mówimy, że graf jest nieredukowalny dla kliki maksymalnej , jeśli każda klika maksymalna ma krawędź, która nie należy do żadnej innej kliki maksymalnej, a graf dziedziczny dla kliki maksymalnej jest nieredukowalny, jeśli ta sama właściwość jest prawdziwa dla każdego indukowanego podgrafu. Dziedziczne grafy nieredukowalne kliki maksymalnej obejmują grafy bez trójkątów , grafy dwudzielne i grafy interwałowe .

Kografy można scharakteryzować jako grafy, w których każda maksymalna klika przecina każdy maksymalny niezależny zbiór i w których ta sama właściwość jest prawdziwa we wszystkich indukowanych podgrafach.

Ograniczenie liczby zestawów

Moon i Moser (1965) wykazali, że dowolny graf z n wierzchołkami ma co najwyżej 3 ^{n /3} maksymalnych klik. Dodatkowo każdy graf z n wierzchołkami ma również co najwyżej 3 ^{n /3} maksymalnych niezależnych zbiorów. Graf z dokładnie 3 ^{n /3} maksymalnymi niezależnymi zbiorami jest łatwy do skonstruowania: wystarczy wziąć rozłączną sumę n /3 grafów trójkątnych . Każdy maksymalny niezależny zbiór w tym grafie jest tworzony przez wybranie jednego wierzchołka z każdego trójkąta. Wykres uzupełniający, z dokładnie 3 ^{n /3} maksymalnych klik, jest szczególnym rodzajem grafu Turána ; ze względu na ich związek z wiązaniem Księżyca i Mosera, wykresy te są czasami nazywane wykresami Księżyca-Mosera. Węższe granice są możliwe, jeśli ograniczy się rozmiar maksymalnych niezależnych zestawów: liczba maksymalnych niezależnych zestawów o rozmiarze k w dowolnym grafie n -wierzchołków wynosi co najwyżej

${\ Displaystyle \ lfloor n/k \ rfloor ^ {k- (n {\ bmod {k}})} \ lfloor n/k + 1 \ rfloor ^ {n {\ bmod {k}}}.}$

Grafy osiągające tę granicę są ponownie grafami Turána.

Niektóre rodziny grafów mogą jednak mieć znacznie bardziej restrykcyjne ograniczenia dotyczące liczby maksymalnych niezależnych zbiorów lub maksymalnych klik. Jeśli wszystkie n -wierzchołkowe grafy w rodzinie grafów mają O( n ) krawędzi i jeśli każdy podgraf w rodzinie również należy do tej rodziny, to każdy graf w rodzinie może mieć co najwyżej O( n ) maksymalnych klik , z których wszystkie mają rozmiar O(1). Na przykład te warunki są prawdziwe dla grafów planarnych : każdy graf planarny n -wierzchołkowy ma co najwyżej 3 n − 6 krawędzi, a podwykres grafu planarnego jest zawsze planarny, z czego wynika, że ​​każdy graf planarny ma O( n ) maksymalnych klik (o wielkości co najwyżej czterech). Grafy interwałowe i grafy akordowe również mają co najwyżej n maksymalnych klik, mimo że nie zawsze są to grafy rzadkie .

Liczba maksymalnych niezależnych zbiorów w n -wierzchołkowych grafach cyklicznych jest określona przez liczby Perrina , a liczba maksymalnych niezależnych zbiorów w n -wierzchołkowych grafach ścieżkowych jest określona przez sekwencję Padovana . Dlatego obie liczby są proporcjonalne do potęg 1,324718, liczby plastycznej .

Znalezienie pojedynczego maksymalnego niezależnego zestawu

Algorytm sekwencyjny

Mając wykres G(V,E), łatwo jest znaleźć pojedynczy MIS przy użyciu następującego algorytmu:

1. Zainicjuj I do pustego zestawu.
2. Podczas gdy V nie jest puste:
   • Wybierz węzeł v∈V;
   • Dodaj v do zbioru I;
   • Usuń z V węzeł v i wszystkich jego sąsiadów.
3. Powrót I.

Czas wykonania wynosi O( m ), ponieważ w najgorszym przypadku musimy sprawdzić wszystkie krawędzie.

O(m) to oczywiście najlepszy możliwy czas działania algorytmu szeregowego. Ale algorytm równoległy może rozwiązać problem znacznie szybciej.

Algorytm równoległy losowego wyboru [algorytm Luby'ego]

Poniższy algorytm znajduje MIS w czasie O(log n ).

1. Zainicjuj I do pustego zestawu.
2. Podczas gdy V nie jest puste:
   • Wybierz losowy zbiór wierzchołków S ⊆ V, wybierając każdy wierzchołek v niezależnie z prawdopodobieństwem 1/(2d(v)), gdzie d jest stopniem v (liczbą sąsiadów v).
   • Dla każdej krawędzi w E, jeśli oba jej punkty końcowe znajdują się w losowym zbiorze S, usuń z S punkt końcowy, którego stopień jest niższy (tj. ma mniej sąsiadów). Rozdzielaj powiązania dowolnie, np. używając porządku leksykograficznego nazw wierzchołków.
   • Dodaj zestaw S do I.
   • Usuń z V zbiór S i wszystkich sąsiadów węzłów w S.
3. Powrót I.

ANALIZA : Dla każdego węzła v podziel jego sąsiadów na niższych sąsiadów (których stopień jest niższy niż stopień v) i wyższych sąsiadów (których stopień jest wyższy niż stopień v), zrywając więzi jak w algorytmie.

Nazwij węzeł v złym , jeśli więcej niż 2/3 jego sąsiadów jest wyższymi sąsiadami. Nazwij krawędź złą , jeśli oba jej punkty końcowe są złe; w przeciwnym razie krawędź jest dobra .

• Przynajmniej 1/2 wszystkich krawędzi jest zawsze dobra. DOWÓD: Zbuduj skierowaną wersję G, kierując każdą krawędź do węzła o wyższym stopniu (dowolne zerwanie wiązań). Tak więc dla każdego złego węzła liczba krawędzi wychodzących jest ponad 2 razy większa niż liczba krawędzi przychodzących. Tak więc każda zła krawędź, która wchodzi do węzła v, może być dopasowana do odrębnego zestawu dwóch krawędzi wychodzących z węzła v. Stąd całkowita liczba krawędzi jest co najmniej 2 razy większa niż liczba złych krawędzi.
• Dla każdego dobrego węzła u prawdopodobieństwo, że sąsiad u zostanie wybrany do S, jest co najmniej pewną stałą dodatnią. DOWÓD: prawdopodobieństwo, że żaden sąsiad u nie zostanie wybrany do S, jest co najwyżej prawdopodobieństwem, że żaden z niższych sąsiadów u nie zostanie wybrany. Dla każdego niższego sąsiada v prawdopodobieństwo, że nie zostanie on wybrany wynosi (1-1/2d(v)), co najwyżej (1-1/2d(u)) (ponieważ d(u)>d(v) )). Liczba takich sąsiadów wynosi co najmniej d(u)/3, ponieważ u jest dobre. Stąd prawdopodobieństwo, że żaden niższy sąsiad nie zostanie wybrany, wynosi co najwyżej 1-exp(-1/6).
• Dla każdego węzła u wybranego do S prawdopodobieństwo, że u zostanie usunięte z S, wynosi co najwyżej 1/2. DOWÓD: To prawdopodobieństwo jest co najwyżej prawdopodobieństwem, że wyższy sąsiad u zostanie wybrany do S. Dla każdego wyższego sąsiada v prawdopodobieństwo, że zostanie wybrany, wynosi co najwyżej 1/2d(v), czyli co najwyżej 1/ 2d(u) (ponieważ d(v)>d(u)). Prawdopodobieństwo, że nie zostanie wybrany żaden wyższy sąsiad, wynosi co najwyżej d(u)/2d(u) = 1/2.
• Stąd dla każdego dobrego węzła u prawdopodobieństwo, że sąsiad u zostanie wybrany do S i pozostanie w S, jest pewną dodatnią stałą. Stąd prawdopodobieństwo, że u zostanie usunięte w każdym kroku, jest co najmniej stałą dodatnią.
• Stąd dla każdej dobrej krawędzi e prawdopodobieństwo, że e zostanie usunięte w każdym kroku, jest co najmniej dodatnią stałą. Tak więc liczba dobrych krawędzi spada co najmniej o stały czynnik w każdym kroku.
• Ponieważ co najmniej połowa krawędzi jest dobra, całkowita liczba krawędzi również spada o stały czynnik w każdym kroku.
• Stąd liczba kroków wynosi O(log m ), gdzie m to liczba krawędzi. Jest to ograniczone przez ${\ Displaystyle O (\ log (n))}$ .

Θ $n))}$ , to wykres złożony z n /2 połączonych elementów, każdy z 2 węzły. Stopień wszystkich węzłów wynosi 1, więc każdy węzeł jest wybierany z prawdopodobieństwem 1/2, a z prawdopodobieństwem 1/4 oba węzły w komponencie nie są wybierane. W związku z tym liczba węzłów spada czterokrotnie na każdy krok, a oczekiwana liczba kroków to ${\ Displaystyle \ log _ {4} (n)}$ .

Algorytm równoległy o losowym priorytecie

Poniższy algorytm jest lepszy od poprzedniego, ponieważ w każdym podłączonym komponencie zawsze dodawany jest co najmniej jeden nowy węzeł:

1. Zainicjuj I do pustego zestawu.
2. Chociaż V nie jest puste, każdy węzeł v wykonuje następujące czynności:
   • Wybiera liczbę losową r(v) w [0,1] i wysyła ją do swoich sąsiadów;
   • Jeśli r(v) jest mniejsze niż liczba wszystkich sąsiadów v, to v wstawia się w I, usuwa się z V i mówi o tym swoim sąsiadom;
   • Jeśli v usłyszał, że jeden z jego sąsiadów dostał się do I, to v usuwa się z V.
3. Powrót I.

Zauważ, że w każdym kroku węzeł o najmniejszej liczbie w każdym połączonym komponencie zawsze wprowadza I, więc zawsze jest jakiś postęp. W szczególności, w najgorszym przypadku poprzedniego algorytmu ( n /2 połączonych komponentów z 2 węzłami każdy), MIS zostanie znaleziony w jednym kroku.

ANALIZA :

• Węzeł ma prawdopodobieństwo co najmniej ${d (v) + d (w)}}} v {\ displaystyle v$$}$$,$ : Dla każdej krawędzi łączącej parę węzłów skierowanymi krawędziami, jedną z $}$ w inne ${\ Displaystyle (w, v)}$ . Zauważ, że ${\ displaystyle | E |}$ jest teraz dwa razy większy. Dla $w \ rightarrow v)}$ pary skierowanych krawędzi zdefiniuj dwa zdarzenia: $v \ rightarrow w)}$$i$ → $($ , ${\ displaystyle v}$ zapobiegawczo usuwa ${\ displaystyle w}$$i$ zapobiegawczo usuwa odpowiednio $\ displaystyle v}$ . Zdarzenie ${\ Displaystyle (v \ rightarrow w)}$ występuje, gdy ${\ Displaystyle r (v) <r (w)}$ i ${\ Displaystyle r (v) <r (x)}$ gdzie $w}$$displaystyle$ jest sąsiadem i jest sąsiadem $displaystyle$$w$ . Przypomnijmy, że każdemu węzłowi jest przypisana losowa liczba z tego samego zakresu [0, 1]. $bycia$ z dwoma rozłącznymi węzłami każdy ma prawdopodobieństwo . Jeśli istnieją trzy rozłączne węzły, każdy z nich ma $prawdopodobieństwo$ . w przypadku ${\ Displaystyle v}$ , ma prawdopodobieństwo co najmniej ${\ Displaystyle {\ Frac {1} {d (v) + d (w)}}}$ bycia najmniejszym, ponieważ jest to możliwe że sąsiad $podwójnie$ również sąsiadem , więc węzeł jest $liczony$$Używając$ , zdarzenie ma co najmniej ${\ Displaystyle {\ Frac {1} {d (w) + d (v)}}}$ usunięcia.
• Kiedy zdarzenia i $\ Displaystyle (w \ rightarrow$${\ Displaystyle d (w)$$mają$ miejsce, usuwają i $_$ . DOWÓD: W przypadku ${\ Displaystyle (v \ rightarrow w)}$ , kiedy ${\ displaystyle v}$ jest usuwany, wszystkie sąsiednie węzły $są$ usuwane. Liczba wychodzących skierowanych krawędzi z usuniętych wynosi $Displaystyle d (w)}$$\$ . Z $.$$_$ usuwa _
• W każdej iteracji kroku 2, w oczekiwaniu, połowa krawędzi jest usuwana. $DOWÓD$$ma$ Jeśli zdarzenie to wszyscy są stąd oczekiwana liczba krawędzi usuniętych w wyniku tego zdarzenia wynosi co najmniej ${\ Displaystyle {\ Frac {d (w)}} {d (v) + d (w)} }}$ . To samo dotyczy zdarzenia odwrotnego ${\ Displaystyle (w \ rightarrow v)}$ , tj. oczekiwana liczba usuniętych krawędzi wynosi co najmniej ${\ Displaystyle {\ Frac {d (v)} {d(w)+d(v)}}}$ . Stąd dla każdej nieskierowanej krawędzi $liczba$ krawędzi usuniętych z powodu najmniejszej wartości jednego ${\ Displaystyle {\ Frac {d (w) + d (v)} {d (w) + d (v)}} = 1}$ . Sumując po wszystkich krawędziach, ${\ Displaystyle \ suma _ {{v, w} \ in E} 1 = | E |}$ daje oczekiwaną liczbę ${\ displaystyle | E |}$ krawędzie usuwane na każdym kroku, ale każda krawędź jest liczona dwukrotnie (raz na kierunek), dając $krawędzie usuwane w$ na każdym kroku.
• Stąd oczekiwany czas działania algorytmu to ${\ Displaystyle 3 \ log _ {4/3} (m) + 1},$ czyli ${ \displaystyle O(\log(n))}$ .

Algorytm równoległy z losową permutacją [algorytm Blellocha]

Zamiast losowania w każdym kroku, możliwe jest jednokrotne losowanie na początku algorytmu, ustalając losową kolejność węzłów. Biorąc pod uwagę tę ustaloną kolejność, następujący algorytm równoległy osiąga dokładnie taki sam MIS jak algorytm #Sequential (tj. wynik jest deterministyczny):

1. Zainicjuj I do pustego zestawu.
2. Podczas gdy V nie jest puste:
   • Niech W będzie zbiorem wierzchołków w V bez wcześniejszych sąsiadów (w oparciu o ustaloną kolejność);
   • Dodaj W do I;
   • Usuń z V węzły ze zbioru W i wszystkich ich sąsiadów.
3. Powrót I.

Pomiędzy całkowicie sekwencyjnymi i całkowicie równoległymi algorytmami istnieje kontinuum algorytmów, które są częściowo sekwencyjne, a częściowo równoległe. Biorąc pod uwagę ustaloną kolejność węzłów i współczynnik δ∈(0,1], następujący algorytm zwraca ten sam MIS:

1. Zainicjuj I do pustego zestawu.
2. Podczas gdy V nie jest puste:
   • Wybierz współczynnik δ∈(0,1).
   • Niech P będzie zbiorem δ n węzłów, które są pierwsze w ustalonej kolejności.
   • Niech W będzie MIS na P przy użyciu całkowicie równoległego algorytmu.
   • Dodaj W do I;
   • Usuń z V wszystkie węzły w prefiksie P i wszystkich sąsiadów węzłów w zbiorze W.
3. Powrót I.

Ustawienie δ=1/ n daje całkowicie sekwencyjny algorytm; ustawienie δ=1 daje całkowicie równoległy algorytm.

ANALIZA : Przy odpowiednim doborze parametru δ w algorytmie częściowo równoległym można zagwarantować, że zakończy się on po co najwyżej log(n) wywołań algorytmu w pełni równoległego, a liczba kroków w każdym wywołaniu jest co najwyżej log (N). Stąd całkowity czas działania algorytmu częściowo równoległego wynosi ${\ Displaystyle O (\ log ^ {2} (n))}$ . Stąd czas działania w pełni równoległego algorytmu również wynosi co najwyżej ${\ Displaystyle O (\ log ^ {2} (n))}$ . Główne kroki dowodowe to:

• Jeśli w kroku i wybierzemy , gdzie D jest maksymalnym stopniem węzła ${\ Displaystyle \ delta = 2 ^ {i} \ log {(n)}/D}$ na wykresie, a następnie WHP wszystkie węzły pozostałe po kroku i mają stopień co najwyżej ${\ displaystyle D/2 ^ {i}}$ . Zatem po krokach log( D ) wszystkie pozostałe węzły mają stopień 0 (ponieważ D < n ) i można je usunąć w jednym kroku.
• $w dowolnym$ stopień każdego i wybieramy dla C ), wtedy WHP najdłuższa ścieżka na grafie skierowanym określona przez ustaloną kolejność ma długość ${\ Displaystyle O (\ log (n))}$ . Stąd w pełni równoległy algorytm zajmuje co najwyżej ${\ Displaystyle O (\ log (n))}$ kroków (ponieważ najdłuższa ścieżka jest ograniczeniem liczby kroków w tym algorytmie w najgorszym przypadku).
• $faktów$ że wybierzemy częściowo równoległy algorytm to ${\ Displaystyle O (\ log (D) \ log (n)) = O (\ log ^ {2} (n))}$ .

Listowanie wszystkich maksymalnych niezależnych zbiorów

Dalsze informacje: Problem kliki § Lista wszystkich maksymalnych klik

Algorytm do wyszczególniania wszystkich maksymalnych niezależnych zbiorów lub maksymalnych klik na grafie może być użyty jako podprogram do rozwiązywania wielu problemów z grafami NP-zupełnymi. Najwyraźniej rozwiązania problemu maksymalnego zbioru niezależnego, problemu maksymalnej kliki i minimalnego niezależnego problemu dominującego muszą być maksymalnymi niezależnymi zbiorami lub maksymalnymi klikami i można je znaleźć za pomocą algorytmu, który wymienia wszystkie maksymalne niezależne zbiory lub maksymalne kliki i zachowuje te o największym lub najmniejszym rozmiarze. Podobnie minimalne pokrycie wierzchołków można znaleźć jako dopełnienie jednego z maksymalnych niezależnych zbiorów. Lawlera (1976) zaobserwował, że zestawienie maksymalnych niezależnych zbiorów może być również użyte do znalezienia 3-kolorowań grafów: graf może być 3-kolorowy wtedy i tylko wtedy, gdy dopełnienie jednego z jego maksymalnych niezależnych zbiorów jest dwudzielne . Zastosował to podejście nie tylko do kolorowania 3-kolorowego, ale jako część bardziej ogólnego algorytmu kolorowania grafów, a podobne podejście do kolorowania grafów zostało od tego czasu udoskonalone przez innych autorów. Inne, bardziej złożone problemy można również modelować jako znalezienie kliki lub niezależnego zbioru określonego typu. Motywuje to algorytmiczny problem skutecznego wylistowania wszystkich maksymalnych niezależnych zbiorów (lub równoważnie wszystkich maksymalnych klik).

Łatwo jest przekształcić dowód 3 ^{n / 3 Moona i Mosera} związany z liczbą maksymalnych niezależnych zbiorów w algorytm, który wymienia wszystkie takie zbiory w czasie O ( 3 ^{n / 3} ). W przypadku grafów, które mają największą możliwą liczbę maksymalnych niezależnych zestawów, ten algorytm wymaga stałego czasu na zestaw wyjściowy. Jednak algorytm z tym ograniczeniem czasowym może być wysoce nieefektywny w przypadku grafów z bardziej ograniczoną liczbą niezależnych zestawów. Z tego powodu wielu badaczy badało algorytmy, które wymieniają wszystkie maksymalne niezależne zbiory w czasie wielomianowym na zbiór wyjściowy. Czas na maksymalny niezależny zestaw jest proporcjonalny do mnożenia macierzy w gęstych grafach lub szybszy w różnych klasach rzadkich grafów.

Równoległość znajdowania maksymalnych zbiorów niezależnych

Historia

Pierwotnie uważano, że problem maksymalnego zbioru niezależnego nie jest trywialny do zrównoleglenia ze względu na fakt, że leksykograficzny maksymalny zbiór niezależny okazał się P-kompletny ; jednak wykazano, że deterministyczne rozwiązanie równoległe można uzyskać przez redukcję albo z maksymalnego upakowania zestawu , albo z $NC ^ {1}$ dopasowania , albo przez redukcję $^{2}}$${\ displaystyle$ redukcja z 2-spełnialności problem. Zazwyczaj struktura podanego algorytmu jest zgodna z innymi algorytmami grafów równoległych - to znaczy dzielą graf na mniejsze lokalne problemy, które można rozwiązać równolegle, uruchamiając identyczny algorytm.

Początkowe badania nad problemem maksymalnego zbioru niezależnego rozpoczęły się od modelu PRAM i od tego czasu rozszerzyły się, dając wyniki dla algorytmów rozproszonych w klastrach komputerowych . Wiele wyzwań związanych z projektowaniem rozproszonych algorytmów równoległych dotyczy równego problemu maksymalnego zbioru niezależnego. W szczególności znalezienie algorytmu, który wykazuje efektywny czas działania i jest optymalny w komunikacji danych do podziału grafu i łączenia niezależnych zestawów.

Klasa złożoności

Wykazali to w 1984 roku Karp i in. że deterministyczne rozwiązanie równoległe ${\ Displaystyle NC_ {4}}$ PRAM do maksymalnego niezależnego zestawu należało do zoo złożoności klasy Nicka z . Oznacza to, że ich algorytm znajduje maksymalny niezależny zbiór przy użyciu ${\ Displaystyle O (\ log ^ {4} n)}$ O $\ Displaystyle O ((n/\log n)^{3})}$ , gdzie $wierzchołków$ . W tym samym artykule zapewniono również losowe rozwiązanie równoległe z czasem wykonania ${\ Displaystyle O (\ log ^ {4} n)}$ przy użyciu ${\ Displaystyle O (n ^ {2})}$ procesorów. Wkrótce potem Luby i Alon et al. $NC_ {2}}$ 2 { ${\ Displaystyle O (\ log ^ {2} n)}$ środowisko wykonawcze przy użyciu procesorów ${\ Displaystyle O (mn ^ {2})} , gdzie$${\ Displaystyle m}$ jest liczbą krawędzi w grafie. Aby pokazać, że ich algorytm jest w $m)$$}$ przedstawili losowy algorytm, który wykorzystuje $, ale można$ za pomocą dodatkowych Dziś pozostaje otwarte pytanie, czy problem maksymalnego zbioru niezależnego jest w ${\ displaystyle NC_ {1}}$ .

Komunikacja i wymiana danych

Algorytmy z rozproszonymi maksymalnymi niezależnymi zbiorami są pod silnym wpływem algorytmów modelu PRAM. Oryginalna praca Luby i Alon et al. doprowadziło do kilku rozproszonych algorytmów. Jeśli chodzi o wymianę bitów, algorytmy te miały dolną granicę rozmiaru wiadomości na $rundę$ . Na przykład rozmiar wykresu musiałby być znany lub można by zapytać o maksymalny stopień sąsiednich wierzchołków dla danego wierzchołka. W 2010 roku Métivier i in. zmniejszono wymagany rozmiar wiadomości na rundę do ${\ Displaystyle O (1)}$ , co jest optymalne i eliminuje potrzebę dodatkowej znajomości wykresów.

Notatki

• Bisdorff, Raymond; Marichal, Jean-Luc (2008), „Zliczanie nieizomorficznych maksymalnych niezależnych zestawów wykresu n -cykli” , Journal of Integer Sequences , 11 : 08.5.7, arXiv : math.CO/0701647 .
•   Bomze, IM; Budinich, M.; Pardalos PM; Pelillo, M. (1999), „Maksymalny problem kliki”, Handbook of Combinatorial Optimization , tom. 4, Kluwer Academic Publishers, s. 1–74, CiteSeerX 10.1.1.48.4074 .
•   Byskov, JM (2003), „Algorytmy do kolorowania k i znajdowania maksymalnych niezależnych zestawów”, Proceedings of the Fourteen Annual ACM-SIAM Symposium on Discrete Algorithms , Soda '03, s. 456–457, ISBN 9780898715385 .
•   Chiba, N.; Nishizeki, T. (1985), „Algorytmy arboryczności i podgrafów” , SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 , S2CID 207051803 .
• Croitoru, C. (1979), „O stajniach na wykresach”, Proc. trzeci kol. Badania operacyjne , Uniwersytet Babeş-Bolyai , Kluż-Napoka, Rumunia, s. 55–60 .
•   Eppstein, D. (2003), „Małe maksymalne niezależne zestawy i szybsze dokładne kolorowanie wykresów” (PDF) , Journal of Graph Algorithms and Applications , 7 (2): 131–140, arXiv : cs.DS/0011009 , CiteSeerX 10.1. 1.342.4049 , doi : 10.7155/jgaa.00064 .
•   Eppstein, D. (2005), „Wszystkie maksymalne niezależne zbiory i dominacja dynamiczna dla rzadkich grafów”, Proc. Szesnaste doroczne sympozjum ACM-SIAM na temat algorytmów dyskretnych , tom. 5, s. 451–459, arXiv : cs.DS/0407036 , doi : 10.1145/1597036.1597042 , S2CID 2769046 .
•    Erdős, P. (1966), „O klikach na wykresach”, Israel Journal of Mathematics , 4 (4): 233–234, doi : 10.1007/BF02771637 , MR 0205874 , S2CID 121993028 .
• Euler, R. (2005), „Liczba Fibonacciego wykresu siatki i nowa klasa sekwencji całkowitych”, Journal of Integer Sequences , 8 (2): 05.2.6, Bibcode : 2005JIntS… 8… 26E .
• Füredi, Z. (1987), „Liczba maksymalnych niezależnych zestawów w połączonych grafach”, Journal of Graph Theory , 11 (4): 463–470, doi : 10,1002 / jgt.3190110403 .
• Jennings, E.; Motycková, L. (1992), „Rozproszony algorytm znajdowania wszystkich maksymalnych klik w grafie sieciowym”, Proc. Pierwsze sympozjum latynoamerykańskie na temat informatyki teoretycznej , notatki z wykładów z informatyki, tom. 583, Springer-Verlag, s. 281–293
• Johnson, DS ; Yannakakis, M .; Papadimitriou, CH (1988), „O generowaniu wszystkich maksymalnych niezależnych zestawów”, Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190 (88) 90065-8 .
• Lawler, EL (1976), „Uwaga na temat złożoności problemu liczb chromatycznych”, Information Processing Letters , 5 (3): 66–67, doi : 10.1016/0020-0190 (76) 90065-X .
• Lawler, EL ; Lenstra, J.K .; Rinnooy Kan, AHG (1980), „Generowanie wszystkich maksymalnych niezależnych zbiorów: NP-twardość i algorytmy czasu wielomianowego” (PDF) , SIAM Journal on Computing , 9 (3): 558–565, doi : 10.1137/0209042 .
• Leung, JY-T. (1984), „Szybkie algorytmy generowania wszystkich maksymalnych niezależnych zestawów wykresów interwałowych, kołowych i akordowych”, Journal of Algorithms , 5 : 22–35, doi : 10.1016/0196-6774 (84) 90037-3 .
•    Liang, YD; Dall, SK; Lakshmivarahan, S. (1991), „O problemie znalezienia wszystkich niezależnych zestawów o maksymalnej masie w wykresach przedziałów i łuków kołowych”, Proceeding of the 1991 Symposium on Applied Computing , s. 465–470, doi : 10.1109 / SOAC.1991.143921 , ISBN 0-8186-2136-2 , S2CID 122685841
•     Makino, K.; Uno, T. (2004), „Nowe algorytmy wyliczania wszystkich maksymalnych klik”, Proc. Dziewiąte skandynawskie warsztaty z teorii algorytmów , notatki z wykładów z informatyki, tom. 3111, Springer-Verlag, s. 260–272, CiteSeerX 10.1.1.138.705 , doi : 10.1007/978-3-540-27810-8_23 , ISBN 978-3-540-22339-9 . ISBN 9783540223399 , 9783540278108 .
•    Mishra, N.; Pitt, L. (1997), „Generowanie wszystkich maksymalnych niezależnych zestawów hipergrafów o ograniczonym stopniu”, Proc. Dziesiąta konferencja Teoria obliczeniowego uczenia się , s. 211–217, doi : 10.1145/267460.267500 , ISBN 978-0-89791-891-6 , S2CID 5254186 .
•    Księżyc, JW; Moser, L. (1965), „O klikach na wykresach”, Israel Journal of Mathematics , 3 : 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414 .
•    Stix, V. (2004), „Znajdowanie wszystkich maksymalnych klik w grafach dynamicznych”, Computational Optimization Appl. 27 ( 2 ) : 173–186 , CiteSeerX 10.1.1.497.6424 _ _ _
• Tomita, E.; Tanaka, A.; Takahashi, H. (2006), „Najgorszy przypadek złożoności czasowej do generowania wszystkich maksymalnych klik i eksperymentów obliczeniowych”, Theoretical Computer Science , 363 (1): 28–42, doi : 10.1016/j.tcs.2006.06.015 .
• Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I. (1977), „Nowy algorytm generowania wszystkich maksymalnych niezależnych zbiorów”, SIAM Journal on Computing , 6 (3): 505–517, doi : 10,1137/0206036 .
•    Waga, Martin; Hartmann, Alexander K. (2001), „Minimalne pokrycie wierzchołków na grafach losowych o skończonej łączności: obraz gazu sieciowego z twardą kulą”, Phys. Rev. E , 63 (5): 056127, arXiv : cond-mat/0011446 , Bibcode : 2001PhRvE..63e6127W , doi : 10.1103/PhysRevE.63.056127 , PMID 11414981 , S2CID 16773685 .
• Yu, C.-W.; Chen, G.-H. (1993), „Generuj wszystkie maksymalne niezależne zbiory na wykresach permutacji”, Internat. J. Komputer. Matematyka , 47 (1–2): 1–8, doi : 10.1080/00207169308804157 .