Maximální nezávislá sada - Maximal independent set

The graf krychle má šest různých maximálních nezávislých množin (dvě z nich jsou maximální), zobrazené jako červené vrcholy.

v teorie grafů, a maximální nezávislá množina (MIS) nebo maximální stabilní sada je nezávislá sada to není podmnožina žádné jiné nezávislé množiny. Jinými slovy, mimo nezávislou množinu neexistuje žádný vrchol, který by se k ní mohl připojit, protože je maximální vzhledem k vlastnosti nezávislé množiny.

Například v grafu ${ displaystyle P_ {3}}$, cesta se třemi vrcholy ${ displaystyle a}$, ${ displaystyle b}$, a ${ displaystyle c}$a dvě hrany ${ displaystyle ab}$ a ${ displaystyle bc}$, sady ${ displaystyle {b }}$ a ${ displaystyle {a, c }}$ jsou oba maximálně nezávislí. Sada ${ displaystyle {a }}$ je nezávislý, ale není maximální nezávislý, protože je podmnožinou větší nezávislé sady ${ displaystyle {a, c }}$. Ve stejném grafu jsou maximálními klikami množiny ${ displaystyle {a, b }}$ a ${ displaystyle {b, c }}$.

MIS je také dominující sada v grafu a každá dominující množina, která je nezávislá, musí být maximálně nezávislá, proto se také nazývají MIS nezávislé dominující sady.

První dva ${ displaystyle P_ {3}}$ grafy jsou maximální nezávislé množiny, zatímco spodní dvě jsou nezávislé sady, ale ne maximální. Maximální nezávislá množina je představována vlevo nahoře.

Graf může mít mnoho MIS různých velikostí;^[1] největší nebo možná několik stejně velkých MIS grafu se nazývá a maximální nezávislá množina. Jsou volány grafy, ve kterých mají všechny maximální nezávislé sady stejnou velikost dobře pokryté grafy.

Fráze „maximální nezávislá množina“ se také používá k popisu maximálních podmnožin nezávislých prvků v jiných matematických strukturách než v grafech, zejména v vektorové prostory a matroidy.

Dvě nezávislé sady pro hvězdný graf ${ displaystyle S_ {8}}$ ukázat, jak obrovsky odlišné mohou být dvě maximální nezávislé množiny (pravá maximální).

Dva algoritmické problémy jsou spojeny s MIS: najít a singl MIS v daném grafu a výpis Všechno MIS v daném grafu.

Definice

Pro graf ${ displaystyle G = (V, E)}$, an nezávislá sada ${ displaystyle S}$ je maximální nezávislá množina pokud pro ${ displaystyle v ve V}$, platí jedna z následujících možností:^[2]

1. ${ displaystyle v v S}$
2. ${ displaystyle N (v) čepice S neq emptyset}$ kde ${ displaystyle N (v)}$ označuje sousedy ${ displaystyle v}$

Výše uvedené lze zopakovat, protože vrchol buď patří do nezávislé množiny, nebo má alespoň jeden sousední vrchol, který patří do nezávislé množiny. Výsledkem je, že každá hrana grafu nemá alespoň jeden koncový bod, který není v ${ displaystyle S}$. Není však pravda, že každá hrana grafu má alespoň jeden nebo dokonce jeden koncový bod ${ displaystyle S}$

Všimněte si, že každý soused s vrcholem v nezávislé množině ${ displaystyle S}$ nemůže být v ${ displaystyle S}$ protože tyto vrcholy jsou disjunktní podle definice nezávislé množiny.

Související sady vrcholů

Li S je maximální nezávislá množina v nějakém grafu, je to maximální klika nebo maximální úplný podgraf v doplňkový graf. Maximální klikou je sada vrcholů, které indukuje A kompletní podgraf, a to není podmnožina vrcholů žádného většího úplného podgrafu. To znamená, že je to sada S tak, aby každý pár vrcholů dovnitř S je spojen hranou a každý vrchol není v S chybí hrana alespoň jednoho vrcholu v S. Graf může mít mnoho maximálních klik různých velikostí; najít největší z nich je maximální problém s klikou.

Někteří autoři zahrnují maximální část jako součást definice kliky a odkazují na maximální kliky jednoduše jako na kliky.

Vlevo je maximální nezávislá množina. Middle je klika, ${ displaystyle K_ {3}}$, na grafu doplněk. Vpravo je vrcholový kryt na maximálním nezávislém množinovém doplňku.

The doplněk maximální nezávislé množiny, tj. množiny vrcholů, které nepatří do nezávislé množiny, tvoří a minimální vrcholový kryt. To znamená, že doplněk je vrcholový kryt, sada vrcholů, která zahrnuje alespoň jeden koncový bod každé hrany, a je minimální v tom smyslu, že žádný z jejích vrcholů nelze odstranit při zachování vlastnosti, že se jedná o krytí. Minimální vrcholové kryty byly studovány v statistická mechanika v souvislosti s mřížkový plyn tvrdé koule model, matematická abstrakce přechodů kapalina-pevná fáze.^[3]

Každá maximální nezávislá množina je a dominující sada, sada vrcholů tak, že každý vrchol v grafu buď patří do množiny, nebo k ní sousedí. Sada vrcholů je maximální nezávislá množina právě tehdy, pokud jde o nezávislou dominující množinu.

Charakterizace rodiny grafů

Určité rodiny grafů byly také charakterizovány z hlediska jejich maximálních klik nebo maximálních nezávislých množin. Mezi příklady patří neredukovatelné maximálně klikaté a dědičné neredukovatelné grafy maximální kliky. Říká se, že je graf maximální klika neredukovatelná pokud má každá maximální klika hranu, která nepatří do žádné jiné maximální kliky, a dědičná maximální klika neredukovatelná pokud platí stejná vlastnost pro každý indukovaný podgraf.^[4] Dědičné maximálně klikaté neredukovatelné grafy zahrnují grafy bez trojúhelníků, bipartitní grafy, a intervalové grafy.

Cographs lze charakterizovat jako grafy, ve kterých každá maximální klika protíná každou maximální nezávislou množinu a ve kterých platí stejná vlastnost ve všech indukovaných podgrafech.

Ohraničení počtu sad

Moon & Moser (1965) ukázal, že jakýkoli graf s n vrcholy má maximálně 3^n/3 maximální kliky. Doplňkově jakýkoli graf s n vrcholy mají také maximálně 3^n/3 maximální nezávislé množiny. Graf s přesně 3^n/3 maximální nezávislé množiny lze snadno sestavit: jednoduše vezměte disjunktní spojení n/3 trojúhelníkové grafy. Jakákoli maximální nezávislá množina v tomto grafu je vytvořena výběrem jednoho vrcholu z každého trojúhelníku. Doplňkový graf s přesně 3^n/3 maximální kliky, je speciální typ Turánův graf; kvůli jejich spojení s Měsícem a Moserovou vazbou se tyto grafy také někdy nazývají Moon-Moserovy grafy. Přísnější hranice jsou možné, pokud omezíme velikost maximálních nezávislých sad: počet maximálních nezávislých sad velikostí k v každém n-vertexový graf je maximálně

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

Grafy dosahující této hranice jsou opět Turánovy grafy.^[5]

Určité rodiny grafů však mohou mít mnohem přísnější hranice počtu maximálních nezávislých množin nebo maximálních klik. Padám n-vertexové grafy v rodině grafů mají O (n) hrany, a pokud každý podgraf grafu v rodině patří také do rodiny, pak každý graf v rodině může mít maximálně O (n) maximální kliky, z nichž všechny mají velikost O (1).^[6] Například tyto podmínky platí pro rovinné grafy: každý n-vertex rovinný graf má maximálně 3n - 6 hran a podgraf rovinného grafu je vždy rovinný, z čehož vyplývá, že každý rovinný graf má O (n) maximální kliky (o velikosti nejvýše čtyř). Intervalové grafy a chordální grafy také mít nanejvýš n maximální kliky, i když ne vždy řídké grafy.

Počet maximálních nezávislých souborů v n-vrchol cyklické grafy je dán Perrinova čísla a počet maximálních nezávislých souborů v n-vrchol grafy cesty je dán Padovan sekvence.^[7] Proto jsou obě čísla úměrná mocninám 1.324718, plastové číslo.

Nalezení jediné maximální nezávislé množiny

Sekvenční algoritmus

Vzhledem k grafu G (V, E) je snadné najít jeden MIS pomocí následujícího algoritmu:

1. Inicializujte I na prázdnou sadu.
2. Zatímco V není prázdný:
   • Vyberte uzel v∈V;
   • Přidejte v do množiny I;
   • Odstraňte z V uzel v a všechny jeho sousedy.
3. Návrat I.

Runtime je O (m) protože v nejhorším případě musíme zkontrolovat všechny hrany.

O (m) je samozřejmě nejlepší možný běh pro sériový algoritmus. Ale paralelní algoritmus může vyřešit problém mnohem rychleji.

Paralelní algoritmus s náhodným výběrem [Luby's Algorithm]

Následující algoritmus najde MIS v čase O (log n).^[2][8][9]

1. Inicializujte I na prázdnou sadu.
2. Zatímco V není prázdný:
   • Vyberte náhodnou množinu vrcholů S ⊆ V výběrem každého vrcholu v nezávisle s pravděpodobností 1 / (2d (v)), kde d je stupeň v (počet sousedů v).
   • Pro každou hranu v E, pokud jsou oba její koncové body v náhodném souboru S, pak odeberte z S koncový bod, jehož stupeň je nižší (tj. Má méně sousedů). Libovolně přerušujte vazby, např. pomocí lexikografického pořadí na názvy vrcholů.
   • Přidejte sadu S do I.
   • Odstraňte z V množinu S a všechny sousedy uzlů v S.
3. Návrat I.

ANALÝZA: Pro každý uzel v rozdělte jeho sousedy na nižší sousedé (jehož stupeň je nižší než stupeň v) a vyšší sousedé (jehož stupeň je vyšší než stupeň v), zlomení vazeb jako v algoritmu.

Volejte uzel v špatný pokud více než 2/3 jejích sousedů jsou vyššími sousedy. Zavolejte hranu špatný pokud jsou oba jeho koncové body špatné; jinak je hrana dobrý.

• Alespoň 1/2 všech okrajů je vždy dobrých. DŮKAZ: Vytvořte řízenou verzi G nasměrováním každé hrany do uzlu s vyšším stupněm (libovolné lámání vazeb). Takže pro každý špatný uzel je počet odchozích hran více než dvojnásobný než počet příchozích hran. Takže každá špatná hrana, která vstupuje do uzlu v, může být porovnána s odlišnou sadou dvou hran, které opouštějí uzel v. Celkový počet hran je tedy alespoň 2krát větší než počet špatných hran.
• Pro každý dobrý uzel u je pravděpodobnost, že je soused u vybrán k S, alespoň určitá pozitivní konstanta. DŮKAZ: pravděpodobnost, že ŽÁDNÝ soused u nebude vybrán na S, je nanejvýš pravděpodobnost, že žádný z u nebude nižší sousedé je vybrána. U každého nižšího souseda v je pravděpodobnost, že není vybrána, (1-1 / 2d (v)), což je maximálně (1-1 / 2d (u)) (protože d (u)> d (v )). Počet takových sousedů je alespoň d (u) / 3, protože u je dobrý. Pravděpodobnost, že není vybrán žádný soused, je tedy maximálně 1-exp (-1/6).
• Pro každý uzel u, který je vybrán na S, je pravděpodobnost, že u bude odstraněno z S, maximálně 1/2. DŮKAZ: Tato pravděpodobnost je nanejvýš pravděpodobností, že vyšší soused u je vybrán na S. Pro každého vyššího souseda v je pravděpodobnost, že je vybrán, nanejvýš 1 / 2d (v), což je maximálně 2d (u) (od d (v)> d (u)). Sjednocená vazba je pravděpodobnost, že není vybrán žádný vyšší soused, nanejvýš d (u) / 2d (u) = 1/2.
• Proto pro každý dobrý uzel u je pravděpodobnost, že soused u je vybrán k S a zůstane v S, je určitá pozitivní konstanta. Proto je pravděpodobnost, že u bude odstraněno, v každém kroku alespoň pozitivní konstanta.
• Proto je pro každou dobrou hranu e pravděpodobnost, že je e odstraněno, v každém kroku alespoň pozitivní konstanta. Takže počet dobrých hran klesá každým krokem alespoň o konstantní faktor.
• Protože alespoň polovina okrajů je dobrá, celkový počet okrajů také klesá o konstantní faktor v každém kroku.
• Proto je počet kroků O (log m), kde m je počet hran. To je omezeno ${ displaystyle O ( log (n))}$.

Nejhorší graf, ve kterém je průměrný počet kroků ${ displaystyle Theta ( log (n))}$, je graf vytvořený z n/ 2 připojené komponenty, každá se 2 uzly. Stupeň všech uzlů je 1, takže každý uzel je vybrán s pravděpodobností 1/2 a s pravděpodobností 1/4 nejsou vybrány oba uzly v komponentě. Proto počet uzlů v každém kroku klesá o faktor 4 a očekávaný počet kroků je ${ displaystyle log _ {4} (n)}$.

Paralelní algoritmus s náhodnou prioritou

Následující algoritmus je lepší než předchozí v tom, že do každé připojené komponenty je vždy přidán alespoň jeden nový uzel:^[10][9]

1. Inicializujte I na prázdnou sadu.
2. Zatímco V není prázdný, každý uzel v provádí následující:
   • Vybere náhodné číslo r (v) v [0,1] a odešle jej sousedům;
   • Pokud je r (v) menší než počet všech sousedů v, pak se v vloží do I, odstraní se z V a řekne o tom svým sousedům;
   • Pokud v slyšel, že se jeden z jeho sousedů dostal do I, pak se v odstraní z V.
3. Návrat I.

Všimněte si, že v každém kroku uzel s nejmenším počtem v každé připojené komponentě vždy vstupuje do I, takže vždy dochází k určitému pokroku. Zejména v nejhorším případě předchozího algoritmu (n/ 2 připojené komponenty po 2 uzlech), MIS bude nalezen v jediném kroku.

ANALÝZA:

• Uzel ${ displaystyle v}$ má alespoň pravděpodobnost ${ displaystyle { frac {1} {d (v) + d (w)}}}$ být odstraněn. DŮKAZ: Pro každou hranu spojující pár uzlů ${ displaystyle (v, w)}$, nahraďte jej dvěma směrovanými hranami, jednou z ${ displaystyle (v, w)}$ a ostatní ${ displaystyle (w, v)}$. Všimněte si toho ${ displaystyle | E |}$ je nyní dvakrát větší. Pro každou dvojici směrovaných hran ${ displaystyle (v, w)}$, definujte dvě události: ${ displaystyle (v rightarrow w)}$ a ${ displaystyle (w rightarrow v)}$, ${ displaystyle v}$ preventivně odstraní ${ displaystyle w}$ a ${ displaystyle w}$ preventivně odstraní ${ displaystyle v}$, resp. Událost ${ displaystyle (v rightarrow w)}$ nastane, když ${ displaystyle r (v)$ a ${ displaystyle r (v)$, kde ${ displaystyle w}$ je soused ${ displaystyle v}$ a ${ displaystyle x}$ je soused ${ displaystyle w}$. Připomeňme, že každému uzlu je dáno náhodné číslo ve stejném rozsahu [0, 1]. V jednoduchém příkladu se dvěma disjunktními uzly má každý pravděpodobnost ${ displaystyle { frac {1} {2}}}$ být nejmenší. Pokud existují tři nesouvislé uzly, každý má pravděpodobnost ${ displaystyle { frac {1} {3}}}$ být nejmenší. V případě ${ displaystyle v}$, má alespoň pravděpodobnost ${ displaystyle { frac {1} {d (v) + d (w)}}}$ být nejmenší, protože je možné, že soused ${ displaystyle v}$ je také sousedem ${ displaystyle w}$, takže uzel se započítá dvakrát. Stejnou logikou událost ${ displaystyle (w rightarrow v)}$ také má alespoň pravděpodobnost ${ displaystyle { frac {1} {d (w) + d (v)}}}$ být odstraněn.
• Když události ${ displaystyle (v rightarrow w)}$ a ${ displaystyle (w rightarrow v)}$ nastanou, odstraní ${ displaystyle d (w)}$ a ${ displaystyle d (v)}$ směrované odchozí hrany. DŮKAZ: V případě ${ displaystyle (v rightarrow w)}$, když ${ displaystyle v}$ je odstraněn, všechny sousední uzly ${ displaystyle w}$ jsou také odstraněny. Počet odchozích směrovaných hran od ${ displaystyle w}$ odstraněno je ${ displaystyle d (w)}$. Se stejnou logikou ${ displaystyle (w rightarrow v)}$ odstraní ${ displaystyle d (v)}$ směrované odchozí hrany.
• V každé iteraci kroku 2 se v očekávání odstraní polovina okrajů. DŮKAZ: Pokud událost ${ displaystyle (v rightarrow w)}$ stane se pak všem sousedům ${ displaystyle w}$ jsou odstraněny; proto je očekávaný počet hran odstraněných kvůli této události alespoň ${ displaystyle { frac {d (w)} {d (v) + d (w)}}}$. Totéž platí pro reverzní událost ${ displaystyle (w rightarrow v)}$, tj. očekávaný počet odstraněných hran je alespoň ${ displaystyle { frac {d (v)} {d (w) + d (v)}}}$. Proto pro každou nepřímou hranu ${ displaystyle (w, v)}$, očekávaný počet hran odstraněných kvůli jednomu z těchto uzlů s nejmenší hodnotou je ${ displaystyle { frac {d (w) + d (v)} {d (w) + d (v)}} = 1}$. Součet přes všechny hrany, ${ displaystyle sum _ {{v, w} v E} 1 = | E |}$, dává očekávaný počet ${ displaystyle | E |}$ hrany odstraněny v každém kroku, ale každá hrana se počítá dvakrát (jednou v každém směru), což dává ${ displaystyle { frac {| E |} {2}}}$ hrany odstraněny v očekávání každého kroku.
• Očekávaná doba běhu algoritmu je tedy ${ displaystyle 3 log _ {4/3} (m) +1}$ který je ${ displaystyle O ( log (n))}$.^[9]

Paralelní algoritmus s náhodnou permutací [Blellochův algoritmus]

Místo randomizace v každém kroku je možné randomizovat jednou, na začátku algoritmu, fixováním náhodného uspořádání na uzlech. Vzhledem k tomuto pevnému uspořádání dosahuje následující paralelní algoritmus přesně stejné MIS jako # Sekvenční algoritmus (tj. výsledek je deterministický):^[11]

1. Inicializujte I na prázdnou sadu.
2. Zatímco V není prázdný:
   • Nechť W je množina vrcholů ve V bez předchozích sousedů (na základě pevného uspořádání);
   • Přidat W do I;
   • Odstraňte z V uzly v množině W a všechny jejich sousedy.
3. Návrat I.

Mezi zcela sekvenčními a zcela paralelními algoritmy existuje kontinuum algoritmů, které jsou částečně sekvenční a částečně paralelní. Vzhledem k pevnému uspořádání na uzlech a faktoru δ∈ (0,1] vrátí následující algoritmus stejnou MIS:

1. Inicializujte I na prázdnou sadu.
2. Zatímco V není prázdný:
   • Vyberte faktor δ∈ (0,1].
   • Nechť P je množina δn uzly, které jsou v pevném pořadí první.
   • Nechť W je MIS na P pomocí zcela paralelního algoritmu.
   • Přidat W do I;
   • Odstraňte z V všechny uzly v prefixu P a všechny sousedy uzlů v množině W.
3. Návrat I.

Nastavení δ = 1 /n dává zcela sekvenční algoritmus; nastavení δ = 1 dává zcela paralelní algoritmus.

ANALÝZA: Při správném výběru parametru δ v částečně paralelním algoritmu je možné zaručit, že skončí po maximálně log (n) voláních plně paralelního algoritmu a počet kroků v každém volání je maximálně log (n). Proto je celková doba běhu částečně paralelního algoritmu ${ displaystyle O ( log ^ {2} (n))}$. Proto je běh plně paralelního algoritmu také nanejvýš ${ displaystyle O ( log ^ {2} (n))}$. Hlavní kontrolní kroky jsou:

• Pokud v kroku i, vybereme ${ displaystyle delta = 2 ^ {i} log {(n)} / D}$, kde D je maximální stupeň uzlu v grafu WHP všechny uzly zbývající po kroku i mít titul nanejvýš ${ displaystyle D / 2 ^ {i}}$. Po protokolu (D) kroky, všechny zbývající uzly mají stupeň 0 (od D<n) a lze jej odstranit v jednom kroku.
• Pokud je v každém kroku stupeň každého uzlu nanejvýš da vybereme ${ displaystyle delta = C log {(n)} / d}$ (pro každou konstantu C), pak WHP nejdelší cesta v směrovaném grafu určená pevným uspořádáním má délku ${ displaystyle O ( log (n))}$. Proto plně paralelní algoritmus trvá nanejvýš ${ displaystyle O ( log (n))}$ kroky (protože nejdelší cesta je nejhorší případ vázaný na počet kroků v daném algoritmu).
• Kombinace těchto dvou faktů to dává, pokud vybereme ${ displaystyle delta = 2 ^ {i} log {(n)} / D}$, pak WHP je doba běhu částečně paralelního algoritmu ${ displaystyle O ( log (D) log (n)) = O ( log ^ {2} (n))}$.

Seznam všech maximálních nezávislých sad

Algoritmus pro výpis všech maximálních nezávislých množin nebo maximálních klik do grafu lze použít jako podprogram pro řešení mnoha problémů grafu NP-Complete. Je zřejmé, že řešení problému maximální nezávislé množiny, problému maximální kliky a problému minimální nezávislé dominance musí být všechny maximální nezávislé množiny nebo maximální kliky a lze je najít pomocí algoritmu, který uvádí všechny maximální nezávislé množiny nebo maximální kliky a zachovává ty s největší nebo nejmenší velikostí. Podobně minimální vrcholový kryt lze nalézt jako doplněk jedné z maximálních nezávislých množin. Lawler (1976) zjistil, že výpis maximálních nezávislých množin lze také použít k nalezení 3barevnosti grafů: graf může být 3barevný právě tehdy, když doplněk jedné z jeho maximálních nezávislých množin je bipartitní. Tento přístup použil nejen pro 3-zbarvení, ale jako součást obecnějšího algoritmu barvení grafů a podobné přístupy k barvení grafů od té doby vylepšili i další autoři.^[12] Další složitější problémy lze také modelovat jako hledání kliky nebo nezávislé sady konkrétního typu. To motivuje algoritmický problém efektivně vypsat všechny maximální nezávislé sady (nebo ekvivalentně všechny maximální kliky).

Je jednoduché ukázat důkaz Měsíce a Moserovy 3^n/3 vázán na počet maximálních nezávislých množin do algoritmu, který uvádí všechny takové množiny v čase O (3^n/3).^[13] U grafů, které mají největší možný počet maximálních nezávislých množin, trvá tento algoritmus konstantní čas na každou výstupní sadu. Algoritmus s touto časovou vazbou však může být vysoce neúčinný pro grafy s omezenějším počtem nezávislých sad. Z tohoto důvodu mnoho vědců studovalo algoritmy, které uvádějí všechny maximální nezávislé sady v polynomiálním čase na výstupní sadu.^[14] Čas na maximální nezávislou množinu je úměrný času pro násobení matic v hustých grafech nebo rychlejší v různých třídách řídkých grafů.^[15]

Paralelizace hledání maximálních nezávislých množin

Dějiny

Původně se myslelo, že maximální problém nezávislé množiny je netriviální paralelizovat vzhledem k tomu, že lexikografická maximální nezávislá množina se ukázala být P-Complete; ukázalo se však, že deterministické paralelní řešení by mohlo být dáno pomocí ${ displaystyle NC ^ {1}}$ snížení buď z maximální sada balení nebo maximální shoda problém nebo ${ displaystyle NC ^ {2}}$ snížení z 2 - uspokojivost problém.^[16][17] Struktura daného algoritmu obvykle následuje další algoritmy paralelního grafu - to znamená, že rozdělují graf na menší lokální problémy, které lze řešit paralelně spuštěním stejného algoritmu.

Počáteční výzkum problému maximální nezávislé množiny začal na PRAM model a od té doby se rozšířil, aby přinesl výsledky pro distribuované algoritmy na počítačové klastry. Mnoho výzev navrhování distribuovaných paralelních algoritmů platí stejně jako problém maximální nezávislé množiny. Zejména hledání algoritmu, který vykazuje efektivní běhový čas a je optimální v datové komunikaci pro rozdělení grafu a sloučení nezávislé množiny.

Třída složitosti

Ukázalo to v roce 1984 Karp et al. že deterministické paralelní řešení na PRAM k maximální nezávislé množině patřilo do Složitost Nickovy třídy zoo ${ displaystyle NC_ {4}}$.^[18] To znamená, že jejich algoritmus najde maximální nezávislou množinu ${ displaystyle O ( log ^ {4} n)}$ použitím ${ displaystyle O ((n / log n) ^ {3})}$, kde ${ displaystyle n}$ je velikost sady vrcholů. Ve stejném článku bylo také poskytnuto randomizované paralelní řešení s dobou běhu ${ displaystyle O ( log ^ {4} n)}$ použitím ${ displaystyle O (n ^ {2})}$ procesory. Krátce nato Luby a Alon a kol. nezávisle na tomto výsledku vylepšeno, čímž se maximální nezávislý problém nastavil do sféry ${ displaystyle NC_ {2}}$ s ${ displaystyle O ( log ^ {2} n)}$ runtime pomocí ${ displaystyle O (mn ^ {2})}$ procesory, kde ${ displaystyle m}$ je počet hran v grafu.^[17][8][19] Aby ukázali, že jejich algoritmus je v ${ displaystyle NC_ {2}}$, původně představili randomizovaný algoritmus, který používá ${ displaystyle O (m)}$ procesory, ale mohly by být derandomizovány dalším ${ displaystyle O (n ^ {2})}$ procesory. Dnes zůstává otevřenou otázkou, zda se jedná o problém maximální nezávislé množiny ${ displaystyle NC_ {1}}$.

Komunikace a výměna dat

Distribuované maximální nezávislé sady algoritmů jsou silně ovlivněny algoritmy na modelu PRAM. Původní dílo Luby a Alon et al. vedlo k několika distribuovaným algoritmům.^{[20][21][22][19]} Pokud jde o výměnu bitů, měly tyto algoritmy spodní hranici velikosti zprávy na jedno kolo ${ displaystyle O ( log n)}$ bitů a vyžadovalo by to další charakteristiky grafu. Například bude třeba znát velikost grafu nebo lze zjistit maximální stupeň sousedních vrcholů pro daný vrchol. V roce 2010 Métivier et al. snížil požadovanou velikost zprávy na kolo na ${ displaystyle O (1)}$, což je optimální a odstranilo potřebu dalších znalostí grafů.^[23]

Poznámky

Reference