Dominantní soubor

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. února 2021; ověření vyžaduje 1 úpravu .

V teorii grafů je dominantní množina pro graf G = ( V , E ) podmnožinou D množiny vrcholů V , takže jakýkoli vrchol mimo D sousedí s alespoň jedním prvkem v D . Číslo dominance γ( G ) je počet vrcholů v nejmenší dominující množině G.

Úkolem dominující množiny je ověřit, zda pro daný graf G a číslo K platí nerovnost γ( G ) ≤ K . Problém je klasickým problémem NP-úplné řešitelnosti v teorii výpočetní složitosti [1] . Má se tedy za to, že neexistuje žádný účinný algoritmus pro nalezení nejmenší dominantní množiny pro daný graf.

Obrázky (a)-(c) vpravo ukazují tři příklady dominujících sad grafů. V těchto příkladech každý bílý vrchol sousedí s alespoň jedním červeným vrcholem a říká se, že bílým vrcholům dominují červené vrcholy. Dominantní číslo tohoto grafu je 2 - příklady (b) a (c) ukazují, že existuje dominující množina se 2 vrcholy a lze ověřit, že pro tento graf neexistuje žádná dominující množina pouze s jedním vrcholem.

Historie

Jak poznamenali Hedeenimi a Laskar [2] , problém dominance byl studován od 50. let 20. století, ale počet studií o dominanci se v polovině 70. let podstatně zvýšil. Jejich bibliografie obsahuje více než 300 článků týkajících se dominance grafů.

Hranice

Nechť G  je graf s n ≥ 1 vrcholy a nechť Δ je maximální stupeň grafu. Jsou známy následující hranice γ( G ) [3] :

Nezávislá nadvláda

Dominantní množiny úzce souvisí s nezávislými množinami  — nezávislá množina je dominantní právě tehdy, je-li největší nezávislou množinou , takže každá největší nezávislá množina [4] v grafu je zároveň nejmenší dominantní množinou. Číslo nezávislé dominance i ( G ) z G  je velikost nejmenší nezávisle dominující množiny (nebo ekvivalentně minimální velikost největších nezávislých množin).

Minimální dominantní množina v grafu nemusí být nutně nezávislá, ale velikost minimální dominantní množiny je vždy menší nebo rovna velikosti minimální největší nezávislé množiny, tedy γ( G ) ≤ i ( G ).

Existují rodiny grafů, ve kterých je minimální největší nezávislá množina minimální dominantní množinou. Například Allan a Lascar [5] ukázali, že γ( G ) = i ( G ), pokud G nemá drápy .

Graf G se nazývá dominantně dokonalý graf , jestliže γ( H ) = i ( H ) v jakémkoli generovaném podgrafu H z G. Protože vygenerovaný podgraf bezdrápového grafu je bezdrápový, vyplývá z toho, že jakýkoli bezdrápový graf je dominantně dokonalý [6] .

Příklady

Obrázky (a) a (b) ukazují nezávislé dominantní množiny, zatímco obrázek (c) ukazuje množinu, která není nezávislá.

Pro jakýkoli graf G je jeho spojnicový graf L ( G ) bez drápů, a proto minimální největší nezávislá množina v L ( G ) je zároveň minimální dominující množinou v L ( G ). Nezávislá množina v L ( G ) odpovídá shody v G a dominující množina v L ( G ) odpovídá hranové dominující množině v G . Minimální největší shoda má tedy stejnou velikost jako minimální sada dominujících hran.

Algoritmy a výpočetní složitost

Mezi problémem minimální dominující množiny a problémem pokrytí množiny existuje dvojice L-redukcí v polynomiálním čase [7] . Tyto redukce (viz níže) ukazují, že efektivní algoritmus pro problém minimální dominující množiny by poskytl efektivní algoritmus pro problém pokrývající množinu a naopak. Navíc redukce zachovávají aproximační faktor  — pro jakékoli α by algoritmus aproximace α v polynomiálním čase pro nalezení minimální dominující množiny poskytl algoritmus aproximace α v polynomiálním čase pro problém pokrývající množinu a naopak. Obě úlohy jsou ve skutečnosti Log-APX-complete [8] .

Problém pokrytí množin je dobře známý NP-těžký problém - problém pokrytí množiny ve variantě problému řešitelnosti byl jedním z 21 Karpových NP-úplných problémů , u kterých byla NP-úplnost prokázána již v roce 1972. Redukovatelnost ukazuje že problém dominující množiny je také NP-těžký.

Aproximovatelnost problému množinového krytí je také dobře pochopena – logaritmický aproximační faktor lze nalézt pomocí jednoduchého zištného algoritmu a nalezení sublogaritmického a logaritmického faktoru je NP-těžký problém. Přesněji řečeno, chamtivý algoritmus poskytuje aproximační faktor 1 + log | v | pro minimální dominující množinu a Raz a Safra [9] ukázali, že žádný algoritmus neposkytuje lepší aproximační faktor než C *log | v | pro některé C > 0 pokud P = NP .

L-odlitky

Následující dvojice redukcí [7] ukazuje, že problém minimální dominující množiny a problém pokrývající množinu jsou ekvivalentní v L-redukci  — za předpokladu jednoho problému můžeme sestrojit ekvivalentní vyjádření druhého problému.

Od dominantní sady po krycí sadu. Je-li dán graf G = ( V , E ) s V = {1, 2, …, n }, sestrojíme obal množiny ( U , S ) takto: Množina U je rovna V a rodina podmnožiny se rovná S = { S 1 , S 2 , …, S n }, kde S v se skládá z vrcholu v a všech vrcholů sousedících s vrcholy v z G .

Nyní, je-li D dominující množina v G , pak C = { S v  : v ∈ D } je proveditelným řešením krycího problému s | c | = | D |. Naopak, jestliže C = { S v  : v ∈ D } je proveditelné řešení krycího problému, pak D je dominující množina pro G s | D | = | C |.

Velikost minimální dominující množiny pro G je tedy rovna velikosti krytí minimální množiny pro ( U , S ). Navíc existuje jednoduchý algoritmus, který mapuje dominující množinu na krycí množinu stejné velikosti a naopak. Zejména účinný a-aproximační algoritmus pro pokrytí množin poskytuje účinný α-aproximační algoritmus pro minimální dominující množiny.

Například s ohledem na graf G zobrazený vpravo vytvoříme kryt množiny s množinou U = {1, 2, …, 6} a podmnožinami S 1 = {1, 2, 5}, S 2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5 , 6 } a S6 = {3, 5, 6}. V tomto příkladu je D = {3, 5} dominantní množinou pro G  - odpovídá obalu C = { S 3 , S 5 }. Například vrcholu 4 ∈ V dominuje vrchol 3 ∈ D a prvek 4 ∈ U je obsažen v množině S 3 ∈ C .

Od krycího souboru k dominantnímu souboru. Nechť ( S , U ) je řešením problému pokrývajícího množinu s kolekcí U a rodinou podmnožin S = { S i  : i ∈ I }. Předpokládáme, že U a indexová množina I se neprolínají. Graf G = ( V , E ) sestrojíme následovně. Vezměte V = I ∪ U jako množinu vrcholů . Definujeme hranu { i , j } ∈ E mezi každou dvojicí i , j ∈ I , stejně jako hranu { i , u } pro každé i ∈ I a u ∈ S i . To znamená, že G je rozdělený graf  - I je klika a U je nezávislá množina .

Nyní, jestliže C = { S i  : i ∈ D } je proveditelné řešení problému pokrývajícího množinu pro nějakou podmnožinu D ⊆ I , pak D je dominující množina pro G s | D | = | C |: Za prvé, pro libovolný vrchol u ∈ U existuje i ∈ D takové, že u ∈ S i , a podle konstrukce u a i sousedí v G . Proto -u dominuje vrchol i . Za druhé, protože D musí být neprázdné, jakékoli i ∈ I sousedí s vrcholem v D .

Naopak, nechť D je dominující množina pro G . Pak můžeme sestrojit další dominující množinu X takovou, že | x | ≤ | D | a X ⊆ I  jednoduše nahradí každý vrchol u ∈ D ∩ U vrcholem i ∈ I sousedícím s u . Pak C = { S i  : i ∈ X } je proveditelné řešení krycího problému s | c | = | x | ≤ | D |.

Obrázek vpravo ukazuje konstrukci pro U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { a , b }, S3 = { b , c , d } a S4 = { c , d , e } . V tomto příkladu je C = { S 1 , S 4 } kryt množiny. Odpovídá dominující množině D = {1, 4}. D = { a , 3, 4} je další dominující množina pro graf G . Vzhledem k D , můžeme sestrojit dominující množinu X = {1, 3, 4}, která nepřesahuje D a je podmnožinou I . Dominující množina X odpovídá obalu množiny C = { S 1 , S 3 , S 4 }.

Zvláštní příležitosti

Pokud má graf maximální stupeň Δ, pak algoritmus chamtivé aproximace najde O (log Δ)-aproximaci minimální dominující množiny. Nechť také d g je mocnina dominující množiny získané pomocí algoritmu hrabivé aproximace, pak platí vztah: d g ≤ N+1 - , kde N je počet uzlů a M je počet hran v daném neorientovaný graf [10] . Pro pevné Δ to znamená, že problém najít dominantní množinu patří do třídy APX . Ve skutečnosti je problém APX-complete [11] .

Algoritmus umožňuje PTAS pro speciální případy, jako jsou jednotkové kruhové grafy a rovinné grafy [12] . Minimální dominující množinu lze nalézt v lineárním čase v paralelně-sekvenčních grafech [13] .

Přesné algoritmy

Minimální dominující množinu grafu s n vrcholy lze nalézt v O (2 n n ) čase pohledem na všechny podmnožiny vrcholů. Fomin, Grandoni a Kratch ukázali [14] , jak najít minimální dominující množinu v O (1,5137 n ) čase pomocí exponenciální paměti a O (1,5264 n ) čase pomocí polynomiální paměti. Rychlejší algoritmus běžící v O (1,5048 n ) čase byl nalezen von Royem, Nederlofem a von Dijkem [15] , kteří ukázali, že počet minimálních dominujících množin lze vypočítat za určený čas. Počet minimálních dominujících množin nepřesahuje 1,7159 n a všechny takové množiny lze vyčíslit v čase O (1,7159 n ) [16] .

Parametrická složitost

Hledání dominující množiny velikosti k hraje ústřední roli v parametrické teorii složitosti. Problém je nejznámější W[2]-úplný problém a používá se v mnoha případech k prokázání neřešitelnosti problému jeho redukcí na problém nalezení dominantní množiny. Konkrétně problém není řešitelný s pevnou parametrem (FPR) v tom smyslu, že neexistuje žádný algoritmus s dobou běhu f ( k ) n O(1) pro žádnou funkci f , pokud se W-hierarchie nezhroutí do FPT =W[2].

Na druhou stranu, pokud je vstupní graf rovinný, problém zůstává NP-těžký, ale algoritmus s pevným parametrem je znám. Ve skutečnosti má problém jádro s lineární velikostí v k [17] a exponenciální čas v √ k a kubický v n lze dosáhnout aplikací dynamického programování na větvení jádra [18] . Obecněji platí, že problém dominující množiny a mnoho variant problému jsou pevně-parametricky řešitelné, pokud je parametrizace provedena jak z hlediska velikosti dominantní množiny, tak z hlediska velikosti nejmenšího zakázaného úplného bipartitního podgrafu . To znamená, že problémem je FPR na grafech bez biclique , což je poměrně obecná třída řídkých grafů, která zahrnuje rovinné grafy [19] .

Možnosti

Vizingova domněnka dává do souvislosti číslo dominance přímého součinu grafů s čísly dominance jeho faktorů.

Existuje mnoho dokumentů o spojené dominující množině . Jestliže S je připojená dominantní množina, lze vytvořit kostru G , ve které S tvoří množinu nelistových vrcholů stromu . Naopak, je-li T kostra grafu s více než dvěma vrcholy, nelistové vrcholy T tvoří spojenou dominující množinu. Hledání minimálních spojených dominujících množin je tedy ekvivalentní hledání kostrových stromů s maximálním možným počtem listů.

Kompletní dominující množina  je taková množina vrcholů, že všechny vrcholy grafu (včetně vrcholů samotné dominující množiny) mají sousedy v dominující množině. Obrázek (c) výše ukazuje dominující množinu, která je zároveň spojenou dominující množinou i kompletní dominující množinou. Na obrázcích (a) a (b) není dominantní množina ani jedna.

Dominantní množina k-tice  je taková množina vrcholů, že každý vrchol v grafu má v množině alespoň k sousedů. Aproximaci (1+log n) minimální k-tice dominující množiny lze nalézt v polynomiálním čase [20] . Podobně, k-dominantní množina  je množina vrcholů taková, že každý vrchol, který není v množině, má v množině alespoň k sousedů. Zatímco jakýkoli graf připouští k-dominantní množinu, pouze grafy s minimálním stupněm k-1 umožňují dominující množinu k-n-tice. Nicméně, i když graf umožňuje k-tice dominující množinu, minimální k-tice dominující množina může být téměř k krát minimální k-tice dominující množina pro stejný graf [21] . (1,7+log Δ)-aproximace minimální k-dominantní množiny lze také nalézt v polynomiálním čase.

Domatická dekompozice  je dekompozice vrcholů na nepřekrývající se dominující množiny. Domatické číslo je maximální velikost domatického rozšíření.

Věčná dominující množina  je dynamická verze dominance , ve které je vrchol v v dominující množině D vybrán a nahrazen sousedním u ( u nikoli v D ) tak , že modifikovaná množina D je také dominantní a tento proces může opakovat pro jakoukoli konečnou posloupnost voleb vrcholů v.

Software pro nalezení minimální dominující množiny

název Licence Uživatelský jazyk krátké informace
openopt BSD Krajta Používá grafy NetworkX . Může používat freeware a komerční balíčky. Podrobnosti a příklady najdete na hlavní stránce sady .

Viz také

Poznámky

  1. ↑ Gary, Johnson, 1982 , s. 235, úkol TG2.
  2. ↑ Hedetniemi, Laskar, 1990 .
  3. ↑ Haynes, Hedetniemi, Slater, 1998a , str. Kapitola 2.
  4. ↑ Často dochází k záměně s pojmy největší množina a maximální množina . Největší množinou se v tomto článku rozumí množina, kterou nelze rozšířit při zachování její vlastnosti. Maximální množina je množina s danou vlastností, která má maximální velikost.
  5. ↑ Allan, Laskar, 1978 .
  6. ↑ Faudree, Flandrin, Ryjaček, 1997 .
  7. ↑ 1 2 Kann, 1992 , str. 108–109.
  8. ↑ Escoffier, Paschos, 2006 , str. 369–377.
  9. ↑ Raz, Safra, 1997 .
  10. ↑ Parekh, 1991 , s. 237-240.
  11. ↑ Papadimitriou, Yannakakis, 1991 , s. 425–440.
  12. ↑ Crescenzi, Kann, Halldorsson, Karpinski, 2000 .
  13. ↑ Takamizawa, Nishizeki, Saito, 1982 .
  14. ↑ Fomin, Grandoni, Kratsch, 2009 .
  15. ↑ van Rooij, Nederlof, van Dijk, 2009 .
  16. ↑ Fomin, Grandoni, Pjatkin, Stepanov, 2008 .
  17. ↑ Alber, Fellows, Niedermeier, 2004 .
  18. ↑ Fomin, Thilikos, 2006 .
  19. ↑ Telle, Villager, 2012 .
  20. ↑ Klasing, Laforest, 2004 .
  21. ↑ Forster, 2013 .

Literatura