Maximális független csúcshalmaz

A matematika, azon belül a gráfelmélet területén egy maximális független csúcshalmaz, maximális független ponthalmaz, maximális független halmaz (MFH) vagy maximális stabil halmaz (angol nyelvterületen: maximal independent set = MIS vagy maximal stable set) olyan független csúcshalmaz, ami nem valódi részhalmaza egyetlen független csúcshalmaznak sem. Más szavakkal, nincs olyan rajta kívül eső csúcs, amit a halmazhoz hozzá lehetne venni anélkül, hogy megszűnne független csúcshalmaznak lenni.

A kockagráfban hat különböző, az ábrákon piros csúcsokkal jelölt maximális független csúcshalmaz található.

Például a három csúcsú ${\displaystyle P_{3}}$ útgráf esetén, melyet az ${\displaystyle a}$, ${\displaystyle b}$ és ${\displaystyle c}$ csúcsok, valamint az ${\displaystyle ab}$ és ${\displaystyle bc}$ élek alkotnak, mind a ${\displaystyle \{b\}}$, mind az ${\displaystyle \{a,c\}}$ maximális független csúcshalmaz. Az ${\displaystyle \{a\}}$ halmaz független, de nem maximális, mivel valódi részhalmaza a nagyobb ${\displaystyle \{a,c\}}$ független csúcshalmaznak. Ugyanennek a gráfnak a maximális klikkjei az ${\displaystyle \{a,b\}}$ és ${\displaystyle \{b,c\}}$ halmazok.

Egy MFH egyben a gráf domináló halmaza is, és minden domináló halmaz, ami független, egyben maximális független is, ezért a maximális független halmazokat gyakran független domináló halmazoknak (independent dominating sets) is nevezik.

A felső két ${\displaystyle P_{3}}$-gráfon maximális független halmazokat, az alsó kettőn nem maximális független halmazokat láthatunk. A bal felső a maximális elemszámú független halmaz.

Egy gráf nagyon különböző méretű MFH-kkal rendelkezhet;^[1] közülük a legnagyobb MFH-t vagy MFH-kat maximális elemszámú független csúcshalmaznak (maximum independent set) nevezzük. Az olyan gráfok, melyekben a maximális független csúcshalmazok mind azonos méretűek, a jól fedett gráfok (well-covered graph).

Az ${\displaystyle S_{8}}$ csillaggráf két független csúcshalmaza demonstrálja, milyen különböző méretűek lehetnek egy gráf maximális független csúcshalmazai (melyek közül a jobboldali a maximális elemszámú).

Két algoritmikus probléma köthető az MFH-khoz: megtalálni adott gráf egyetlen, illetve az összes MFH-ját.

Definíció

Egy ${\displaystyle G=(V,E)}$ gráf ${\displaystyle S}$ független csúcshalmaza akkor maximális független csúcshalmaz, ha bármely ${\displaystyle v\in V}$ csúcsra a következők egyike igaz:^[2]

1. ${\displaystyle v\in S}$
2. ${\displaystyle N(v)\cap S\neq \emptyset }$, ahol ${\displaystyle N(v)}$ ${\displaystyle v}$ szomszédait jelöli.

A fenti definíció úgy is megfogalmazható, hogy egy csúcs vagy a független csúcshalmazba tartozik, vagy legalább egy csúcs-szomszédja a független csúcshalmazba tartozik. Végeredményképpen a gráf minden élének legalább egy végpontja ${\displaystyle S}$-en kívül esik. Ugyanakkor nem igaz, hogy a gráf bármely élének legalább egy végpontja ${\displaystyle S}$-ben lenne.

Vegyük észre, hogy az ${\displaystyle S}$ független csúcshalmaz közvetlen szomszédságában lévő csúcs a független halmaz definíciója szerint nem lehet ${\displaystyle S}$-ben.

Vonatkozó csúcshalmazok

Ha S egy gráf maximális független csúcshalmaza, egyben a gráf komplementerének maximális klikkje vagy maximális teljes részgráfja. Egy maximális klikk olyan csúcshalmazt jelent, melyek feszített részgráfjai teljes gráfok, de maga nem valódi részhalmaza egyetlen teljes részgráfnak sem. Tehát egy olyan S csúcshalmaz, amiben minden S-beli csúcspárat él köt össze, és minden S-en kívüli csúcsra igaz, hogy legalább egy S-beli csúccsal nem köti össze él. Egy gráfnak több maximális klikkje is lehet, ezek közül a legnagyobb megkeresése a klikkprobléma.

Egyes szerzők a maximális jelleget a klikk alaptulajdonságának tekintik, és a maximális klikkekre egyszerűen klikkekként hivatkoznak.

A baloldali egy maximális független csúcshalmaz. A középső egy klikk, ${\displaystyle K_{3}}$, a gráf komplementerén. A jobboldali egy csúcslefedés a maximális független csúcshalmaz komplementerén.

Egy maximális független csúcshalmaz komplementere, tehát az MFH-ba nem tartozó csúcsok halmaza minimális csúcslefedést (minimal vertex cover) alkot. Tehát a komplementer halmaz egy csúcslefedés, azaz olyan csúcsok halmaza, melyek minden él legalább egy végpontját tartalmazzák, és olyan értelemben minimális, hogy egy csúcsot sem lehet belőle eltávolítani anélkül, hogy ne veszítse el csúcslefedés mivoltát. A minimális csúcslefedéseket a statisztikus mechanika területén a folyékony-szilárd halmazállapot-átmenetek egy matematikai absztrakciójával, a merev gömbök modelljével kapcsolatban tanulmányozzák.^[3]

Minden maximális csúcshalmaz egyben domináló halmaz, a gráf csúcsainak olyan halmaza, melyre igaz, hogy a gráf csúcsai vagy beletartoznak a halmazba vagy szomszédosak vele. Csúcsok egy halmaza pontosan akkor maximális független, ha független domináló.

Gráfcsalád-jellemzések

Egyes gráfcsaládokat a maximális klikkszámuk vagy maximális független halmazuk kapcsán határoznak meg. Ilyenek például a maximal-clique irreducible és hereditary maximal-clique irreducible gráfok. Egy gráf akkor maximal-clique irreducible, ha minden maximális klikkjének van olyan éle, ami nem tartozik másik maximális klikkhez, míg a hereditary maximal-clique irreducible gráfoknak ez a tulajdonság minden feszített részgráfjára is igaz.^[4] A Hereditary maximal-clique irreducible gráfok közé tartoznak a háromszögmentes gráfok, a páros gráfok és az intervallumgráfok is.

A kográfok egyik jellemzésük szerint olyan gráfok, melyekben minden maximális klikk metsz minden maximális független csúcshalmazt, és ez a tulajdonság minden feszített részgráfra is teljesül.

A csúcshalmazok számára vonatkozó korlátok

(Moon & Moser 1965) megmutatták, hogy egy n csúcsú gráf legfeljebb 3^n/3 maximális klikket tartalmaz. A komplementer esetben hasonló a helyzet, egy n csúcsú gráf legfeljebb 3^n/3 maximális független csúcshalmazzal bír. Könnyű konstruálni olyan gráfot, aminek pontosan 3^n/3 MFH-ja van: venni kell n/3 db háromszöggráf össze nem kötött unióját. Ebben a gráfban az MFH-kat úgy kaphatjuk meg, hogy minden háromszögből pontosan egy csúcsot választunk. A komplementer gráf, amiben pontosan 3^n/3 maximális klikk van, a Turán-gráfok egy specifikus fajtája; a Moon and Moser-féle korláttal való kapcsolatuk miatt néha Moon–Moser-gráfoknak is nevezik őket. Az MFH-k méretét korlátozva szorosabb korlátok is elérhetők: egy n-csúcsú gráfban a k nagyságú MFH-k maximális száma

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

A korlátot beállító gráfok itt is Turán-gráfok.^[5]

Egyes gráfcsaládok még erősebb korlátokkal bírnak az MFH-k számára, illetve a maximális klikkekre nézve. Ha egy család minden n-csúcsú gráfjának O(n) éle van, és a gráfcsalád minden gráfjának minden részgráfja is a családba tartozik, akkor a család minden gráfjának legfeljebb O(n) maximális klikkje lehet, melyek mérete O(1).^[6] Ezek a feltételek igazak például a síkgráfokra: minden n-csúcsú síkgráfnak legfeljebb 3n − 6 éle van, és egy síkgráf részgráfja is mindig síkgráf, amiből az következik, hogy egy síkgráfnak legfeljebb O(n) maximális klikkje lehet (melyek mérete legfeljebb négy). A intervallumgráfok és húrgráfok szintén legfeljebb n maximális klikkel rendelkeznek, bár ezek nem mindig ritka gráfok.

Az n-csúcsú körgráfok MFH-inak számát a Perrin-számok adják meg, míg az n-csúcsú útgráfokét a Padovan-sorozat.^[7] Így tehát mindkét szám a plasztikszám, ~1,324718 hatványaival arányos.

Egyetlen maximális független csúcshalmaz megkeresése

Szekvenciális algoritmus

Adott G(V,E) gráf egy MFH-ja könnyen megkereshető a következő algoritmussal:

1. Inicializáljuk I-t üres halmazként.
2. Amíg V üres nem lesz:
   • Válasszunk egy v∈V csúcsot;
   • Adjuk v-t az I halmazhoz;
   • Vegyük ki v-t és összes szomszédját V-ből.
3. Visszatérési érték: I.

A futási idő O(n), mivel legrosszabb esetben minden csúcsot vizsgálni kell.

Az O(n) nyilvánvalóan az elérhető legjobb futási idő egy soros algoritmus számára. Egy párhuzamos algoritmussal azonban jóval gyorsabban megoldható a probléma.

Véletlen kiválasztásos párhuzamos algoritmus

A következő algoritmus O(log n) időben talál egy MFH-t.^[2][8][9]

1. Inicializáljuk I-t üres halmazként.
2. Amíg V üres nem lesz:
   • Válasszunk ki véletlenszerűen egy S ⊆ V csúcshalmazt úgy, hogy minden egyes v csúcsot egymástól függetlenül, 1/(2d(v)) valószínűséggel választunk ki, ahol d a v csúcs fokát (szomszédainak számát) jelöli.
   • Minden E-beli élre, ha mindkét végpontja a véletlen S halmazban található, akkor a két végpont közül az alacsonyabb fokszámút távolítsuk el S-ből. Döntetlen esetekben tetszés szerint lehet választani, például a csúcsok neveinek lexikografikus sorrendjét figyelembe véve.
   • Adjuk az S halmaz elemeit I-hez.
   • Vegyük ki V halmaz elemeit és az összes velük szomszédos elemet az S halmazból.
3. Visszatérési érték: I.

Analízis: Minden v csúcs esetében felosztjuk a szomszédokat „alacsonyakra” (melyek fokszáma kisebb v fokszámánál) és „magasakra” (melyek fokszáma magasabb v fokszámánál), a döntetlen eseteket valamilyen módon eldöntve.

Tekintsünk egy csúcsot „rossznak”, ha szomszédainak több mint ⅔-ad része a magasak közé tartozik. Tekintsünk egy élet „rossznak”, ha mindkét csúcsa rossz, egyébként az él legyen „jó”.

• Legalább az élek ½-e minden esetben jó. Bizonyítás: Alakítsunk ki irányított gráfot G-ből oly módon, hogy minden él a magasabb fokszámú csúcs felé mutasson (a döntetlen eseteket tetszőleges módon eldöntve). Így minden rossz csúcsnál a kimenő élek száma több mint kétszerese a bejövő élekének. Tehát minden v-be menő rossz élhez párosítható két másik él, ami v-ből kifelé irányul. Összegezve, az összes él száma legalább kétszerese a rossz élek számának.
• Minden jó u csúcs esetében annak valószínűsége, hogy egy szomszédot S tagjává választunk nagyobb egyenlő egy pozitív konstanssal. Bizonyítás: annak valószínűsége, hogy u egyetlen szomszédját sem választjuk S-be legfeljebb annak a valószínűségével egyezik meg, hogy u egyetlen „alacsony” szomszédját sem választjuk ki. Minden egyes alacsony szomszéd v csúcs esetében a nem kiválasztás valószínűsége (1-1/2d(v)), ami legfeljebb (1-1/2d(u)) lehet, mivel d(u)≤d(v). Az ilyen szomszédok száma legalább d(u)/3, mivel u jó csúcs. Ezért annak a valószínűsége, hogy egyetlen alacsony szomszéd sem lesz kiválasztva, legfeljebb 1-exp(-1/6).
• Bármely S-be választott u csúcs esetében annak valószínűsége, hogy u el lesz távolítva S-ből legfeljebb ½. Bizonyítás: ez a valószínűség legfeljebb annak a valószínűségét éri el, hogy u-nak egy magas szomszédját választjuk S-be. Minden egyes magas v szomszéd esetében a kiválasztás valószínűsége legfeljebb 1/2d(v), ami legfeljebb 1/2d(u), mivel d(v)≤d(u). A korlátok egyesítésével megkapjuk, hogy annak valószínűsége, hogy egyetlen magas szomszéd sem lesz kiválasztva, legfeljebb d(u)/2d(u) = 1/2.
• Így tehát, minden jó u csúcs esetén annak valószínűsége, hogy egy szomszédját S-be választják és benne is marad, egy bizonyos pozitív konstansnak felel meg. Ebből következik, hogy annak a valószínűsége, hogy u eltávolításra kerül, bármely lépésben, szintén nagyobb egyenlő egy pozitív konstansnál.
• Továbbá, minden jó e él esetében az e eltávolításának valószínűsége minden lépésben nagyobb egyenlő egy pozitív konstansnál. Tehát a jó élek száma minden lépésben legalább egy konstans faktorral csökken.
• Mivel legalább az élek fele jó, az össz-élszám is minden lépésben legalább egy konstans faktorral csökken.
• Így tehát, a szükséges lépések száma O(log m), ahol m az élek száma. Ennek korláta ${\displaystyle O(\log(n))}$.

Az algoritmus számára a legrosszabb eset, ahol ${\displaystyle \Theta (\log(n))}$ lépésre van szükség, egy n/2 összefüggő komponensből álló gráf, melynek minden komponensét két csúcs alkotja. A csúcsok fokszáma 1, tehát minden csúcs ½ valószínűséggel lesz kiválasztva, és ¼ valószínűséggel nem választjuk ki egy komponens mindkét csúcsát. Tehát a csúcsok száma minden lépésben 4-edére csökken, a várható lépésszám tehát ${\displaystyle \log _{4}(n)}$.

Véletlen prioritásos párhuzamos algoritmus

A következő algoritmus annyival jobb az előzőleg leírtnál, hogy minden lépésben legalább egy új csúcsot hozzáadunk minden összefüggő komponenshez:^[9][10]

1. Inicializáljuk I-t üres halmazként.
2. Amíg V üres nem lesz, minden v csúcs a következőket végezze el:
   • Válasszon egy r(v) véletlen számot a [0,1] intervallumban és küldje el az összes szomszédjának;
   • Ha r(v) kisebb mint bármely szám, amit a szomszédaitól kapott, akkor v behelyezi magát I-be, eltávolítja magát V-ből és erről értesíti szomszédait;
   • Ha v megtudja, hogy valamely szomszédja I-be jutott, akkor v eltávolítja magát V-ből.
3. Visszatérési érték: I.

Vegyük észre, hogy minden összefüggő komponensben legalább egy, a legkisebb számot választó csúcs bekerül I-be, tehát mindig történik előrelépés. Az előző algoritmus legrosszabb esetének számító n/2 összefüggő komponens, mindegyikben pontosan 2 csúcs esetben az MFH-t egyetlen lépésben előállítjuk.

Analízis:

• Egy ${\displaystyle v}$ csúcs eltávolításának valószínűsége legalább ${\displaystyle {\frac {1}{d(v)+d(w)}}}$. Bizonyítás: Cseréljünk le minden ${\displaystyle (v,w)}$ csúcspárt összekötő élet két irányított éllel, az egyik legyen ${\displaystyle (v,w)}$, a másik ${\displaystyle (w,v)}$ irányú. Vegyük észre, hogy az ${\displaystyle |E|}$ most éppen dupla méretű lett. Minden ${\displaystyle (v,w)}$ irányított élpárhoz definiáljunk két eseményt: ${\displaystyle (v\rightarrow w)}$-t és ${\displaystyle (w\rightarrow v)}$-t, ahol ${\displaystyle v}$ preemptíven eltávolítja ${\displaystyle w}$-t és ${\displaystyle w}$ preemptíven eltávolítja ${\displaystyle v}$-t. A ${\displaystyle (v\rightarrow w)}$ esemény akkor következik be, ha ${\displaystyle r(v)<r(w)}$ és ${\displaystyle r(v)<r(x)}$, ahol ${\displaystyle w}$ szomszédja ${\displaystyle v}$-nek és ${\displaystyle x}$ szomszédja ${\displaystyle w}$-nek. Tudjuk, hogy minden csúcshoz tartozik egy [0, 1] intervallumbeli véletlenszám. Tekintsünk egy egyszerű, két különálló csúcsból álló példát, ekkor mindkettő ${\displaystyle {\frac {1}{2}}}$ valószínűséggel lesz a legkisebb; három különálló csúcsnál mindhárom esetében ez a valószínűség ${\displaystyle {\frac {1}{3}}}$. Ha ${\displaystyle v}$ csúcsot vizsgálunk, a legkisebbnek levés valószínűsége legalább ${\displaystyle {\frac {1}{d(v)+d(w)}}}$, hiszen elképzelhető, hogy ${\displaystyle v}$ szomszédja egyben ${\displaystyle w}$ szomszédja is, így pedig egy csúcsot kétszer számolnánk. Ugyanezen logika alapján a ${\displaystyle (w\rightarrow v)}$ esemény eltávolításának valószínűsége is legalább ${\displaystyle {\frac {1}{d(w)+d(v)}}}$.
• Amikor a ${\displaystyle (v\rightarrow w)}$ és a ${\displaystyle (w\rightarrow v)}$ események történnek, ${\displaystyle d(w)}$, illetve ${\displaystyle d(v)}$ irányított kimenő éleket távolítják el. Bizonyítás: A ${\displaystyle (v\rightarrow w)}$ esemény bekövetkeztekor, amikor ${\displaystyle v}$ eltávolításra kerül, valamennyi szomszédos ${\displaystyle w}$ csúcsot is eltávolítjuk. A ${\displaystyle w}$-ből kimenő, eltávolított élek száma ${\displaystyle d(w)}$. Hasonló logikát alkalmazva, ${\displaystyle (w\rightarrow v)}$ éppen ${\displaystyle d(v)}$ irányított kimenő élet távolít el.
• A második lépés minden iterációja során várható, hogy az élek fele eltávolításra kerül. Bizonyítás: Ha a ${\displaystyle (v\rightarrow w)}$ esemény következik be, akkor ${\displaystyle w}$ minden szomszédját eltávolítjuk, ezért az eltávolított élek száma legalább ${\displaystyle {\frac {d(w)}{d(v)+d(w)}}}$. Ugyanez igaz a fordított, ${\displaystyle (w\rightarrow v)}$ eseményre is, tehát az eltávolított élek száma legalább ${\displaystyle {\frac {d(v)}{d(w)+d(v)}}}$. Így tehát, minden irányítatlan ${\displaystyle (w,v)}$ él esetében a legkisebb értékű csúcs miatt eltávolított élek számának várható értéke ${\displaystyle {\frac {d(w)+d(v)}{d(w)+d(v)}}=1}$. Ezt összegezve az éleken, ${\displaystyle \sum _{{v,w}\in E}1=|E|}$, ami az egyes lépésben eltávolított élekre ${\displaystyle |E|}$-t adna, de minden élet kétszer számoltunk (irányonként egyszer), ami az egy lépésben eltávolított élek várható értékére ${\displaystyle {\frac {|E|}{2}}}$-t ad.
• Ebből következően, az algoritmus várható futási ideje ${\displaystyle 3\log _{4/3}(m)+1}$, ami ${\displaystyle O(\log(n))}$.^[9]

Véletlen permutáló párhuzamos algoritmus

Ahelyett, hogy minden lépésben véletlenül választanánk, elegendő egyszer, az algoritmus kezdetén véletlenszerűen választani, megadva a csúcsok egy véletlenszerű rendezését. Ezt a véletlenszerű rendezést tekintve a következő párhuzamos algoritmus ugyanahhoz az MFH-hoz jut, mint a #Szekvenciális algoritmus (tehát az eredmény determinisztikus):^[11]

1. Inicializáljuk I-t üres halmazként.
2. Amíg V üres nem lesz:
   • Legyen W azoknak a V-beli csúcsoknak a halmaza, amiknek nincsen korábbi szomszédjuk (a fix rendezést tekintve);
   • Adjuk W-t I-hez;
   • Vegyük ki V-ből a W-ben lévő csúcsokat és az összes szomszédjukat.
3. Visszatérési érték: I.

A teljesen szekvenciális és a teljesen párhuzamosított algoritmus szélső esetei között elképzelhető egy kontinuum, amit részben szekvenciális, részben párhuzamos algoritmusok alkotnak. Ha veszünk egy fix rendezést a csúcsokon, és egy δ∈(0,1] faktort, a következő algoritmus ugyanazt az MFH-t adja vissza:

1. Inicializáljuk I-t üres halmazként.
2. Amíg V üres nem lesz:
   • Válasszunk egy δ∈(0,1] faktort.
   • Legyen P a rendezésben elöl álló, δn csúcs halmaza.
   • Legyen W a P-n futtatott teljesen párhuzamos algoritmus által visszaadott MFH.
   • Adjuk W-t I-hez;
   • Vegyük ki V-ből a P-ben lévő csúcsokat és a W halmaz szomszédait.
3. Visszatérési érték: I.

A δ=1/n a teljesen szekvenciális algoritmust adja, a δ=1 pedig a teljesen párhuzamos algoritmust.

Analízis: A részlegesen párhuzamos algoritmus esetében a δ paraméter értékének megfelelő megválasztásával garantálható, hogy a teljesen párhuzamos algoritmus legfeljebb log(n) meghívásával befejeződik, és minden hívás legfeljebb log(n) lépésben véget ér. Így a részlegesen párhuzamos algoritmus teljes futási ideje ${\displaystyle O(\log ^{2}(n))}$. Továbbá, a teljesen párhuzamos algoritmus futásideje szintén legfeljebb ${\displaystyle O(\log ^{2}(n))}$. A bizonyítás főbb lépései:

• Ha az i. lépésben ${\displaystyle \delta =2^{i}\log {(n)}/D}$-t választunk, ahol D a gráf maximális fokszáma, akkor nagy valószínűséggel minden i lépés után megmaradó csúcs fokszáma legfeljebb ${\displaystyle D/2^{i}}$. Tehát log(D) lépés után minden megmaradó csúcs foka 0 (hiszen D<n) és egyetlen lépésben eltávolítható.
• Ha bármely lépésben minden csúcs fokszáma legfeljebb d, és ${\displaystyle \delta =C\log {(n)}/d}$-t választunk (bármely C konstansra), akkor nagy valószínűséggel az irányított gráfban a fix rendezés által meghatározott leghosszabb út hossza ${\displaystyle O(\log(n))}$. Így a teljesen párhuzamos algoritmusnak legfeljebb ${\displaystyle O(\log(n))}$ lépésre van szüksége (hiszen a leghosszabb út az algoritmus lépésszáma szempontjából a legrosszabb eset).
• Ezt a két tényt kombinálva, ha ${\displaystyle \delta =2^{i}\log {(n)}/D}$-t választjuk, akkor nagy valószínűséggel a részlegesen párhuzamos algoritmus futásideje ${\displaystyle O(\log(D)\log(n))=O(\log ^{2}(n))}$.

Az összes maximális független csúcshalmaz listázása

Lásd még: Klikkprobléma#Az összes maximális klikk listázása

Egy olyan algoritmust, ami megkeresi egy gráf összes MFH-ját vagy maximális klikkjét fel lehet használni számos NP-teljes gráfprobléma megoldásának szubrutinjaként. A legnyilvánvalóbb esetekben, tehát a maximális elemszámú független halmaz, a maximális elemszámú klikk, illetve a minimális független domináló halmaz keresése esetében a keresett halmaznak mindig MFH-nak vagy maximális klikknek kell lennie, tehát a keresés végrehajtható úgy is, hogy egy algoritmus listázza az összes maximális független halmazt vagy maximális klikket, és megtartja a legnagyobb vagy legkisebb méretűt. Hasonlóan, a minimális csúcslefedés is megkereshető, mint valamely MFH komplementere. (Lawler 1976) megfigyelése szerint az MFH-k listázása a gráfok 3-színezésének megtalálására is használható: egy gráf pontosan akkor színezhető 3 színnel, ha valamely MFH-jának komplementer gráfja páros. Ezt a megközelítést Lawler nem csak a 3-színezéshez használta fel, hanem egy általánosabb gráfszínező algoritmus részeként. Más szerzők azóta hasonló, egyre kifinomultabb gráfszínezési megközelítéseket dolgoztak ki.^[12] Más, komplex problémák szintén modellezhetők valamely specifikus típusú klikk vagy független halmaz kereséseként. Ezek motiválják annak az összes maximális független csúcshalmaz (vagy maximális klikk) listázásának algoritmikus problémájának hatékonyabb megoldását.

Elég egyszerűen átültethető Moon and Moser az MFH-k számára vonatkozó 3^n/3-as korlátja egy olyan algoritmusba, ami az összes MFH-t O(3^n/3) idő alatt listázza.^[13] Ez az algoritmus a kimeneti halmazonként konstans időben lefut a lehető legnagyobb számú MFH-val rendelkező gráfokra. Sajnos azonban egy ilyen időkorláttal rendelkező algoritmus nagyon hatékonytalan tud lenni a kevesebb MFH-val rendelkező gráfokon. Így aztán számos kutató tanulmányozta a kimenetenként polinomális időben lefutó algoritmusokat.^[14] Az MFH-nként szükséges idő arányos a sűrű gráfok mátrixszorzásának idejével, illetve ritka gráfok egyes osztályainál ennél gyorsabb is lehet.^[15]

A maximális elemszámú független halmazok keresésének párhuzamosítása

Története

Eredetileg úgy gondolták, hogy az MFH-keresés problémáját nem triviális párhuzamosítani, hiszen a lexikografikus MFH-keresés P-teljesnek bizonyult; megmutatták azonban, hogy megadható egy determinisztikus párhuzamos megoldás akár a maximális halmazpakolás vagy a maximális párosítás problémájának ${\displaystyle NC^{1}}$-redukciójával, akár a 2-SAT kielégíthetőségi probléma ${\displaystyle NC^{2}}$-redukciójával.^[16][17] Jellemzően az algoritmus szerkezete hasonlít a többi párhuzamos gráfalgoritmuséhoz: felosztják a gráfot kisebb lokális problémákra, melyek aztán ugyanazt az algoritmust párhuzamos módon sok helyen futtatva megoldhatók.

Az MFH-probléma kezdeti kutatását a PRAM-modell szerint végezték, majd kiterjesztették a számítógépfürtökön futó elosztott algoritmusokra is. Az elosztott párhuzamos algoritmusok számos tervezési problémája az MFH-probléma esetében is előjön; különös tekintettel arra, hogy az algoritmus futásidő és adatkommunikáció szempontjából is hatékony legyen, miközben a gráfot felosztja és a független halmazba elemeket helyez.

Bonyolultságosztály

1984-ben Karp és tsai megmutatták, hogy az MFH-probléma PRAM-on történő megoldása az NC bonyolultsági osztályon belül ${\displaystyle NC_{4}}$-be tartozik.^[18] Ez azt jelenti, hogy az algoritmusuknak egy MFH megkereséséhez ${\displaystyle O(\log ^{4}n)}$ időre és ${\displaystyle O((n/\log n)^{3})}$ helyre van szüksége, ahol ${\displaystyle n}$ a csúcshalmaz mérete. Ugyanebben a tanulmányukban egy randomizált párhuzamosított megoldást is leírtak, ami ${\displaystyle O(\log ^{4}n)}$ idő alatt futott le ${\displaystyle O(n^{2})}$ processzoron. Nem sokkal ezután Luby, Alon és tsai. Karpék eredményétől függetlenül javítottak ezen az eredményen, elérve az ${\displaystyle NC_{2}}$-t, ${\displaystyle O(\log ^{2}n)}$ futási idővel ${\displaystyle O(mn^{2})}$ processzoron, ahol ${\displaystyle m}$ a gráf éleinek számát jelöli.^[8][17][19] Az algoritmus ${\displaystyle NC_{2}}$ voltának igazolására először bemutattak egy randomizált algoritmust, aminek ${\displaystyle O(m)}$ processzorra van szükség, de a véletlenszerűség megszüntethető ${\displaystyle O(n^{2})}$ processzor hozzáadásával. Jelenleg is nyitott kérdés, hogy az MFH-probléma vajon az ${\displaystyle NC_{1}}$ osztályban található-e..

Kommunikáció, adatcsere

Az elosztott MFH-algoritmusok létrehozását jelentősen befolyásolták a korábban a PRAM-modellre készített algoritmusok. A Luby, Alon és tsai. által végzett kezdeti kutatások számos elosztott algoritmushoz vezettek.^{[19][20][21][22]} Bitek átvitele szempontjából ezek az algoritmusok körönként legalább ${\displaystyle O(\log n)}$ bitet igényelnek és a gráf egyéb karakterisztikájára is szükség van a működésükhöz. Például ismerni kell a gráf méretét vagy a szomszédos csúcsok maximális fokszámát le kell tudni kérdezni a működéshez. 2010-ben Métivier és tsai. sikeresen lecsökkentették a körönkénti üzenetek méretét az optimális ${\displaystyle O(1)}$ értékre, és megszabadították az algoritmust a gráf egyéb tulajdonságai ismeretének igényétől.^[23]

Jegyzetek

1. (Erdős 1966) megmutatja, hogy egy n-csúcsú gráf különböző méretű MFH-inak száma akár n − log n − O(log log n) is lehet, de sohasem nagyobb n − log n-nél.
2. Luby’s Algorithm, in: Lecture Notes for Randomized Algorithms, Last Updated by Eric Vigoda on February 2, 2006
3. (Weigt & Hartmann 2001).
4. Information System on Graph Class Inclusions: maximal clique irreducible graphs Archiválva 2007. július 9-i dátummal a Wayback Machine-ben and hereditary maximal clique irreducible graphs Archiválva 2007. július 8-i dátummal a Wayback Machine-ben.
5. (Byskov 2003). Korábbi eredmények ezen a téren itt: (Croitoru 1979) és (Eppstein 2003).
6. (Chiba & Nishizeki 1985). Chiba and Nishizeki az O(n) élek feltételét ezzel ekvivalens módon, a gráf arboricitásának konstansságával mondják ki.
7. (Bisdorff & Marichal 2007); (Euler 2005); (Füredi 1987).
8. (1986) „A Simple Parallel Algorithm for the Maximal Independent Set Problem”. SIAM Journal on Computing 15 (4), 1036. o. DOI:10.1137/0215074.
9. Principles of Distributed Computing (lecture 7). ETH Zurich. [2015. február 21-i dátummal az eredetiből archiválva]. (Hozzáférés: 2015. február 21.)
10. (2010) „An optimal bit complexity randomized distributed MIS algorithm”. Distributed Computing 23 (5–6), 331. o. DOI:10.1007/s00446-010-0121-5.
11. Blelloch, Guy; Fineman, Jeremy; Shun, Julian (2012). "Greedy Sequential Maximal Independent Set and Matching are Parallel on Average".
12. (Eppstein 2003); (Byskov 2003).
13. (Eppstein 2003). A széles körben használt Bron–Kerbosch-algoritmus hasonló korlátjához lásd (Tomita, Tanaka & Takahashi 2006).
14. (Bomze et al. 1999); (Eppstein 2005); (Jennings & Motycková 1992); (Johnson, Yannakakis & Papadimitriou 1988); (Lawler, Lenstra & Rinnooy Kan 1980); (Liang, Dhall & Lakshmivarahan 1991); (Makino & Uno 2004); (Mishra & Pitt 1997); (Stix 2004); (Tsukiyama et al. 1977); (Yu & Chen 1993).
15. (Makino & Uno 2004); (Eppstein 2005).
16. Cook, Stephen (1983. június 1.). „An overview of computational complexity”. Commun. ACM. [2016. március 4-i dátummal az eredetiből archiválva]. (Hozzáférés: 2016. szeptember 30.)
17. Barba, Luis: LITERATURE REVIEW: Parallel algorithms for the maximal independent set problem in graphs, 2012. október 1.
18. Karp, R.M. (1984. október 14.). „A fast parallel algorithm for the maximal independent set problem”. Proc. 16th ACM Symposium on Theory of Computing.
19. Alon, Noga (1986. október 14.). „A fast and simple randomized parallel algorithm for the maximal independent set problem”. Journal of Algorithms.
20. Peleg, D. (2000. október 14.). „Distributed computing—A Locality-sensitive approach”. SIAM Monographs on Discrete Mathematics and Applications.
21. Lynch, N.A. (1996. október 14.). „Distributed Algorithms”. Morgan Kaufman.
22. Wattenhofer, R.: Chapter 4: Maximal Independent Set
23. Métivier, Y. (2010. október 14.). „An optimal bit complexity randomized distributed MIS algorithm”. Distributed Computing.

• .
• .
• .
• .
• .
• Archiválva 2008. július 25-i dátummal a Wayback Machine-ben.
• .
• .
• .
• .
• .
• .
• .
• .
• ^{[halott link]}.
• .
• .
• .
• .
• .
• .