A független halmaz probléma

A független halmazprobléma a gráfelmélet területén az NP-teljes feladatok osztályába tartozik . Egyenértékű a klikk problémával .

Definíciók

Egy gráf csúcshalmazát függetlennek nevezzük, ha ennek a halmaznak nincs két csúcsa összekötve éllel. Más szóval, a halmaz által indukált részgráf izolált csúcsokból áll. Néha azt is mondják, hogy a gráf minden éle egy független halmaz legfeljebb egy csúcsára esik. A felismerési probléma (decidability problem) így néz ki: van-e egy adott G gráfnak független k méretű halmaza ? A hozzá tartozó optimalizálási feladat, más néven független halmazprobléma a következőképpen fogalmazódik meg: egy adott G gráfban meg kell találni egy maximális méretű független halmazt. Ezt a méretet függetlenségi számnak , belső sűrűségszámnak vagy lazaságnak nevezik, és [1] [2] -ként jelöljük . $\alpha (G)$

Ezt a problémát néha a legnagyobb független halmaz megtalálásának nevezik . Ezt a fogalmat nem szabad összetéveszteni a maximális független halmazzal , vagy a maximális független halmazzal , amely a csúcsok olyan független halmazaként van definiálva, hogy ha az eredeti gráf még egy (bármely) csúcsát hozzáadjuk hozzá, az megszűnik függetlenek legyenek (általában több és különböző méretű ilyen halmazok létezhetnek). Egy befogadó-maximális független halmaz semmiképpen sem mindig a legnagyobb. Ugyanakkor minden legnagyobb független halmaz definíció szerint a befogadás által is maximális. A befogadás (valamilyen) maximális független halmazának megtalálásához egy mohó algoritmus használható , amely polinomiális időben fut, míg a legnagyobb független halmaz problémája az NP-teljes feladatok osztályába tartozik.

A befogadás-maximális független halmaz egy domináns halmaz . Bármely gráf maximum 3 n /3 zárványmaximális független halmazt tartalmaz [3] , de a legtöbb gráfban jóval kevesebb van belőlük.

Az n csúcsú ciklusokban a befogadás-maximális független halmazok száma Perrin-szám , az n csúcsú utak zárvány-maximális független halmazainak számát pedig a Padovan sorozat [4] adja meg . Így mindkét szám arányos 1,324718, a képlékeny szám hatványával .

A gráf legkisebb független részhalmaza a gráf bármely csúcsa.

Kapcsolat más gráfparaméterekkel

Egy halmaz akkor és csak akkor független, ha egy klikk a gráf komplementerében , tehát a két fogalom kiegészíti egymást. A kellően nagy gráfok nagy klikkek nélkül nagy független halmazokkal rendelkeznek, ami a Ramsey-elmélet tanulmányozásának tárgya .

Egy halmaz akkor és csak akkor független, ha komplementere csúcsfedő . A függetlenségi szám és a csúcsfedő szám összege megegyezik a gráf csúcsainak számával (az első Gallai azonosság ). $\alpha (G)$ $\tau (G)$

A gráf csúcsainak színezése megfelel a csúcsok független részhalmazokra való felosztásának . Ezért a csúcsok színezéséhez szükséges minimális színszám, a kromatikus szám nem kisebb, mint a csúcsok számának és a függetlenségi számnak a hányadosa . $G$ $\chi (G)$ $G$ $\alpha (G)$

Az izolált csúcsokkal nem rendelkező kétrészes gráfokban a legnagyobb független halmaz csúcsainak száma megegyezik a legkisebb élfedő éleinek számával (a König-tétel következménye ).

Független halmazok keresése

A számítástechnikában számos független halmazhoz kapcsolódó számítási problémát

A legnagyobb független halmazproblémában a bemenet egy irányítatlan gráf, a kimenet pedig a gráf legnagyobb független halmaza. Ha több ilyen készlet van, akkor elég egyet találni.
A maximális súlyfüggetlen halmazfeladatnál a bemenet egy irányítatlan gráf csúcssúlyokkal, a kimenet pedig egy független halmaz a maximális összsúllyal. A befogadó maximum független halmazprobléma ennek a feladatnak egy speciális esete eggyel egyenlő súlyokkal.
A befogadó-maximális független halmazok felsorolásának problémájában a bemenet egy irányítatlan gráf, a kimenet pedig az összes befogadó-maximális független halmaz listája. A legnagyobb független halmaz problémája ennek a feladatnak a részproblémájaként oldható meg, mivel a legnagyobb független halmaz a maximum, és szerepelnie kell ebben a listában.
Abban a problémában, hogy van egy adott méretű független halmaz, a bemenet egy irányítatlan gráf és egy k szám , a kimenet pedig Igen / Nem : Igen , ha a gráf k méretű független halmazt tartalmaz , egyébként pedig a No.

Az első három probléma a gyakorlati alkalmazásokban fontos, míg az utolsó az NP-teljesség elmélete szempontjából a független halmazokkal kapcsolatos problémák esetében.

A független halmazprobléma és a klikk probléma kettős: a klikk G -ben független halmaz G komplementerében és fordítva. Így számos számítási eredmény egyformán jól alkalmazható mindkét problémára. Például a klikkproblémával kapcsolatos eredmények a következő következményekkel járnak:

A jelenléti probléma NP-teljes , ami azt jelenti, hogy a megoldására szolgáló hatékony algoritmus létezése (ahogy a nemléte is) nem bizonyított. Hatékony (közelítő [5] ) heurisztikus algoritmusok léteznek a gráf maximális súlytól független csúcskészletének megtalálására, erre példa a Rusov-féle V.S. és Zakharova D.A. amelynek komplexitása O( n 3 ).
A legnagyobb független halmazprobléma NP-nehéz , és ráadásul nehezen közelíthető .

A legnagyobb független halmaz megkeresése

Ezt a problémát néha " csúcscsomagolásnak " is nevezik.

A legnagyobb független halmazprobléma és a legnagyobb klikkprobléma polinomiálisan ekvivalens – a legnagyobb független halmazt úgy találhatjuk meg, ha a gráf komplementerében megtaláljuk a maximális klikket, így sok szerző nem különösebben törődik a két probléma szétválasztásával. Mindkét probléma NP-teljes, így nem valószínű, hogy polinomiális időben megoldhatóak. A legnagyobb független halmazprobléma azonban hatékonyabban megoldható, mint O( n 2 2 n ) idő alatt, ami egy kimerítő keresést eredményez, amely megvizsgálja a csúcsok összes részhalmazát, hogy kiderüljön, független halmazokról van-e szó. A Robson-algoritmus [6] O(2 0,276 n ) időben oldja meg a feladatot az exponenciális tér felhasználásával. Ha van korlát a méretben (polinom tér), akkor van egy algoritmus az O*(1,2127 n ) időbeli megoldására [7] .

Annak ellenére, hogy egy tetszőleges gráfban szoros kapcsolat van a legnagyobb klikk és a legnagyobb független halmaz között, a független halmaz és a klikk megtalálásának problémái jelentősen eltérhetnek, ha egy speciális gráfosztályon oldjuk meg. Például ritka gráfok esetén (olyan gráfok, amelyekben az élek száma egy részgráfban nem nagyobb, mint a csúcsok számának szorzata valamilyen konstanssal) a legnagyobb klikk korlátozott méretű, és lineáris időben pontosan megtalálható [8] . Azonban ugyanazon gráfosztályok esetén, vagy akár szigorúbb korlátozások esetén egy korlátos fokozatú gráfosztályra a legnagyobb független halmaz keresése MAXSNP-teljes , ami azt jelenti, hogy valamilyen c állandóra (attól függően fokon) NP - nehéz olyan közelítő megoldást találni, amely c tényezővel különbözik az optimálistól [9] . Hatékony közelítő algoritmusok azonban ismertek, de garantált hatékonyságuk rosszabb, mint ez a küszöb. Például egy mohó algoritmus egy befogadás-maximális független halmazt hoz létre úgy, hogy minden lépésben kiválaszt egy csúcsot a minimális fokszámmal, és eltávolítja a szomszédait. Ez az algoritmus garantált hatékonyságot (Δ+2)/3 ér el maximum Δ [10] fokú gráfokon .

A gráfok egyes osztályaiban (beleértve a karmok nélküli gráfokat [11] és a tökéletes gráfokat [12] ; a fák is ez utóbbi osztályba tartoznak ) a legnagyobb független halmaz polinomidőben található. Síkgráfok esetén a legnagyobb független halmazprobléma NP-teljes marad a pontos megoldáshoz, de bármilyen garantált hatékonysággal közelíthető, ha c < 1 polinomidőben. Hasonló közelítő polinomiális idősémák léteznek bármely kis mértékben zárt gráfcsaládban [ 13] [14] .

A kétrészes gráfokban minden olyan csúcs, amely nincs a legkisebb csúcsfedőben, a legnagyobb független halmazba foglalható (lásd König tételét ). Ezért a legnagyobb független halmazt megtalálhatjuk a kétrészes gráfokban a legnagyobb egyezések megtalálására szolgáló algoritmus segítségével.

Inklúzió-maximális független halmazok keresése

Minden zárvány-maximális független halmaz megtalálható O(3 n /3 ) időben.

Szoftver független halmazok megtalálásához

Név	Engedély	API nyelv	Leírás
igraph	GPL	C, Python, R, Ruby	pontos megoldás
NetworkX	BSD	Piton	közelítő megoldás, lásd a maximum_independent_set eljárást
openopt	BSD	Piton	pontos és közelítő megoldások, a beszámítandó / kizárandó csúcsok megadásának képessége. Részletekért és példákért lásd a STAB osztályt

A legnagyobb független halmaz egy fában

Ha az adott gráf egy fa , akkor a független halmazprobléma hatékonyan megoldható dinamikus programozással .

A probléma optimális alstruktúrája

Maga a fa szerkezete sugallja a probléma megoldását. Ugyanis bármely csúcsot a fa gyökereként jelöljük, és nevezzük . Jelölje annak a részfa legnagyobb független csúcshalmazának méretét, amelynek gyökere a csúcs . Akkor az lesz a válasz a problémára . $r$ $én(u)$ $u$ $I(r)$

Könnyen belátható, hogy ha a legnagyobb független halmazba belevesszük az u csúcsot , akkor annak számossága 1-gyel nő, de gyermekeit nem vehetjük (hiszen éllel kapcsolódnak az u csúcshoz ); ha ezt a csúcsot nem vesszük figyelembe, akkor a legnagyobb független halmaz számossága megegyezik az e csúcshoz tartozó független gyermekhalmazok méreteinek összegével. Csak a két lehetőség közül a maximumot kell kiválasztani a probléma megoldása érdekében:

I(u)=\max \left\{1\ +\ \sum _{{{\text{unoka}}\ w\ of\ u}}I(w),\ \sum _{{{\text{ gyermek}}\ w\ of\ u}}I(w)\right\},

ahol az unoka a csúcs bármely "unokáját", a gyermek pedig a csúcs bármely leszármazottját jelöli.

Pszeudokód

Úgy gondoljuk, hogy a tetején az u található : $én(u)$

függvény get_independent_set(u csomópont) { ha az I(u)-t már kiszámoltuk, akkor adja vissza az I(u)-t // a halmaz számossága, amelyet akkor kaphatunk, ha nem vesszük fel az u csúcsot gyermekek_összege = 0 // a halmaz számossága, amelyet az u csúcs felvételével kaphatunk unokák_összege = 0 // hurok az összes gyermeken keresztül for i := 1 - gyermek_szám do children_sum = children_sum + get_independent_set(childs[i]) // hurok az összes unokán keresztül i:= 1-től unokák_számához unokák_összege = unokák_összege + get_independent_set(unokák[i]) // ne feledje, hogy ne számolja újra I(u) = max(1 + unokák_összege, gyermekek_összege) visszatérés I(u) }

A get_independent_set( r ) meghívása megadja a választ a problémára. Az algoritmus végrehajtási ideje nyilvánvalóan O (|V| + |E|).

Lásd még

A Bron-Kerbosh algoritmus a maximális (befoglalással) független csúcshalmazok megtalálására.

Jegyzetek

↑ Chris Godsil, Gordon Royle. . Algebrai gráfelmélet. - New York: Springer , 2001. - ISBN 0-387-95220-9 . — 3. o.
↑ Evstigneev V. A., Kasyanov V. N. . Számítástechnikai grafikonok szótára. - Novoszibirszk, 200. - (Programok tervezése és optimalizálása, 17. szám). - ISBN 978-591124-036-3 .
↑ Moon J. W., Moser L. On cliques in graphs // Israel Journal of Mathematics. - 1965. - 1. évf. 3, sz. 1. - P. 23–28. - doi : 10.1007/BF02760024 .
↑ Furedi Zoltán. A maximálisan független halmazok száma összekapcsolt gráfokban // Journal of Graph Theory. - 1987. - 1. évf. 11, sz. 4. - P. 463-470. - doi : 10.1002/jgt.3190110403 .
↑ Rusov és Zakharova alábbi cikkéből: A közelmúltban a heurisztikus algoritmusok, vagyis azok az algoritmusok, amelyek még mindig lehetővé teszik egy NP-teljes probléma megoldását, de némi hibával, az ilyen jellegű problémák megoldásában voltak a legnagyobb érdeklődésre. A heurisztikus algoritmus kiértékelésének fő kritériumai az "időhatékonyság" és a pontos algoritmushoz viszonyított hiba.
↑ Robson J. M. Algorithms for maximum független halmazok // Journal of Algorithms. - 1986. - 1. évf. 7, sz. 3. - P. 425-440. - doi : 10.1016/0196-6774(86)90032-5 .
↑ Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij. . Alulról felfelé irányuló módszer és gyors algoritmusok MAX FÜGGETLEN HASZNÁLATHOZ // Algoritmuselmélet – SWAT 2010 . - Berlin: Springer , 2010. - (Lecture Notes in Computer Science, 6139. köt.). - doi : 10.1007/978-3-642-13731-0_7 . — P. 62–73.
↑ Chiba N., Nishizeki T. Arboricitás és részgráfok listázási algoritmusai // SIAM Journal on Computing . - 1985. - 1. évf. 14. sz. 1. - P. 210-223. - doi : 10.1137/0214017 .
↑ Piotr Berman, Toshihiro Fujito. . A független halmazprobléma közelítési tulajdonságairól 3. fokozatú gráfokhoz // Negyedik Nemzetközi Algoritmusok és Adatstruktúrák Workshop. - Springer , 1995. - (Lecture Notes in Computer Science, 995. kötet). - doi : 10.1007/3-540-60220-8_84 . - P. 449-460.
↑ Halldórsson M. M., Radhakrishnan J. A kapzsiság jó: Független halmazok közelítése ritka és korlátos fokú gráfokban // Algorithmica . - 1997. - 1. évf. 18, sz. 1. - P. 145-163. - doi : 10.1007/BF02523693 . .
↑ Sbihi, 1980 .
↑ Grötschel, Lovász, Schrijver, 1988 .
↑ Brenda S. Baker. Közelítő algoritmusok NP-teljes problémákhoz síkgráfokon // Journal of the ACM . - 1994. - 1. évf. 41. sz. 1. - P. 153-180. - doi : 10.1145/174644.174650 .
↑ Martin Grohe. Helyi faszélesség, kizárt mellékek és közelítő algoritmusok // Combinatorica . - 2003. - 20. évf. 23. sz. 4. - P. 613-632. - doi : 10.1007/s00493-003-0037-9 .

Irodalom

Chris Godsil, Gordon Royle. . Algebrai gráfelmélet. - New York: Springer , 2004. - ISBN 0-387-95220-9 .
Grötschel M., Lovász L., Schrijver A. . 9.4. Tökéletes grafikonok színezése // Geometriai algoritmusok és kombinatorikus optimalizálás. - Springer , 1988. - (Algoritmusok és kombinatorikák, 2. kötet). — ISBN 0-387-13624-X . - P. 296-298.
Karp, Richard. Redukálhatóság a kombinatorikus problémák között // Proceedings of a Symposium on the Complexity of Computer Computations. – 1972.
Michael R. Garey, David S. Johnson. . Számítógépek és kezelhetetlenség: Útmutató az NP-teljesség elméletéhez . - W. H. Freeman, 1979. - ISBN 0-7167-1045-5 .
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. . 6. fejezet Dinamikus programozás // Algoritmusok. — McGraw-Hill Science/Engineering/Math, 2006. — ISBN 0073523402 . — 336. o.
Sbihi, Najiba Sbihi. Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile // Discrete Mathematics. - 1980. - 1. évf. 29. sz. 1. - P. 53–76. - doi : 10.1016/0012-365X(90)90287-R .

Linkek

Weisstein, Eric W. Maximális független csúcskészlet a Wolfram MathWorldnél .
Kihívást jelentő mércék a maximális kattintáshoz, a maximális független készlethez, a minimális csúcsfedéshez és a csúcsszínezéshez
Polikarpova N., Gerasimenko A. Nehéz problémák megoldásának módszerei
Dinamikus programozási előadás diák
Videó előadások a dinamikus programozásról
Rusov V.S., Zakharova D.A. Heurisztikus algoritmus a gráf maximális súlytól független csúcskészletének megtalálásához

NP-teljes problémák
A halmozás (csomagolás) maximalizálási problémája	Csomagolás konténerekbe kétdimenziós csomagolás lineáris csomagolás súly szerinti csomagolás érték szerinti csomagolás A hátizsák probléma
gráfelmélet halmazelmélet	Csúcsborítási probléma Kattintson a probléma Egy független halmaz (halmaz) problémája Állítsa be a fedési problémát Steiner probléma Az utazó eladó probléma Általános utazó eladó probléma
Algoritmikus problémák	Kielégíthetőségi probléma Boole-képleteknél (konjunktív normál formában)
Logikai játékok és rejtvények	Általános címkék (játék N 2 -1-ben) legrövidebb megoldási probléma Problémák, amelyek megoldásait a Tetrisben alkalmazzák Általános Sudoku probléma Latin négyzet kitöltési probléma Kakuro feladata
Nehézségi osztályok Operációkutatás Optimalizálás Kombinatorikus optimalizálás Alkalmazott matematika Algoritmusok elmélete Dinamikus programozás 21 NP-teljes Karp probléma