Független csúcshalmaz

A kilenc kék csúcs az általánosított Petersen-gráf GP(12,4) egy maximális független halmazát jelöli.

A matematika, azon belül a gráfelmélet területén egy független csúcshalmaz, független ponthalmaz, független halmaz (independent set) vagy stabil halmaz (stable set) egy gráf olyan csúcsainak halmaza, melyek közül semelyik kettő sem szomszédos egymással. Tehát a csúcsok olyan S halmaza, hogy bármelyik két S-beli csúcsot tekintve állítható, hogy nincs közöttük él. Ezzel ekvivalens állítás, hogy a gráf minden élének legfeljebb egy végpontja található S-ben. A független halmaz méretén az azt alkotó csúcsok számát értjük. A független halmazokat nevezik belsőleg stabil halmazoknak (internally stable sets) is.[1]

Egy maximális független halmaz (maximal independent set) olyan halmaz, melyhez vagy bármely csúcsot hozzáadva biztosan tartalmazni fog egy élet is, vagy az üres gráf összes csúcsát tartalmazza.

Egy adott G gráfhoz tartozó maximális független halmazok nevükkel ellentétben nagyon különböző méretűek lehetnek. A maximális független halmazok közül a maximális elemszámú független halmaz az adott G gráfhoz tartozó legnagyobb lehetséges méretű halmaz. Ezt a méretet nevezik G függetlenségi számának (independence number), jelölése α(G).[2] Az ilyen halmaz előállításának a problémája, a maximális elemszámú független csúcshalmaz-probléma (maximum independent set problem) NP-nehéz optimalizálási feladat. Így hát valószínűtlen, hogy létezik hatékony algoritmus egy gráf maximális elemszámú független csúcshalmazának meghatározására.

A maximális elemszámú független csúcshalmazok (maximum independent set) minden esetben maximális független csúcshalmazok is (maximal independent set), az állítás megfordítása azonban nem áll fenn.

Tulajdonságai

Más gráfparaméterekkel való kapcsolata

Egy csúcshalmaz akkor és csak akkor független, ha a gráf komplementerében klikket alkot, tehát a két fogalom egymás komplementerének tekinthető. Valójában azok az elegendően nagy gráfok, melyek nem rendelkeznek nagy klikkekkel, biztosan rendelkeznek nagy független csúcshalmazokkal, ami a Ramsey-elmélet egy fontos témája.

Egy csúcshalmaz akkor és csak akkor független, ha komplementere csúcslefedést alkot. Tehát az α(G) maximális elemszámú független halmaz és a β(G) minimális csúcslefedés összege éppen megegyezik a gráf csúcsainak számával.

Egy G gráf csúcsszínezésén annak csúcsainak független halmazokba való particionálását értjük. Tehát a csúcsszínezéshez minimálisan szükséges színek száma, azaz a χ(G) kromatikus szám nagyobb vagy egyenlő G csúcsai számának és α(G) függetlenségi számának hányadosával.

Egy izolált csúcsokat nem tartalmazó páros gráfban a maximális elemszámú független halmaz elemszáma megegyezik a minimális éllefedés éleinek számával; ez a König-tétellel ekvivalens állítás.

Maximális független halmaz

Bővebben: Maximális független halmaz

Egy maximális független halmaz olyan független halmaz, ami nem valódi részhalmaza egyetlen független halmaznak sem. Az ilyen halmazok minden esetben domináló halmazok. Egy gráf legfeljebb 3n/3 maximális független halmazt tartalmazhat,[3] de a legtöbb gráfnak ennél jóval kevesebb van. Az n-csúcsú körgráfok maximális független halmazainak számát a Perrin-számok sorozata adja meg, míg az n-csúcsú útgráfokét pedig a Padovan-sorozat.[4] Így tehát mindkét szám a „plasztikus szám”, azaz 1,324718 hatványaival arányosan növekszik.

Független halmazok keresése

A számítástudomány számos, a független csúcshalmazokhoz kapcsolódó számítási problémát tart számon.

  • A maximális elemszámú független halmaz-problémában (maximum independent set) a bemenet egy irányítatlan gráf, a kimenet pedig a gráf egy maximális elemszámú független csúcshalmaza. Ha több ilyen is létezik, elegendő egynek szerepelnie a kimenetben. A problémát néha csúcspakolásnak (vertex packing) is nevezik.
  • A maximális súlyú független halmaz-problémában (maximum-weight independent set) a bemenet egy irányítatlan, a csúcsain súlyozott gráf, a kimenet pedig egy maximális súlyú, független csúcshalmaz. Az előző probléma ennek egy speciális esete, ahol minden súly értéke 1.
  • A maximális független csúcshalmaz listázása-problémában (maximal independent set listing) a bemenet egy irányítatlan gráf, a kimenet pedig az összes maximális független csúcshalmazainak listája. A probléma megoldása közben természetes módon előáll a maximális elemszámú független halmaz-probléma megoldása is.
  • A független halmaz eldöntése-problémában (independent set decision) a bemenet egy irányítatlan gráf és egy k szám, a kimenet pedig egy logikai érték: igaz, ha a gráf tartalmaz k méretű független csúcshalmazt, egyébként hamis.

Az első három problémának fontos gyakorlati alkalmazásai vannak; az eldöntési problémának nincsen, de szükséges felvetni annak érdekében, hogy az NP-teljesség elméletét alkalmazni lehessen a független csúcshalmazokat érintő problémákban.

Maximális elemszámú független halmazok és maximális elemszámú klikkek

A maximális elemszámú független halmaz-probléma és a maximális elemszámú klikkek problémája egymás komplementerei: G egy klikkje G komplementer gráfjának független csúcshalmaza, és vice versa. Ezért sok számítástudományi eredmény egyformán jól alkalmazható mindkét problémára. Például a klikkproblémára érvényes eredmények az alábbi következményekkel is járnak:

  • A független halmaz eldöntése-probléma NP-teljes, ezért úgy gondoljuk, nem létezik hatékony algoritmus a megoldására.
  • A maximális elemszámú független halmaz-probléma NP-nehéz, ráadásul közelítő megoldást is nehéz találni rá.

Annak ellenére, hogy a maximális elemszámú független halmazok és a maximális elemszámú klikkek problémája általános gráfokban közeli rokonságban állnak, egyes speciális gráfosztályokban a két probléma nagyon különböző lehet. Például ritka gráfokban (ahol az élek száma bármely részgráfban legfeljebb konstansszorosa a csúcsok számának) a maximális elemszámú klikk mérete korlátos és lineáris időben megtalálható;[5] ugyanakkor a ritka gráfok, sőt a még speciálisabb korlátos fokszámú gráfok esetében a maximális elemszámú független halmazok megkeresése MAXSNP-teljes, ami azt jelenti, hogy adott c konstansra (a fokszámtól függően) NP-nehéz olyan közelítő megoldást találni, ami az optimálist c faktorral megközelíti.[6]

Maximális elemszámú független halmazok keresése

Lásd még: klikkprobléma

Pontos algoritmus

A maximális elemszámú független halmaz megkeresése NP-nehéz probléma. Mindazonáltal a naiv brute-force keresés O(n2 2n) idejénél (ti. ha minden csúcshalmazt egyenként megvizsgálunk, hogy az vajon független csúcshalmaz-e) hatékonyabb algoritmusok is léteznek a feladatra.

(Robson 1986) egy algoritmusa O(1,2108n) időben oldja meg, ha exponenciális tér áll rendelkezésre. Polinomiális térre korlátozva létezik egy O(1,2127n) algoritmus,[7] ami az egyszerűbb O(1,2209n) algoritmus továbbfejlesztése.[8]

Sok gráfosztály esetében a maximális súlyú független csúcshalmaz polinomiális időben megtalálható. Jellemző példák erre a karommentes gráfok,[9] a P5-mentes gráfok[10] és a perfekt gráfok.[11] A merevkörű gráfoknál a maximális súlyú független csúcshalmaz lineáris időben megtalálható.[12]

A moduláris dekompozíció hatékony eszköz a maximális súlyú független csúcshalmaz-probléma megoldására; jó példa erre a kográfokon lineáris idejű algoritmus. Másik fontos eszköz a Tarjan által leírt klikkszeparátor.[13]

Egy páros gráfban a minimális csúcslefedésben nem szereplő csúcsok hozzátehetők a maximális elemszámú független csúcshalmazhoz; lásd a König-tételt. Ezért a minimális csúcslefedés megtalálható a páros gráf párosítási algoritmusával.

Közelítő algoritmusok

Általában a maximális elemszámú független halmaz problémája nem approximálható konstans faktor erejéig sem polinomiális időben (kivéve, ha P = NP). Sőt, általánosságban Poly-APX-teljes, tehát olyan nehéz, mint bármely polinomiális faktorral approximálható probléma.[14] Egyes speciális gráfosztályokra azonban léteznek hatékony közelítési algoritmusok.

Síkgráfok maximális elemszámú független halmazai c < 1 approximációs faktorral polinomiális időben számíthatók; hasonló polinomiális approximációs sémák léteznek bármely gráfminorképzésre zárt gráfcsalád esetében.[15]

Korlátos fokszámú gráfokban léteznek hatékony approximációs algoritmusok, melyek a maximális fokszámtól függő konstans approximációs rátával rendelkeznek; például egy mohó algoritmus, ami úgy találja meg a maximális elemszámú független halmazt, hogy minden lépésben kiválaszt egy minimális fokszámú csúcsot a gráfban és eltávolítja a szomszédait, Δ maximális fokszámú gráfban (Δ+2)/3 approximációs rátát ér el.[16] Az ilyen esetek approximációjának a nehézségére (Berman & Karpinski 1999) határozott meg korlátokat. Még a 3-reguláris, 3 színnel színezhető gráfokra is APX-teljes a probléma.[17]

Intervallumgráfok független csúcshalmazai

Bővebben: Intervallum-ütemezés

Egy intervallumgráf olyan gráf, melynek csúcsai 1 dimenziós intervallumok (pl. időintervallumok), melyek között akkor van él, ha a két intervallum metszi egymást. Egy intervallumgráf független csúcshalmaza egyszerűen egymást nem átfedő intervallumokból áll. Az intervallumgráfok független csúcshalmazai keresésének problémáját például a feladatütemezés kontextusában vizsgálták: ha adott futtatandó feladatok egy halmaza, keressük meg azt a maximális halmazt ezek közül, melyek az egymással való interferálás veszélye nélkül lefuttathatók. Ez a probléma pontosan polinomiális időben megoldható a legkorábbi határidő szerinti ütemezés (wd) alkalmazásával.

Mértani metszetgráfok független csúcshalmazai

Bővebben: Maximális diszjunkt halmaz

Egy mértani metszetgráf esetében a csúcsok mértani alakzatok, és két mértani alakzatot reprezentáló csúcs között pontosan akkor van él, ha az alakzatoknak van közös pontjuk. Egy mértani metszetgráf esetén tehát a független csúcshalmaz át nem fedő mértani alakzatok összessége. Ezek keresését tanulmányozták többek közt a térképek automatikus címkézésének kontextusában: ha adott a térképen helyek egy halmaza, keressük a környezetükben egymást át nem fedő téglalap alakú címkék elhelyezésének maximális lehetőségét.

A metszetgráfok maximális elemszámú független csúcshalmazának megtalálása NP-teljes, de még mindig könnyebb probléma, mint az általános gráfok esetében. A témát körüljárják a (Chan & Har-Peled 2012) előszavában.

Maximális független csúcshalmaz megkeresése

Bővebben: Maximális független csúcshalmaz

A maximális (nem maximális elemszámú!) független csúcshalmaz megkeresése polinomiális időben végrehajtható egy triviális mohó algoritmussal.[18] Az összes maximális független csúcshalmaz O(3n/3) = O(1,4423n) időben megkereshető.

Maximális elemszámú független csúcshalmazokat kereső programok

Név Licenc API nyelve Rövid leírás
igraph Archiválva 2014. február 14-i dátummal a Wayback Machine-ben GPL C, Python, R, Ruby Pontos megoldás. "The current implementation was ported to igraph from the Very Nauty Graph Library by Keith Briggs and uses the algorithm from the paper S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm for generating all the maximal independent sets. SIAM J Computing, 6:505–517, 1977".
NetworkX BSD Python Közelítő megoldás a következő rutinnal: maximum_independent_set
OpenOpt BSD Python Pontos és közelítő megoldások, megadhatók a csomópontok, amiket feltétlenül
tartalmaznia / kihagyni kell; lásd STAB további példákért és részletekért

Kapcsolódó szócikkek

  • A független élhalmaz élek olyan halmaza a gráfban, melyek nem rendelkeznek közös csúccsal. Általában párosításnak nevezik.
  • Egy csúcsszínezés a gráf csúcsainak független halmazokba való particionálása.

Jegyzetek

  1. ↑ (Korshunov 1974)
  2. ↑ (Godsil & Royle 2001), p. 3.
  3. ↑ (Moon & Moser 1965).
  4. ↑ (Füredi 1987).
  5. ↑ (Chiba & Nishizeki 1985).
  6. ↑ (Berman & Fujito 1995).
  7. ↑ (Bourgeois et al. 2010)
  8. ↑ (Fomin, Grandoni & Kratsch 2009)
  9. ↑ (Minty 1980),(Sbihi 1980),(Nakamura & Tamura 2001),(Faenza, Oriolo & Stauffer 2014),(Nobili & Sassano 2015)
  10. ↑ (Lokshtanov, Vatshelle & Villanger 2014)
  11. ↑ (Grötschel, Lovász & Schrijver 1988)
  12. ↑ (Frank 1976)
  13. ↑ (Tarjan 1985)
  14. ↑ (2005. június 30.) „Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness”. Theoretical Computer Science 339 (2–3), 272–292. o. DOI:10.1016/j.tcs.2005.03.007.  
  15. ↑ (Baker 1994); (Grohe 2003).
  16. ↑ (Halldórsson & Radhakrishnan 1997).
  17. ↑ (2003. június 30.) „Approximation Hardness for Small Occurrence Instances of NP-Hard Problems”. Proceedings of the 5th International Conference on Algorithms and Complexity.  
  18. ↑ (Luby 1986).
  • Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM 41 (1): 153–180, DOI 10.1145/174644.174650.
  • Berman, Piotr & Fujito, Toshihiro (1995), "On approximation properties of the Independent set problem for degree 3 graphs", Workshop on Algorithms and Data Structures, vol. 955, Lecture Notes in Computer Science, Springer-Verlag, pp. 449–460, ISBN 978-3-540-60220-0, DOI 10.1007/3-540-60220-8_84.
  • Berman, Piotr & Karpinski, Marek (1999), "On some tighter inapproximability results", Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague, vol. 1644, Lecture Notes in Computer Science, Prague: Springer-Verlag, pp. 200–209, ISBN 978-3-540-66224-2, DOI 10.1007/3-540-48523-6
  • Bourgeois, Nicolas; Escoffier, Bruno & Paschos, Vangelis Th. et al. (2010), A bottom-up method and fast algorithms for MAX INDEPENDENT SET, "Algorithm theory—SWAT 2010", Algorithm Theory – SWAT 2010, Lecture Notes in Computer Science (Berlin: Springer) 6139: 62–73, ISBN 978-3-642-13730-3, DOI 10.1007/978-3-642-13731-0_7.
  • Chan, T. M. (2003), "Polynomial-time approximation schemes for packing and piercing fat objects", Journal of Algorithms 46 (2): 178–189, DOI 10.1016/s0196-6774(02)00294-8.
  • Chan, T. M. & Har-Peled, S. (2012), "Approximation algorithms for maximum independent set of pseudo-disks", Discrete & Computational Geometry 48 (2): 373, DOI 10.1007/s00454-012-9417-5.
  • Chiba, N. & Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing 14 (1): 210–223, DOI 10.1137/0214017.
  • Erlebach, T.; Jansen, K. & Seidel, E. (2005), "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs", SIAM Journal on Computing 34 (6): 1302, DOI 10.1137/s0097539702402676.
  • Faenza, Y.; Oriolo, G. & Stauffer, G. (2014), "Solving the Weighted Stable Set Problem in Claw-Free Graphs", Journal of the ACM 61 (4): 1–41, DOI 10.1145/2629600.
  • Fomin, Fedor V.; Grandoni, Fabrizio & Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of ACM 56 (5): 1–32, DOI 10.1145/1552285.1552286.
  • Frank, Andras (1976), "Some polynomial algorithms for certain graphs and hypergraphs", Congressus Numerantium XV: 211–226.
  • Füredi, Z. (1987), "The number of maximal independent sets in connected graphs", Journal of Graph Theory 11 (4): 463–470, DOI 10.1002/jgt.3190110403.
  • Godsil, Chris & Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer, ISBN 0-387-95220-9.
  • Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica 23 (4): 613–632, DOI 10.1007/s00493-003-0037-9.
  • Grötschel, M.; Lovász, L. & Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, vol. 2, Algorithms and Combinatorics, Springer-Verlag, pp. 296–298, ISBN 0-387-13624-X.
  • Halldórsson, M. M. & Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs", Algorithmica 18 (1): 145–163, DOI 10.1007/BF02523693.
  • Korshunov, A.D. (1974), "Coefficient of Internal Stability", Kibernetika 10 (1): 17–28, DOI 10.1007/BF01069014.
  • Lokshtanov, D.; Vatshelle, M. & Villanger, Y. (2014), "Independent sets in P5-free graphs in polynomial time", SODA (Symposium on Discrete Algorithms): 570–581.
  • Luby, Michael (1986), "A simple parallel algorithm for the maximal independent set problem", SIAM Journal on Computing 15 (4): 1036–1053, DOI 10.1137/0215074.
  • Minty, G.J. (1980), "On maximal independent sets of vertices in claw-free graphs", Journal of Combinatorial Theory Series B 28: 284–304, DOI 10.1016/0095-8956(80)90074-x.
  • Moon, J.W. & Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics 3 (1): 23–28, DOI 10.1007/BF02760024.
  • Nakamura, D. & Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph", Journal of Operations Research Society Japan 44: 194–204.
  • Nobili, P. & Sassano, A. (2015), An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs
  • Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms 7 (3): 425–440, DOI 10.1016/0196-6774(86)90032-5.
  • Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile", Discrete Mathematics 29 (1): 53–76, DOI 10.1016/0012-365X(90)90287-R.
  • Tarjan, R.E. (1985), "Decomposition by clique separators", Discrete Mathematics 55: 221–232, DOI 10.1016/0012-365x(85)90051-2.

Fordítás

  • Ez a szócikk részben vagy egészben az Independent set (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

  • Weisstein, Eric W.: Maximal Independent Vertex Set (angol nyelven). Wolfram MathWorld
  • Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring Archiválva 2013. május 29-i dátummal a Wayback Machine-ben
  • Independent Set and Vertex Cover, Hanan Ayad.
  • Maximum Independent Sets in Graphs – an interactive demo in JavaScript

Jegyzetek