Dominující sada - Dominating set

Dominující sady (červené vrcholy).

v teorie grafů, a dominující sada pro graf G = (PROTI, E) je podmnožina D z PROTI tak, že každý vrchol není v D sousedí s alespoň jedním členem D. The dominantní číslo γ (G) je počet vrcholů v nejmenší dominující množině proG.

The dominující množinový problém týká se testování, zda γ (G) ≤ K. pro daný graf G a vstup K.; je to klasický NP-kompletní rozhodovací problém v teorie výpočetní složitosti.^[1] Proto se věří, že nemusí existovat žádná efektivní algoritmus který najde nejmenší dominující množinu pro všechny grafy, i když existují efektivní aproximační algoritmy, stejně jako efektivní a přesné algoritmy pro určité třídy grafů.

Obrázky (a) - (c) vpravo ukazují tři příklady dominujících množin pro graf. V každém příkladu každý bílý vrchol sousedí s alespoň jedním červeným vrcholem a říká se, že bílý vrchol je dominoval červeným vrcholem. Číslo dominance tohoto grafu je 2: příklady (b) a (c) ukazují, že existuje dominující množina se 2 vrcholy, a lze zkontrolovat, že pro tento graf neexistuje dominující množina pouze s 1 vrcholem.

Dějiny

Problém dominance byl studován od padesátých let 20. století, avšak v polovině sedmdesátých let se významně zvýšila míra výzkumu dominance. V roce 1972 Richard Karp prokázal nastavit problém s krytem být NP-kompletní. To mělo okamžité důsledky pro problém s dominující množinou, protože mezi těmito dvěma problémy existuje přímý vrchol a hrana s nedisjunktními průsečíky. To se ukázalo jako problém s dominující sadou NP-kompletní také.^[2]

Dominantní sady mají praktický význam v několika oblastech. v bezdrátové sítě, dominující sady se používají k hledání efektivních cest v mobilních sítích ad-hoc. Byly také použity při sumarizaci dokumentů a při navrhování bezpečných systémů pro elektrické sítě.

Dominující a nezávislé soubory

Dominující sady úzce souvisí nezávislé sady: nezávislá množina je také dominující množinou tehdy a jen tehdy, je-li a maximální nezávislá množina, takže jakákoli maximální nezávislá množina v grafu je nutně také minimální dominující množina.

Nadvláda podle nezávislé sady

Dominující sada může, ale nemusí být nezávislou sadou. Například obrázky (a) a (b) výše ukazují nezávislé dominující množiny, zatímco obrázek (c) ilustruje dominující množinu, která není nezávislou množinou.

The nezávislé číslo dominance i(G) grafu G je velikost nejmenší dominující sady, která je nezávislou sadou. Ekvivalentně je to velikost nejmenší maximální nezávislé množiny. Minimální v i(G) je převzato méně prvků (uvažovány jsou pouze nezávislé množiny), takže γ (G) ≤ i(G) pro všechny grafy G.

Nerovnost může být přísná - existují grafy G pro které γ (G) < i(G). Například nechte G být dvojitý hvězdný graf skládající se z vrcholů X₁, ..., X_p, A, b, y₁, ..., y_q, kde p, q > 1. Okraje G jsou definovány takto: každý X_i sousedí s A, A sousedí s b, a b sousedí s každým b_j. Pak γ (G) = 2 od {A, b} je nejmenší dominující množina. Li p ≤ q, pak i(G) = p + 1 od {X₁, ..., X_p, b} je nejmenší dominující množina, která je také nezávislá (je to nejmenší maximální nezávislá množina).

Existují rodiny grafů, ve kterých γ (G) = i(G), to znamená, že každá minimální maximální nezávislá množina je minimální dominující množina. Například γ (G) = i(G) pokud G je graf bez drápů.^[3]

Graf G se nazývá a dokonalý graf dominance pokud γ (H) = i(H) v každé indukovaný podgraf H z G. Protože indukovaný podgraf grafu bez drápů je bez drápů, vyplývá z toho, že každý graf bez drápů je také dokonalý.^[4]

Pro jakýkoli graf G, své hranový graf L(G) je bez drápů, a tedy minimální maximální nezávislá sada v L(G) je také minimální dominující sada v L(G). Nezávislý soubor L(G) odpovídá a vhodný v Ga dominující set in L(G) odpovídá an hrana dominující sada v G. Proto a minimální maximální shoda má stejnou velikost jako sada ovládající minimální hranu.

Nadvláda z nezávislé sady

The číslo dominance nezávislosti iγ(G) grafu G je maximum ve všech nezávislých sadách A z G, dominující nejmenší množina A.^[5] Ovládnutí podmnožin vrcholů vyžaduje potenciálně méně vrcholů než ovládnutí všech vrcholů, takže iγ (G) ≤ y(G) pro všechny grafy G.

Nerovnost může být přísná - existují grafy G pro které iγ (G) < y(G). Například pro nějaké celé číslo n, nechť G být graf, ve kterém vrcholy jsou řádky a sloupce n-podle-n deska a dva takové vrcholy jsou spojeny právě tehdy, když se protínají. Jediné nezávislé sady jsou sady pouze řádků nebo sady pouze sloupců a každé z nich může dominovat jeden vrchol (sloupec nebo řádek), takže iγ(G) = 1. Abychom však ovládli všechny vrcholy, potřebujeme alespoň jeden řádek a jeden sloupec y(G) = 2. Navíc poměr mezi y(G) / iγ(G) může být libovolně velký. Například pokud vrcholy G jsou všechny podmnožiny čtverců an n-podle-n deska, pak stále iγ(G) = 1, ale y(G)=n.^[5]

The bi-nezávislé číslo nadvlády iγi(G) grafu G je maximum ve všech nezávislých sadách A z G, dominující nejmenší nezávislé množiny A. Následující vztahy platí pro jakýkoli graf G:

$${ displaystyle { begin {zarovnáno} i (G) & geq gamma (G) geq i gamma (G) i (G) & geq i gamma i (G) geq i gamma (G) end {zarovnáno}}}$$

Algoritmy a výpočetní složitost

Problém s krytem sady je dobře známý NP-tvrdé problém - rozhodovací verze krytiny sady byla jednou z Karpových 21 NP-úplných problémů. Existuje dvojice polynomiálního času L-redukce mezi problémem minimální dominující množiny a nastavit problém s krytem.^[6] Tato snížení (viz. níže ) ukazují, že efektivní algoritmus pro problém s minimální dominující množinou by poskytl efektivní algoritmus pro problém s krytem množiny a naopak. Snížení navíc zachovává přibližný poměr: pro jakýkoli α by algoritmus α-aproximace v polynomiálním čase pro minimální dominující množiny poskytoval algoritmus α-aproximace v polynomiálním čase pro problém krytí sady a naopak. Oba problémy jsou ve skutečnosti Log-APX-kompletní.^[7]

Přibližnost zakrytí množiny je také dobře známa: logaritmický aproximační faktor lze najít pomocí a jednoduchý chamtivý algoritmus a nalezení sublogaritmického aproximačního faktoru je NP-těžké. Chamtivější algoritmus poskytuje faktor 1 + log |PROTI| aproximace minimální dominující množiny a žádný algoritmus polynomiálního času nemůže dosáhnout aproximačního faktoru lépe než C přihlásit |PROTI| pro některé C > 0, pokud P = NP.^[8]

L-redukce

Následující dvě redukce ukazují, že problém s minimální dominující sadou a nastavit problém s krytem jsou ekvivalentní pod L-redukce: vzhledem k instanci jednoho problému můžeme vytvořit ekvivalentní instanci druhého problému.^[6]

Od dominující sady po krycí sadu.Daný graf G = (PROTI, E) s PROTI = {1, 2, ..., n}, vytvořte instanci sady krytu (U, S) takto: vesmír U je PROTIa rodina podmnožin je S = {S₁, S₂, ..., S_n} takové, že S_proti sestává z vrcholu proti a všechny vrcholy sousedící s proti v G.

Teď když D je dominující sada pro G, pak C = {S_proti : proti ∈ D} je proveditelné řešení problému sady krytů s |C| = |D|. Naopak, pokud C = {S_proti : proti ∈ D} je tedy proveditelné řešení problému se stanoveným krytem D je dominující sada pro G, s |D| = |C|.

Proto velikost minimální dominující sady pro G se rovná velikosti minimálního krytí pro (U, S). Kromě toho existuje jednoduchý algoritmus, který mapuje dominující sadu na kryt sady stejné velikosti a naopak. Zejména efektivní algoritmus α-aproximace pro zakrytí množiny poskytuje efektivní algoritmus α-aproximace pro minimální dominující množiny.

Například vzhledem k grafu G zobrazeno vpravo, sestrojíme instanci sady krytu s vesmírem U = {1, 2, ..., 6} a podmnožiny S₁ = {1, 2, 5}, S₂ = {1, 2, 3, 5}, S₃ = {2, 3, 4, 6}, S₄ = {3, 4}, S₅ = {1, 2, 5, 6} a S₆ = {3, 5, 6}. V tomto příkladu D = {3, 5} je dominující množina pro G - to odpovídá nastavenému krytu C = {S₃, S₅}. Například vrchol 4 ∈PROTI dominuje vrchol 3 ∈Da prvek 4 ∈U je obsažen v sadě S₃ ∈ C.

Od krycí sady po dominující sadu.Nechť (S, U) být příkladem problému pokrytí množiny vesmírem U a rodina podmnožin S = {S_i : i ∈ Já}; předpokládáme to U a sada indexů Já jsou disjunktní. Vytvořte graf G = (PROTI, E) takto: množina vrcholů je PROTI = Já ∪ U, je tu hrana {i, j} ∈ E mezi každým párem i, j ∈ Já, a je tu také hrana {i, u} pro každého i ∈ Já a u ∈ S_i. To znamená G je dělený graf: Já je klika a U je nezávislá sada.

Teď když C = {S_i : i ∈ D} je proveditelné řešení problému sady krytů pro nějakou podmnožinu D ⊆ Já, pak D je dominující sada pro G, s |D| = |C|: Nejprve pro každého u ∈ U tady je i ∈ D takhle u ∈ S_ia podle konstrukce, u a i sousedí v G; proto u dominuje i. Zadruhé, protože D musí být neprázdné, každý i ∈ Já sousedí s vrcholem v D.

Naopak, pojďme D být dominující sadou pro G. Pak je možné postavit další dominující množinu X takové, že |X| ≤ |D| a X ⊆ Já: jednoduše je vyměňte u ∈ D ∩ U soused i ∈ Já z u. Pak C = {S_i : i ∈ X} je proveditelné řešení problému s nastaveným krytem pomocí |C| = |X| ≤ |D|.

Ilustrace vpravo ukazuje konstrukci pro U = {A, b, C, d, E}, Já = {1, 2, 3, 4}, S₁ = {A, b, C}, S₂ = {A, b}, S₃ = {b, C, d}, a S₄ = {C, d, E}.

V tomto příkladu C = {S₁, S₄} je sada kryt; to odpovídá dominující množině D = {1, 4}.

D = {A, 3, 4} je další dominující množina pro graf G. Dáno D, můžeme sestrojit dominující množinu X = {1, 3, 4} což není větší než D a která je podmnožinou Já. Dominující sada X odpovídá nastavenému krytu C = {S₁, S₃, S₄}.

Speciální případy

Pokud má graf maximální stupeň Δ, pak chamtivý aproximační algoritmus najde znak Ó(log Δ) - přiblížení minimální dominující množiny. Také nechte d_G být mohutnost dominující množiny získaná chamtivou aproximací, pak platí následující vztah, ${ displaystyle d_ {g} leq N + 1 - { sqrt {2M + 1}}}$, kde N je počet uzlů a M je počet hran v daném neorientovaném grafu.^[9] Pro pevné Δ se to kvalifikuje jako dominující množina pro APX členství; ve skutečnosti je to APX-kompletní.^[10]

Problém připouští a schéma polynomiálního času (PTAS) pro speciální případy, jako je jednotkové diskové grafy a rovinné grafy.^[11] Minimální dominující množinu lze nalézt v lineárním čase v sériově paralelní grafy.^[12]

Přesné algoritmy

Minimální dominující sada an n-vrcholový graf lze najít v čase Ó(2ⁿn) kontrolou všech podskupin vrcholů. Fomin, Grandoni & Kratsch (2009) ukázat, jak najít minimální dominující sadu v čase Ó(1.5137ⁿ) a exponenciální prostor a v čase Ó(1.5264ⁿ) a polynomiální prostor. Rychlejší algoritmus, použití Ó(1.5048ⁿ) čas byl nalezen van Rooij, Nederlof & van Dijk (2009), kteří také ukazují, že v této době lze vypočítat počet minimálních dominujících sad. Počet minimálně dominujících sad je maximálně 1,7159ⁿ a všechny takové sady mohou být uvedeny v čase Ó(1.7159ⁿ).^[13]

Parametrizovaná složitost

Nalezení dominující množiny velikostí k hraje ústřední roli v teorii parametrizované složitosti. Jedná se o nejznámější problém dokončený ve třídě Z [2] a používá se v mnoha redukcích k prokázání neřešitelnosti dalších problémů. Problém zejména není fixovatelný parametr v tom smyslu, že žádný algoritmus s dobou chodu F(k)n^{O (1)} pro jakoukoli funkci F existuje, pokud se W-hierarchie nespadne na FPT = W [2].

Na druhou stranu, pokud je vstupní graf rovinný, problém zůstává NP-tvrdý, ale je znám algoritmus pevných parametrů. Ve skutečnosti má problém jádro velikosti lineární k,^[14] a doby běhu, které jsou exponenciální √k a krychlový n lze získat aplikací dynamické programování do a větvový rozklad jádra.^[15] Obecněji řečeno, problém dominující množiny a mnoho variant problému je fixovatelných parametrů, když je parametrizován jak velikostí dominující množiny, tak velikostí nejmenšího zakázáno kompletní bipartitní podgraf; to znamená, že problém je na FPT bezklikové grafy, velmi obecná třída řídkých grafů, která zahrnuje rovinné grafy.^[16]

Doplňková sada k dominující sadě, a neblokující, lze nalézt pomocí algoritmu s pevnými parametry na libovolném grafu.^[17]

Varianty

Důležitou podtřídou dominujících množin je třída spojené dominující sady. Li S je propojená dominující množina, lze vytvořit a kostra z G ve kterém S tvoří množinu nelistových vrcholů stromu; naopak, pokud T je libovolný kostra v grafu s více než dvěma vrcholy, nelistovými vrcholy T tvoří propojenou dominující sadu. Najít minimální spojené dominující sady je tedy ekvivalentní hledání kosterních stromů s maximálním možným počtem listů.

A celkem dominující sada je sada vrcholů, takže všechny vrcholy v grafu (včetně samotných vrcholů v dominující množině) mají v dominující množině souseda. Obrázek (c) výše ukazuje dominující množinu, která je spojenou dominující množinou a celkovou dominující množinou; příklady na obrázcích (a) a (b) nejsou žádné.

A k-tuple dominující set je sada vrcholů tak, že každý vrchol v grafu má alespoň k sousedé v sadě. Přibližné minimum (1 + log n) k-tuple dominující množinu lze nalézt v polynomiálním čase.^[18] Podobně, a k-dominující sada je sada vrcholů tak, že každý vrchol, který není v množině, má alespoň k sousedé v sadě. Zatímco každý graf připouští a k-dominující sada, pouze grafy s minimálním stupněm k - 1 připouštím a k-tuple dominující set. I když však graf připouští dominující množinu k-tice, minimum k-tuple dominující sada může být téměř k krát tak velké jako minimum k- dominační sada pro stejný graf;^[19] Přibližné minimum (1,7 + log Δ) k-dominující množinu lze nalézt také v polynomiálním čase.

A hvězdná sada je podmnožina D z PROTI tak, že pro každý vrchol v v PROTI, hvězda z proti (sada hran sousedících s proti) protíná hvězdu nějakého vrcholu v D. Je zřejmé, že pokud G má izolované vrcholy pak nemá žádné hvězdy dominující sady (protože hvězda izolovaných vrcholů je prázdná). Pokud G nemá izolované vrcholy, pak každá dominující množina je hvězdotvorná množina a naopak. Rozdíl mezi nadvládou hvězd a obvyklou nadvládou je podstatnější, když vezmeme v úvahu jejich dílčí varianty.^[20]

A domatická přepážka je rozdělení vrcholů do disjunktních dominujících sad. Domatické číslo je maximální velikost domatické oblasti.

An věčná dominující sada je dynamická verze nadvlády, ve které je vrchol proti v dominující sadě D je vybrán a nahrazen sousedem u (u není v D) takové, že upravené D je také dominující množina a tento proces lze opakovat v jakékoli nekonečné posloupnosti možností vrcholůproti.

Viz také

• Vizingova domněnka - spojuje dominantní číslo a kartézský součin grafů počtu dominujících faktorů.
• Nastavit problém s krytem
• Číslo otroctví

Poznámky

Reference

• Alber, Jochen; Fellows, Michael R.; Niedermeier, Rolf (2004), „Redukce dat polynomiálního času pro dominující množinu“, Deník ACM, 51 (3): 363–384, arXiv:cs / 0207066, doi:10.1145/990308.990309, S2CID  488501.
• Allan, Robert B .; Laskar, Renu (1978), „O dominanci a nezávislých číslech dominance grafu“, Diskrétní matematika, 23 (2): 73–76, doi:10.1016 / 0012-365X (78) 90105-X.
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), „Minimum dominating set“, Kompendium problémů s optimalizací NP.
• Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena; Rosamond, Frances (2006), "Nonblocker: Parametrizované algoritmy pro minimální dominující množinu" (PDF), SOFSEM 2006: 32. konference o současných trendech v teorii a praxi informatiky, Merin, Česká republika, 21. – 27. Ledna 2006, sborník, Přednášky v informatice, 3831, Springer, str. 237–245, doi:10.1007/11611257_21.
• Escoffier, Bruno; Paschos, Vangelis Th. (2006), „Úplnost ve třídách aproximace nad rámec APX“, Teoretická informatika, 359 (1–3): 369–377, doi:10.1016 / j.tcs.2006.05.023
• Faudree, Ralphe; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Grafy bez drápů - průzkum", Diskrétní matematika, 164 (1–3): 87–147, doi:10.1016 / S0012-365X (96) 00045-3, PAN  1432221.
• Fomin, Fedor V .; Grandoni, Fabrizio; Kratsch, Dieter (2009), „Přístup měření a dobývání pro analýzu přesných algoritmů“, Deník ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286, S2CID  1186651.
• Fomin, Fedor V .; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), „Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications“, Transakce ACM na algoritmech, 5 (1): 9:1–17, doi:10.1145/1435375.1435384, S2CID  2489447.
• Fomin, Fedor V .; Thilikos, Dimitrios M. (2006), „Dominující množiny v rovinných grafech: šířka větve a exponenciální zrychlení“, SIAM Journal on Computing, 36 (2): 281, doi:10.1137 / S0097539702419649, S2CID  5232238.
• Förster, Klaus-Tycho. (2013), „Přibližování poruch odolných vůči poruchám v obecných grafech“, Proc. desátého semináře o analytické algoritmice a kombinatorice ANALCO, SIAM, s. 25–32, doi:10.1137/1.9781611973037.4, ISBN  978-1-61197-254-2.
• Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, ISBN  0-7167-1045-5, str. 190, problém GT2.
• Hedetniemi, S. T .; Laskar, R. C. (1990), „Bibliografie o dominanci v grafech a některé základní definice parametrů dominance“, Diskrétní matematika, 86 (1–3): 257–277, doi:10.1016 / 0012-365X (90) 90365-O.
• Kann, Viggo (1992), O přibližnosti NP-úplných optimalizačních problémů (PDF). Disertační práce, Katedra numerické analýzy a výpočetní techniky, Královský technologický institut, Stockholm.
• Klasing, Ralf; Laforest, Christian (2004), "Výsledky tvrdosti a aproximační algoritmy dominance k-n-tice v grafech", Dopisy o zpracování informací, 89 (2): 75–83, doi:10.1016 / j.ipl.2003.10.004.
• Papadimitriou, Christos H .; Yannakakis, Mihailis (1991), „Třídy optimalizace, aproximace a složitosti“, Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016 / 0022-0000 (91) 90023-X
• Parekh, Abhay K. (1991), „Analýza chamtivé heuristiky pro hledání malých převládajících množin v grafech“, Dopisy o zpracování informací, 39 (5): 237–240, doi:10.1016/0020-0190(91)90021-9
• Raz, R.; Safra, S. (1997), „Test nízkého stupně pravděpodobnosti subkonstantní chyby a PCP charakterizace NP konstantní chybou“, Proc. 29. výroční ACM Symposium on Theory of Computing, ACM, str. 475–484, doi:10.1145/258533.258641, ISBN  0-89791-888-6, S2CID  15457604.
• Takamizawa, K .; Nishizeki, T.; Saito, N. (1982), "Lineární časová vypočítatelnost kombinatorických problémů na sériově paralelních grafech", Deník ACM, 29 (3): 623–641, doi:10.1145/322326.322328, S2CID  16082154.
• Telle, Jan Arne; Villanger, Yngve (2012), „Algoritmy FPT pro nadvládu v grafech bez biklů“, Epstein, Leah; Ferragina, Paolo (eds.), Algoritmy - ESA 2012: 20. výroční evropské sympozium, Lublaň, Slovinsko, 10. – 12. Září 2012, sborník, Přednášky z informatiky, 7501, Springer, str. 802–812, doi:10.1007/978-3-642-33090-2_69.
• van Rooij, J. M. M .; Nederlof, J .; van Dijk, T. C. (2009), „Inclusion / Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets“, Proc. 17. výroční evropské symposium o algoritmech, ESA 2009, Přednášky v informatice, 5757, Springer, str. 554–565, doi:10.1007/978-3-642-04128-0_50, ISBN  978-3-642-04127-3.

Další čtení

• Grandoni, F. (2006), „Poznámka ke složitosti minimální dominující množiny“, Journal of Discrete Algorithms, 4 (2): 209–214, CiteSeerX  10.1.1.108.3223, doi:10.1016 / j.jda.2005.03.002.
• Guha, S .; Khuller, S. (1998), "Aproximační algoritmy pro připojené dominující množiny" (PDF), Algorithmica, 20 (4): 374–387, doi:10.1007 / PL00009201, hdl:1903/830, S2CID  1249122.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Základy dominance v grafechMarcel Dekker, ISBN  0-8247-0033-3, OCLC  37903553.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Nadvláda v grafech: Pokročilá témataMarcel Dekker, ISBN  0-8247-0034-1, OCLC  38201061.