Problém nezávislé množiny

Problém nezávislých množin patří do třídy NP-úplných problémů v oblasti teorie grafů . Ekvivalent k problému kliky .

Definice

Množina vrcholů v grafu se nazývá nezávislá , pokud žádné dva vrcholy této množiny nejsou spojeny hranou. Jinými slovy, podgraf indukovaný touto množinou sestává z izolovaných vrcholů. Někdy se také říká, že každá hrana grafu dopadá na nejvýše jeden vrchol z nezávislé množiny. Problém rozpoznávání (problém rozhoditelnosti) vypadá takto: má daný graf G nezávislou množinu velikosti k ? Jemu odpovídající optimalizační problém, známý také jako problém nezávislých množin , je formulován následovně: v daném grafu G je třeba najít nezávislou množinu maximální velikosti. Tato velikost se nazývá číslo nezávislosti , číslo vnitřní hustoty nebo vůli a označuje se jako [1] [2] .

Tento problém je někdy označován jako nalezení největší nezávislé sady . Tento koncept by se neměl zaměňovat s maximální nezávislou množinou nebo maximální nezávislou množinou inkluzí , která je definována jako taková nezávislá množina vrcholů, ke které když je přidán další (jakýkoli) vrchol původního grafu, přestane být nezávislé (obecně řečeno, takových sad může být několik a různých velikostí). Nezávislá množina inkluzního maxima není v žádném případě vždy největší. Přitom každá největší nezávislá množina je z definice také maximální inkluzí. K nalezení (nějaké) maximální nezávislé množiny s ohledem na inkluzi lze použít chamtivý algoritmus , který běží v polynomiálním čase, zatímco problém největší nezávislé množiny patří do třídy NP-úplných problémů.

Nezávislá množina inkluze-maximální je dominantní množina . Libovolný graf obsahuje maximálně 3 n /3 inkluzně-maximálních nezávislých množin [3] , ale většina grafů jich má mnohem méně.

Počet nezávislých množin inkluze-maximální v cyklech n vrcholů je Perrinova čísla a počet nezávislých množin inkluze-maximální v cestách s n vrcholy je dán Padovanovou sekvencí [4] . Obě čísla jsou tedy úměrná mocnině 1,324718, plastovému číslu .

Nejmenší nezávislá podmnožina v grafu je jakýkoli vrchol tohoto grafu.

Vztah k ostatním parametrům grafu

Množina je nezávislá právě tehdy, když je klikou v doplňku grafu , takže se tyto dva pojmy vzájemně doplňují. Dostatečně velké grafy bez velkých klik mají velké nezávislé množiny, což je předmětem studia Ramseyovy teorie .

Množina je nezávislá právě tehdy, když je jejím doplňkem kryt vrcholu . Součet čísla nezávislosti a krycího čísla vrcholu se rovná počtu vrcholů v grafu (první Gallaiova identita ).

Zbarvení vrcholů grafu odpovídá rozdělení jeho vrcholů do nezávislých podmnožin. Minimální počet barev potřebný k obarvení vrcholů, chromatické číslo , tedy není menší než podíl počtu vrcholů a čísla nezávislosti .

V bipartitních grafech , které nemají žádné izolované vrcholy, je počet vrcholů v největší nezávislé množině roven počtu hran v nejmenším pokrytí hran (důsledek Königovy věty ).

Hledat nezávislé množiny

V informatice se studuje několik výpočetních problémů souvisejících s nezávislými množinami:

První tři problémy jsou důležité v praktických aplikacích, zatímco poslední je důležitý pro teorii NP-úplnosti pro problémy související s nezávislými množinami.

Problém nezávislé množiny a problém kliky jsou duální: klika v G  je nezávislá množina v doplňku G a naopak. Mnoho výpočtových výsledků lze tedy stejně dobře aplikovat na oba problémy. Například výsledky spojené s problémem kliky mají následující důsledky:

Hledání největší nezávislé množiny

Tento problém je někdy označován jako „ balení vrcholů “.

Problém největší nezávislé množiny a problém největší kliky jsou polynomiálně ekvivalentní – největší nezávislou množinu lze najít nalezením maximální kliky v doplňku grafu, takže mnoho autorů se o oddělení těchto dvou problémů nijak zvlášť nestará. Oba problémy jsou NP-úplné, takže je nepravděpodobné, že budou vyřešeny v polynomiálním čase. Problém s největší nezávislou množinou však lze vyřešit efektivněji než v čase O( n 2  2 n ), což poskytuje vyčerpávající hledání , které testuje všechny podmnožiny vrcholů, aby se zjistilo, zda se jedná o nezávislé množiny. Robsonův algoritmus [6] řeší problém v čase O(2 0,276 n ) pomocí exponenciálního prostoru. Pokud existuje omezení velikosti (polynomiální prostor), existuje algoritmus pro řešení v čase O*(1,2127 n ) [7] .

Navzdory úzkému vztahu mezi největší klikou a největší nezávislou množinou v libovolném grafu se problémy s nalezením nezávislé množiny a kliky mohou při řešení na speciální třídě grafů výrazně lišit. Například pro řídké grafy (grafy, ve kterých počet hran v žádném podgrafu není větší než počet vrcholů vynásobený nějakou konstantou) má největší klika omezenou velikost a lze ji najít přesně v lineárním čase [8] . Avšak pro stejné třídy grafů, nebo dokonce pro případ přísnějších omezení pro třídu grafů s omezeným stupněm, je hledání největší nezávislé množiny MAXSNP-complete , což znamená, že pro nějakou konstantu c (v závislosti na na stupni) NP - je obtížné najít přibližné řešení, které se liší faktorem c od optimálního [9] . Jsou však známy efektivní přibližné algoritmy, ale jejich garantovaná účinnost je horší než tento práh. Například chamtivý algoritmus vytvoří nezávislou množinu zahrnutí maxima výběrem vrcholu s minimálním stupněm v každém kroku a odstraněním jeho sousedů. Tento algoritmus dosahuje garantované účinnosti (Δ+2)/3 na grafech s maximálním stupněm Δ [10] .

V některých třídách grafů (včetně grafů bez drápů [11] a dokonalých grafů [12] ; do druhé třídy patří i stromy ) lze největší nezávislou množinu nalézt v polynomiálním čase. Pro rovinné grafy zůstává problém největší nezávislé množiny NP-úplný pro přesné řešení, ale lze jej aproximovat s jakoukoli zaručenou účinností c  < 1 v polynomiálním čase. Podobná přibližná polynomiální časová schémata existují v jakékoli rodině mírně uzavřených grafů [13] [14] .

V bipartitních grafech mohou být všechny vrcholy, které nejsou v nejmenším vrcholovém pokrytí, zahrnuty do největší nezávislé množiny (viz Königův teorém ). Proto lze největší nezávislou množinu nalézt pomocí algoritmu pro nalezení největších shod v bipartitních grafech.

Hledání nezávislých množin inkluze-maximální

Všechny nezávislé množiny inkluze-maximální lze nalézt v čase O(3 n /3 ).

Software pro hledání nezávislých množin

název Licence API jazyk Popis
igraf GPL C, Python, R, Ruby přesné řešení
NetworkX BSD Krajta přibližné řešení, viz postup maximum_independent_set
openopt BSD Krajta přesná a přibližná řešení, schopnost specifikovat vrcholy, které by měly být zahrnuty / vyloučeny. Podrobnosti a příklady viz třída STAB

Největší nezávislá sada ve stromu

Pokud je daný graf strom , pak je problém nezávislé množiny efektivně vyřešen dynamickým programováním .

Optimální podstruktura problému

Struktura stromu sama o sobě naznačuje řešení problému. Jakýkoli vrchol totiž označíme jako kořen stromu a nazýváme jej . Označme velikost největší nezávislé množiny vrcholů podstromu, jehož kořenem je vrchol . Pak bude odpověď na problém .

Je snadné vidět, že pokud zahrneme vrchol u do největší nezávislé množiny, pak se jeho mohutnost zvýší o 1, ale nemůžeme vzít jeho potomky (protože jsou spojeny hranou s vrcholem u ); pokud tento vrchol nezahrneme, pak mohutnost největší nezávislé množiny bude rovna součtu velikostí nezávislých množin potomků tohoto vrcholu. Zbývá pouze vybrat maximum z těchto dvou možností, abyste získali řešení problému:

kde vnuk označuje jakéhokoli „vnuka“ vrcholu a dítě označuje jakéhokoli potomka vrcholu.

Pseudokód

Uvažujeme, že nahoře u je uloženo :

funkce get_independent_set(Uzel u) { pokud I(u) již bylo vypočteno, vraťte I(u) // mohutnost množiny, kterou lze získat, pokud nebereme vrchol u dětský_součet = 0 // mohutnost množiny, kterou lze získat převzetím vrcholu u součet_vnoučat = 0 // procházet všemi dětmi for i := 1 to child_num do children_sum = children_sum + get_independent_set(children[i]) // procházet všemi vnoučaty for i:= 1 to grandchildren_num vnoučata_součet = vnoučata_součet + get_independent_set(vnoučata[i]) // zapamatujte si, abyste se znovu nepřepočítali I(u) = max(1 + součet_vnoučat, součet_dětí) vrátit já(u) }

Volání get_independent_set( r ) dá odpověď na problém. Doba provádění algoritmu je zjevně O (|V| + |E|).

Viz také

Poznámky

  1. ↑ Chris Godsil, Gordon Royle. . Algebraická teorie grafů. - New York: Springer , 2001. - ISBN 0-387-95220-9 .  — str. 3.
  2. ↑ Evstigneev V. A., Kasjanov V. N. . Slovník grafů v informatice. - Novosibirsk, 200. - (Návrh a optimalizace programů, číslo 17). - ISBN 978-591124-036-3 .
  3. ↑ Moon J. W., Moser L.  O klikách v grafech // Israel Journal of Mathematics. - 1965. - Sv. 3, č. 1. - S. 23–28. - doi : 10.1007/BF02760024 .
  4. ↑ Furedi, Zoltan. Počet maximálně nezávislých množin v spojených grafech // Journal of Graph Theory. - 1987. - Sv. 11, č. 4. - S. 463-470. - doi : 10.1002/jgt.3190110403 .
  5. ↑ Z článku Rusova a Zakharové níže: V poslední době jsou pro řešení tohoto druhu problémů největší zájem o heuristické algoritmy, tedy algoritmy, které stále umožňují řešení NP-úplného problému, ale s určitou chybou. Hlavními kritérii pro vyhodnocení heuristického algoritmu jsou „časová efektivita“ a chyba ve vztahu k přesnému algoritmu.
  6. ↑ Robson J. M.  Algorithms for Maximum independent sets // Journal of Algorithms. - 1986. - Sv. 7, č. 3. - S. 425-440. - doi : 10.1016/0196-6774(86)90032-5 .
  7. ↑ Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos, Johan M. M. van Rooij. . Metoda zdola nahoru a rychlé algoritmy pro MAX INDEPENDENT SET // Teorie algoritmů — SWAT 2010 . - Berlin: Springer , 2010. - (Lecture Notes in Computer Science, sv. 6139). - doi : 10.1007/978-3-642-13731-0_7 .  — S. 62–73.
  8. ↑ Chiba N., Nishizeki T.  Arboricita a algoritmy výpisu podgrafů // SIAM Journal on Computing . - 1985. - Sv. 14, č. 1. - S. 210-223. - doi : 10.1137/0214017 .
  9. ↑ Piotr Berman, Toshihiro Fujito. . O aproximačních vlastnostech úlohy nezávislých množin pro grafy stupně 3 // Čtvrtý mezinárodní seminář o algoritmech a datových strukturách. - Springer , 1995. - (Lecture Notes in Computer Science, sv. 995). - doi : 10.1007/3-540-60220-8_84 .  - S. 449-460.
  10. ↑ Halldórsson M. M., Radhakrishnan J.  Chamtivost je dobrá: Aproximace nezávislých množin v řídkých a omezených grafech // Algorithmica . - 1997. - Sv. 18, č. 1. - S. 145-163. - doi : 10.1007/BF02523693 . .
  11. ↑ Sbihi, 1980 .
  12. ↑ Grötschel, Lovász, Schrijver, 1988 .
  13. ↑ Brenda S. Bakerová. Aproximační algoritmy pro NP-úplné problémy na rovinných grafech // Journal of the ACM . - 1994. - Sv. 41, č. 1. - S. 153-180. - doi : 10.1145/174644.174650 .
  14. ↑ Martin Grohe. Místní stromová šířka, vyloučení nezletilí a aproximační algoritmy // Combinatorica . - 2003. - Sv. 23, č. 4. - S. 613-632. - doi : 10.1007/s00493-003-0037-9 .

Literatura

Odkazy

 NP-úplné problémy
Maximalizační problém
stohování (balení)
teorie grafů
teorie množin
Algoritmické problémy
Logické hry
a hádanky