Oberoende uppsättning (grafteori) - Independent set (graph theory)

De nio blå hörnen utgör en maximal oberoende uppsättning för Generalized Petersen -grafen GP (12,4).

I grafteorin är en oberoende uppsättning , stabil uppsättning , coclique eller anticlique en uppsättning hörn i en graf , av vilka inte två ligger intill varandra. Det vill säga, det är en uppsättning hörn så att för varje två hörn i , finns det ingen kant som förbinder de två. På motsvarande sätt har varje kant i grafen högst en slutpunkt i . En uppsättning är oberoende om och bara om det är en klick i grafens komplement . Storleken på en oberoende uppsättning är antalet hörn den innehåller. Oberoende uppsättningar har också kallats "internt stabila uppsättningar", varav "stabila uppsättningar" är en förkortning. ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle S}$

En maximal oberoende uppsättning är en oberoende uppsättning som inte är en korrekt delmängd av någon annan oberoende uppsättning.

En maximal oberoende uppsättning är en oberoende uppsättning med största möjliga storlek för en given graf . Denna storlek kallas självständighetsnummer för och brukar betecknas med . Det optimeringsproblem att hitta en sådan uppsättning kallas maximalt oberoende uppsättning problem. Det är ett starkt NP-hårt problem. Som sådan är det osannolikt att det finns en effektiv algoritm för att hitta en maximal oberoende uppsättning av en graf. ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle \ alpha (G)}$

Varje maximal oberoende uppsättning är också maximal, men den motsatta implikationen håller inte nödvändigtvis.

Egenskaper

Förhållande till andra grafparametrar

En uppsättning är oberoende om och bara om det är en klick i grafens komplement , så de två begreppen är komplementära. Faktum är att tillräckligt stora grafer utan stora klickar har stora oberoende uppsättningar, ett tema som utforskas i Ramsey -teorin .

En uppsättning är oberoende om och endast om dess komplement är en toppunktskydd . Därför är summan av storleken på den största oberoende uppsättningen och storleken på ett minimum vertex -lock lika med antalet hörn i grafen. ${\ displaystyle \ alpha (G)}$ ${\ displaystyle \ beta (G)}$

En hörnfärgning av en graf motsvarar en uppdelning av dess toppunkt i oberoende delmängder. Därför är det minimala antal färger som behövs i en toppunktsfärgning, det kromatiska talet , åtminstone kvoten för antalet hörn i och det oberoende talet . ${\ displaystyle G}$ ${\ displaystyle \ chi (G)}$ ${\ displaystyle G}$ ${\ displaystyle \ alpha (G)}$

I en bipartitgraf utan isolerade hörn är antalet hörn i en maximal oberoende uppsättning lika med antalet kanter i en minsta kantbeläggning ; detta är Kőnigs sats .

Maximal oberoende uppsättning

En oberoende uppsättning som inte är en korrekt delmängd av en annan oberoende uppsättning kallas maximal . Sådana uppsättningar är dominerande uppsättningar . Varje graf innehåller högst 3 ^{n /3} maximala oberoende uppsättningar, men många grafer har mycket färre. Antalet maximala oberoende uppsättningar i n -vertex cyklisk graf ges av perrintal , och antalet maximala oberoende uppsättningar i n -vertex path grafer ges av Padovan sekvensen . Därför båda talen är proportionella mot befogenheter 1.324718 ..., den plastnummer .

Hitta oberoende uppsättningar

Inom datavetenskap har flera beräkningsproblem relaterade till oberoende uppsättningar studerats.

I problemet med maximal oberoende uppsättning är ingången en oriktad graf och utmatningen är en maximal oberoende uppsättning i grafen. Om det finns flera maximala oberoende uppsättningar behöver bara en matas ut. Detta problem kallas ibland " vertexpackning ".
I maximal vikt oberoende uppsättning problem, är den ingående en oriktad graf med vikter på dess hörn och utsignalen är en oberoende uppsättning med maximal totalvikt. Det maximala oberoende inställningsproblemet är specialfallet där alla vikter är ett.
I problemet med maximal oberoende uppsättningslista är ingången en oriktad graf och utmatningen är en lista över alla dess maximala oberoende uppsättningar. Det maximala oberoende uppsättningsproblemet kan lösas genom att använda som en underprogram en algoritm för det maximala oberoende uppsättningsuppgiftsproblemet, eftersom den maximala oberoende uppsättningen måste inkluderas bland alla de maximala oberoende uppsättningarna.
I det oberoende uppsättningsbeslutsproblemet är ingången en oriktad graf och ett tal k , och utmatningen är ett booleskt värde : sant om grafen innehåller en oberoende uppsättning av storlek k , och falskt annars.

De tre första av dessa problem är alla viktiga i praktiska tillämpningar; det oberoende beslutsproblemet är inte, men är nödvändigt för att tillämpa teorin om NP-fullständighet på problem relaterade till oberoende uppsättningar.

Maximala oberoende uppsättningar och maximala klickningar

Det oberoende uppsättningsproblemet och klickproblemet är komplementära: en klick i G är en oberoende uppsättning i komplementdiagrammet för G och vice versa. Därför kan många beräkningsresultat tillämpas lika bra på båda problemen. Resultaten relaterade till klickproblemet har till exempel följande konsekvenser:

Det oberoende beslutsproblemet är NP-komplett , och därför tror man inte att det finns en effektiv algoritm för att lösa det.
Det maximala oberoende inställningsproblemet är NP-hårt och det är också svårt att uppskatta .

Trots det nära sambandet mellan maximala klickningar och maximala oberoende uppsättningar i godtyckliga grafer kan de oberoende uppsättningarna och klickproblemen vara mycket olika när de begränsas till särskilda klasser av grafer. Till exempel, för glesa grafer (grafer där antalet kanter högst är konstanta gånger antalet hörn i någon undergraf), har den maximala klicken begränsad storlek och kan hittas exakt i linjär tid; för samma klasser av grafer, eller till och med för den mer begränsade klassen av gränsade grafer, är det dock MAXSNP-komplett att hitta den maximala oberoende uppsättningen , vilket innebär att det för vissa konstanta c (beroende på graden) är NP-svårt att hitta en ungefärlig lösning som ligger inom en faktor c av det optimala.

Hitta maximalt oberoende uppsättningar

Exakta algoritmer

Det maximala oberoende inställningsproblemet är NP-hårt. Det kan dock lösas mer effektivt än O ( n ² 2 ⁿ ) -tiden som skulle ges av en naiv brute force -algoritm som undersöker varje vertex -delmängd och kontrollerar om det är en oberoende uppsättning.

Från och med 2017 kan det lösas i tid O (1.1996 ⁿ ) med hjälp av polynomrum. När den är begränsad till grafer med maximal grad 3 kan den lösas i tid O (1.0836 ⁿ ).

För många klasser av grafer kan en oberoende uppsättning med maximal vikt hittas under polynomtiden. Kända exempel är klofria grafer , P ₅ -fria grafer och perfekta grafer . För ackordgrafer kan en oberoende maximal viktuppsättning hittas i linjär tid.

Modulär sönderdelning är ett bra verktyg för att lösa det maximala viktoberoende setproblemet; den linjära tidsalgoritmen på cographs är det grundläggande exemplet för det. Ett annat viktigt verktyg är klickseparatorer som beskrivs av Tarjan.

Kőnigs sats antyder att i en bipartitgraf kan den maximala oberoende uppsättningen hittas i polynomtid med hjälp av en bipartitmatchningsalgoritm.

Approximationsalgoritmer

I allmänhet kan det maximala oberoende uppsättningsproblemet inte approximeras till en konstant faktor i polynomtid (om inte P = NP). Faktum är att Max Independent Set i allmänhet är Poly-APX-komplett , vilket betyder att det är lika svårt som alla problem som kan approximeras till en polynomfaktor. Det finns dock effektiva approximationsalgoritmer för begränsade klasser av grafer.

I plana grafer kan den maximala oberoende uppsättningen approximeras till inom varje approximationsförhållande c <1 i polynomtid; liknande schema för tillnärmning av polynomtid finns i alla familjer av grafer som stängs under att ta minderåriga .

I avgränsade grafer är effektiva approximationsalgoritmer kända med approximationsförhållanden som är konstanta för ett fast värde för den maximala graden; till exempel uppnår en girig algoritm som bildar en maximal oberoende uppsättning genom att vid varje steg välja minsta gradens toppunkt i grafen och ta bort dess grannar ett approximationsförhållande på (Δ+2)/3 på grafer med maximal grad Δ. Approximationshårdhetsgränser för sådana fall bevisades i Berman & Karpinski (1999) . Faktum är att även Max Independent Set på 3-vanliga 3-kant-färgbara grafer är APX-komplett .

Oberoende uppsättningar i intervallskärningsgrafer

Ett intervalldiagram är en graf där noder är 1-dimensionella intervall (t.ex. tidsintervall) och det finns en kant mellan två intervall om och bara om de skär varandra. En oberoende uppsättning i ett intervalldiagram är bara en uppsättning icke-överlappande intervall. Problemet med att hitta maximala oberoende uppsättningar i intervalldiagram har studerats, till exempel i samband med jobbplanering : med tanke på en uppsättning jobb som måste utföras på en dator, hitta en maximal uppsättning jobb som kan utföras utan att störa med varandra. Detta problem kan lösas exakt i polynomtid med hjälp av tidigaste tidsplanering första schemaläggning .

Oberoende uppsättningar i geometriska skärningslinjer

En geometrisk skärningslinje är en graf där noder är geometriska former och det finns en kant mellan två former om och bara om de skär varandra. En oberoende uppsättning i en geometrisk skärningslinje är bara en uppsättning av osammanhängande (icke-överlappande) former. Problemet med att hitta maximala oberoende uppsättningar i geometriska skärningslinjer har studerats, till exempel i samband med automatisk etikettplacering : med en uppsättning platser på en karta, hitta en maximal uppsättning av osammanhängande rektangulära etiketter nära dessa platser.

Att hitta en maximal oberoende uppsättning i skärningskort är fortfarande NP-komplett, men det är lättare att approximera än det allmänna maximala oberoende uppsättningsproblemet. En nyligen genomförd undersökning finns i introduktionen av Chan & Har-Peled (2012) .

Hitta maximala oberoende uppsättningar

Problemet med att hitta en maximal oberoende uppsättning kan lösas på polynomtid med en trivial girig algoritm . Alla maximala oberoende uppsättningar kan hittas i tiden O (3 ^{n /3} ) = O (1,4423 ⁿ ).

Programvara för att söka efter maximal oberoende uppsättning

namn	Licens	API -språk	Kort info
igraph	GPL	C, Python, R, Ruby	exakt lösning. "Den nuvarande implementeringen portades till igraph från Very Nauty Graph Library av Keith Briggs och använder algoritmen från tidningen S. Tsukiyama, M. Ide, H. Ariyoshi och I. Shirawaka. En ny algoritm för att generera alla maximala oberoende uppsättningar . SIAM J Computing, 6: 505–517, 1977 ".
LightGraphs	MIT	Julia	exakt lösning. Se dokumentationen för mer information.
NetworkX	BSD	Pytonorm	ungefärlig lösning, se rutinen maximum_independent_set
mis	Öppen	Rost (binärer)	ungefärlig lösning genom slumpmässig provtagning av maximalt oberoende uppsatt utrymme, se webbsida för mer information

Ansökningar

Den maximala oberoende uppsättningen och dess dubbla, det minimala toppunktsprovet , är involverat i att bevisa beräkningskomplexiteten hos många teoretiska problem. De fungerar också som användbara modeller för verkliga optimeringsproblem, till exempel minsta oberoende uppsättning är en användbar modell för att upptäcka stabila genetiska komponenter för att designa konstruerade genetiska system .

Se även

En oberoende uppsättning kanter är en uppsättning kanter av vilka inga två har en toppunkt gemensamt. Det brukar kallas en matchning .
En vertexfärgning är en uppdelning av vertexuppsättningen i oberoende uppsättningar.

Anteckningar

Referenser

Baker, Brenda S. (1994), "Approximation algoritms for NP-complete problems on planar graphs", Journal of the ACM , 41 (1): 153–180, doi : 10.1145/174644.174650 , S2CID 9706753.
Berman, Piotr; Fujito, Toshihiro (1995), "On approximation properties of the Independent set problem for degree 3 graphs", Workshop on Algorithms and Data Structures , Lecture Notes in Computer Science, 955 , Springer-Verlag , s. 449–460, doi : 10.1007 /3-540-60220-8_84 , ISBN 978-3-540-60220-0.
Berman, Piotr; Karpinski, Marek (1999), "On some tighter inapproximability results", Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague , Lecture Notes in Computer Science , 1644 , Prague: Springer-Verlag , s. 200–209, doi : 10.1007/3-540-48523-6 , ISBN 978-3-540-66224-2, S2CID 23288736
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th .; van Rooij, Johan MM (2010), "En bottom-up-metod och snabba algoritmer för MAX INDEPENDENT SET", Algorithm theory-SWAT 2010 , Lecture Notes in Computer Science, 6139 , Berlin: Springer, s. 62–73, Bibcode : 2010LNCS.6139 ... 62B , doi : 10.1007/978-3-642-13731-0_7 , ISBN 978-3-642-13730-3, MR 2678485.
Chan, TM (2003), "Polynomial gången tillnärmning system för packning och piercing fett objekt", Journal of Algorithms , 46 (2): 178-189, CiteSeerX 10.1.1.21.5344 , doi : 10,1016 / s0196-6774 (02 ) 00294-8.
Chan, TM ; Har-Peled, S. (2012), "Approximation algoritms for maximum independent set of pseudo-disks", Discrete & Computational Geometry , 48 (2): 373, arXiv : 1103.1431 , CiteSeerX 10.1.1.219.2131 , doi : 10.1007/ s00454-012-9417-5 , S2CID 38183751.
Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph listing algoritms", 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 ACM , 61 (4): 1–41, doi : 10.1145/2629600 , S2CID 1995056.
Fomin, Fedor V .; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms ", Journal of the ACM , 56 (5): 1–32, doi : 10.1145/1552285.1552286 , S2CID 1186651 , artikelnr. 25CS1 maint: postscript ( länk ).
Frank, Andras (1976), "Några polynomalgoritmer för vissa grafer och hypergrafer", Congressus Numerantium , XV : 211–226.
Füredi, Z. (1987), "Antalet maximala oberoende uppsättningar i anslutna grafer", 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 978-0-387-95220-8.
Grohe, Martin (2003), "Lokal trädbredd, uteslutna minderåriga och approximationsalgoritmer", Combinatorica , 23 (4): 613–632, arXiv : math/0001128 , doi : 10.1007/s00493-003-0037-9 , S2CID 11751235.
Grötschel, M .; Lovász, L .; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization , Algorithms and Combinatorics, 2 , Springer-Verlag , s. 296–298, ISBN 978-0-387-13624-0.
Halldórsson, MM; Radhakrishnan, J. (1997), "Girighet är bra: Approximera oberoende uppsättningar i gles och avgränsas-graders grafer", Algorithmica , 18 (1): 145-163, CiteSeerX 10.1.1.145.4523 , doi : 10,1007 / BF02523693 , S2CID 4661668.
Korshunov, AD (1974), "Coefficient of Internal Stability", Kibernetika (på ukrainska), 10 (1): 17–28, doi : 10.1007/BF01069014 , S2CID 120343511.
Lokshtanov, D .; Vatshelle, M .; Villanger, Y. (2014), "Oberoende uppsättningar i P ₅ -fria grafer i polynomtid", SODA (Symposium on Discrete Algorithms ) : 570–581.
Luby, Michael (1986), "En enkel parallell algoritm för det maximala oberoende uppsättningsproblemet", SIAM Journal on Computing , 15 (4): 1036–1053, CiteSeerX 10.1.1.225.5475 , doi : 10.1137/0215074 , MR 0861369.
Minty, GJ (1980), "Om maximala oberoende uppsättningar av hörn i klofria grafer", Journal of Combinatorial Theory, Series B , 28 (3): 284–304, doi : 10.1016/0095-8956 (80) 90074- x.
Moon, JW; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics , 3 (1): 23–28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414.
Nakamura, D .; Tamura, A. (2001), "En översyn av Mintys algoritm för att hitta en maximal viktstabil uppsättning i en klorös graf", Journal of Operations Research Society Japan , 44 (2): 194–204, doi : 10.15807/jorsj .44.194.
Nobili, P .; Sassano, A. (2015), En O (n^2 log n) algoritm för det vägda stabila uppsättningsproblemet i klofria grafer , arXiv : 1501.05775 , Bibcode : 2015arXiv150105775N
Robson, JM (1986), "Algoritmer för maximalt oberoende uppsättningar", 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", Diskret matematik (på franska), 29 (1): 53–76, doi : 10.1016/0012-365X (90 ) 90287-R , MR 0553650.
Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exakta algoritmer för maximal oberoende uppsättning", Information och beräkning , 255 : 126–146, arXiv : 1312.6260 , doi : 10.1016/j.ic.2017.06.001 , S2CID 1714739.
Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Konfigurera uppsättningar och undvika flaskhalsfall: En enkel maximal oberoende uppsättningsalgoritm i grad-3-grafer", Teoretisk datavetenskap , 469 : 92–104, doi : 10.1016/j.tcs.2012.09.022.
Tarjan, RE (1985), "Sönderfall med klickseparatorer", Diskret matematik , 55 (2): 221–232, doi : 10.1016/0012-365x (85) 90051-2.

Languages

In other projects