Domináns készlet

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. február 24-én felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A gráfelméletben a G = ( V , E ) gráf domináns halmaza a V csúcshalmaz D részhalmaza úgy, hogy minden olyan csúcs, amely nincs D -ben , szomszédos legalább egy D -beli elemmel . A γ( G ) dominanciaszám a legkisebb domináns G halmaz csúcsainak száma .

A domináns halmazprobléma annak ellenőrzése, hogy a γ( G ) ≤ K egyenlőtlenség igaz -e egy adott G gráfra és egy K számra . A probléma egy klasszikus NP-teljes megoldhatósági probléma a számítási komplexitáselméletben [1] . Ezért úgy gondoljuk, hogy nincs hatékony algoritmus egy adott gráf legkisebb domináns halmazának megtalálására.

A jobb oldali (a)-(c) ábrák három példát mutatnak az uralkodó gráfhalmazokra. Ezekben a példákban minden fehér csúcs szomszédos legalább egy vörös csúcsgal, és a fehér csúcsokat a vörös csúcsok uralják . Ennek a gráfnak a domináns száma 2 – a (b) és (c) példák azt mutatják, hogy van egy domináns halmaz, amelynek 2 csúcsa van, és ellenőrizhető, hogy ehhez a gráfhoz nincs egyetlen csúcsú domináns halmaz.

Történelem

Ahogy Hedeenimi és Laskar [2] megjegyezte , a dominancia-problémát az 1950-es évek óta tanulmányozták, de a dominanciával foglalkozó tanulmányok száma jelentősen megnőtt az 1970-es évek közepén. Bibliográfiájuk több mint 300, a gráfdominanciával kapcsolatos közleményt tartalmaz.

Szegélyek

Legyen G  egy n ≥ 1 csúcsú gráf, és legyen Δ a gráf maximális foka. A következő γ( G ) [3] határok ismertek :

Független uralom

A domináns halmazok szorosan kapcsolódnak a független halmazokhoz  – egy független halmaz akkor és csak akkor domináns, ha a legnagyobb független halmaz , így a gráfban szereplő bármely legnagyobb független halmaz [4] egyben a legkisebb domináns halmaz is. G független dominanciája i ( G )  a legkisebb független domináns halmaz mérete (vagy ennek megfelelően a legnagyobb független halmazok minimális mérete).

A minimális domináns halmaz egy gráfban nem feltétlenül független, de a minimális domináns halmaz mérete mindig kisebb vagy egyenlő, mint a legkisebb legnagyobb független halmaz mérete, azaz γ( G ) ≤ i ( G ).

Vannak gráfcsaládok, amelyekben a legkisebb legnagyobb független halmaz a minimális domináns halmaz. Például Allan és Lascar [5] kimutatta, hogy γ( G ) = i ( G ), ha G - nek nincsenek karmai .

Egy G gráfot dominánsan tökéletes gráfnak nevezünk , ha γ( H ) = i ( H ) G bármely generált H részgráfjában . Mivel a karmok nélküli gráf generált részgráfja körmök nélküli, ebből következik, hogy bármely körmök nélküli gráf dominánsan tökéletes [6] .

Példák

Az (a) és (b) ábrákon független domináns halmazok láthatók, míg a (c) ábrán egy nem független halmaz látható.

Bármely G gráf esetén az L ( G ) vonalgráfja körömmentes, ezért az L ( G ) legkisebb legnagyobb független halmaza egyben L ( G ) minimális domináns halmaza is . Egy független halmaz L -ben ( G ) megfelel a G - beli illeszkedésnek , és egy domináns halmaz L -ben ( G ) egy éldomináns halmaznak G -ben . Így a legkisebb legnagyobb egyezés mérete megegyezik a minimális éldomináns halmazéval.

Algoritmusok és számítási bonyolultság

A minimális domináns halmazprobléma és a halmazlefedési probléma között van egy polinomiális idejű L-redukció pár [7] . Ezek a redukciók (lásd alább) azt mutatják, hogy egy hatékony algoritmus a minimálisan domináns halmazproblémára hatékony algoritmust adna a lefedő halmazproblémára , és fordítva. Ezenkívül a redukciók megőrzik a közelítési tényezőt  – bármely α esetén egy polinomiális idejű α-közelítési algoritmus egy minimális domináns halmaz megtalálására polinomiális idejű α-közelítési algoritmust biztosít a halmazlefedő probléma számára , és fordítva. Mindkét feladat valójában Log-APX-teljes [8] .

A halmazlefedési probléma egy jól ismert NP-nehéz probléma - a megoldhatósági probléma egy változatában szereplő halmazlefedési probléma egyike volt Karp 21 NP-teljes feladatának , amelyekre az NP-teljességet már 1972- ben igazolták . A redukálhatóság azt mutatja, hogy hogy az uralkodó halmazprobléma is NP-kemény.

A halmazfedő-probléma közelíthetősége is jól érthető – a logaritmikus közelítési tényezőt egy egyszerű mohó algoritmussal találhatjuk meg , a szublogaritmikus és logaritmikus tényező megtalálása pedig NP-nehéz feladat. Pontosabban, a mohó algoritmus 1 + log | közelítési tényezőt ad v | a minimális domináns halmazra, és Raz és Safra [9] kimutatta, hogy egyetlen algoritmus sem ad jobb közelítési tényezőt, mint C *log | v | bizonyos C > 0 esetén, hacsak nem P = NP .

L-casts

A következő redukciópár [7] azt mutatja, hogy a minimálisan domináns halmazprobléma és a halmazlefedési probléma ekvivalensek az L-redukcióban  – adott probléma esetén a másik probléma ekvivalens kijelentését is megszerkeszthetjük.

Az uralkodó készlettől a fedőkészletig. Adott egy G = ( V , E ) gráf, ahol V = {1, 2, …, n }, megszerkesztjük az ( U , S ) halmaz fedőjét a következőképpen: Az U halmaz egyenlő V -vel , és a család részhalmaz egyenlő S = { S 1 , S 2 , …, S n }, ahol S v a v csúcsból és a G -ből származó v csúcsokkal szomszédos összes csúcsból áll .

Most, ha D egy domináns halmaz G -ben, akkor C = { S v  : v ∈ D } megvalósítható megoldás a | c | = | D |. Ezzel szemben, ha C = { S v  : v ∈ D } a lefedési probléma megvalósítható megoldása, akkor D egy domináns halmaz G számára | D | = | C |.

Ennélfogva a G minimális domináns halmazának mérete megegyezik az ( U , S ) minimális halmazának a méretével. Ezenkívül van egy egyszerű algoritmus, amely egy domináns halmazt képez le egy azonos méretű fedőhalmazra, és fordítva. A halmazlefedettség hatékony α-közelítési algoritmusa hatékony α-közelítési algoritmust eredményez minimális domináns halmazokhoz.

Például a jobb oldalon látható G grafikon alapján készítünk egy halmazborítót az U = {1, 2, …, 6} halmazzal és az S 1 = {1, 2, 5}, S 2 = {1} részhalmazokkal, 2, 3, 5}, S 3 = {2, 3, 4, 6}, S 4 = {3, 4}, S 5 = {1, 2, 5, 6} és S 6 = {3, 5, 6}. Ebben a példában D = {3, 5} a G domináns halmaza  - ez megfelel a C = { S 3 , S 5 } borítónak. Például a 4 ∈ V csúcsot a 3 ∈ D csúcs uralja , és a 4 ∈ U elemet az S 3 ∈ C halmaz tartalmazza .

Egy halmaz lefedétől a domináns halmazig. Legyen ( S , U ) megoldása a halmazlefedési probléma U gyűjteményével és az S = { S i  : i ∈ I } részhalmazok családjával . Feltételezzük, hogy U és az I indexhalmaz nem metszi egymást. A G = ( V , E ) gráfot a következőképpen építjük fel. V = I ∪ U a csúcsok halmaza . Minden i , j ∈ I pár között meghatározunk egy { i , j } ∈ E élt, valamint minden i ∈ I és u ∈ S i egy { i , u } élt . Vagyis G egy osztott gráf  - I egy klikk , U pedig egy független halmaz .

Most, ha C = { S i  : i ∈ D } a halmazlefedési probléma megvalósítható megoldása valamilyen D ⊆ I részhalmazra , akkor D egy domináns halmaz G -re | D | = | C |: Először is, bármely u ∈ U csúcsra létezik olyan i ∈ D , hogy u ∈ S i , és a konstrukció alapján u és i szomszédosak G -ben . Ezért - u -t az i csúcs uralja . Másodszor, mivel D -nek nem üresnek kell lennie, bármely i ∈ I szomszédos egy D -beli csúcstal .

Fordítva, legyen D domináns halmaz G számára . Ekkor létrehozhatunk egy másik domináns X halmazt úgy, hogy | x | ≤ | D | és X ⊆ I  egyszerűen lecseréli minden u ∈ D ∩ U csúcsot egy u -val szomszédos i ∈ I csúcsra . Ekkor C = { S i  : i ∈ X } megvalósítható megoldás a | c | = | x | ≤ | D |.

A jobb oldali ábra az U = { a , b , c , d , e }, I = {1, 2, 3, 4}, S 1 = { a , b , c }, S 2 = { konstrukcióját mutatja. a , b } , S 3 = { b , c , d } és S 4 = { c , d , e }. Ebben a példában C = { S 1 , S 4 } a halmaz borítója. Ez megfelel a D = {1, 4} domináns halmaznak. D = { a , 3, 4} egy másik domináns halmaz a G gráfban . Adott D , megalkothatunk egy domináns X = {1, 3, 4} halmazt, amely nem haladja meg D -t, és az I részhalmaza . A domináns X halmaz a C = { S 1 , S 3 , S 4 } halmaz fedőjének felel meg .

Különleges alkalmak

Ha a gráf maximális foka Δ, akkor a mohó közelítési algoritmus megtalálja a minimális domináns halmaz O (log Δ)-közelítését. Legyen d g a mohó közelítési algoritmussal kapott domináns halmaz hatványa is, ekkor teljesül a következő összefüggés: d g ≤ N+1 - , ahol N a csomópontok száma, M pedig az élek száma egy adott területen. irányítatlan gráf [10] . Rögzített Δ esetén ez azt jelenti, hogy a domináns halmaz megtalálásának problémája az APX osztályba tartozik . Valójában a probléma APX-teljes [11] .

Az algoritmus lehetővé teszi a PTAS -t speciális esetekben, mint például egységkörgráfok és síkgráfok [12] . A minimális domináns halmaz lineáris időben párhuzamos-szekvenciális gráfokban található [13] .

Pontos algoritmusok

Az n csúcsú gráf minimális domináns halmaza O (2 n n ) idő alatt megtalálható, ha a csúcsok összes részhalmazát megnézzük. Fomin, Grandoni és Kratch megmutatta [14] , hogyan lehet megtalálni a minimális domináns halmazt O (1,5137 n ) időben exponenciális memória és O (1,5264 n ) időben polinomiális memória használatával. Egy gyorsabb, O (1,5048 n ) időben futó algoritmust talált von Roy, Nederlof és von Dijk [15] , akik kimutatták, hogy a minimális domináns halmazok száma kiszámítható a megadott idő alatt. A minimális domináns halmazok száma nem haladja meg az 1,7159 n -t , és az összes ilyen halmaz megszámlálható O (1,7159 n ) idő alatt [16] .

Paraméteres összetettség

A k méretű domináns halmaz keresése központi szerepet játszik a parametrikus komplexitáselméletben. A probléma a legismertebb W[2]-teljes probléma, és sok esetben a probléma megoldhatatlanságának bemutatására használják úgy, hogy a domináns halmaz megtalálásának problémájára redukálják. Konkrétan a probléma nem megoldható fix-paraméteres (FPR) abban az értelemben, hogy nincs f ( k ) n O(1) futási idejű algoritmus egyetlen f függvényre sem , hacsak a W-hierarchia nem omlik össze FPT-be. =W[2].

Másrészt, ha a bemeneti gráf síkbeli, akkor a probléma NP-nehéz marad, de a fix paraméterű algoritmus ismert. Valójában a probléma egy olyan kernelre vonatkozik, amelynek mérete lineáris k -ban [17] , és √ k -ban exponenciális, n -ben köbös futási idő érhető el, ha dinamikus programozást alkalmazunk a kernel elágazására [18] . Általánosságban elmondható, hogy a domináns halmazprobléma és a probléma számos változata fix-parametrikusan megoldható, ha a paraméterezést mind a domináns halmaz méretének, mind a legkisebb tiltott teljes kétrészes részgráf méretének megfelelően végezzük . Ez azt jelenti, hogy a probléma az FPR a biklik nélküli gráfokon , a ritka gráfok meglehetősen általános osztálya, amely síkgráfokat is tartalmaz [19] .

Opciók

Vining sejtése a gráfok direkt szorzatának dominanciáját a faktorainak dominanciaszámaival hozza összefüggésbe.

A kapcsolódó domináns halmazról sok dolgozat létezik . Ha S egy összefüggő domináns halmaz, akkor létrehozhatunk egy feszítőfát G -ből, amelyben S alkotja a fa nem leveles csúcsainak halmazát . Ezzel szemben, ha T egy gráf feszítőfája, amelynek több mint két csúcsa van, akkor T nem leveles csúcsai egy összefüggő domináns halmazt alkotnak. Így a minimálisan összefüggő domináns halmazok keresése egyenértékű a lehető legnagyobb levélszámú, átívelő fák keresésével.

A teljes domináns halmaz  olyan csúcsok halmaza, ahol a gráf összes csúcsának (beleértve magának a domináns halmaznak a csúcsait is) vannak szomszédai a domináns halmazban. A fenti (c) ábra egy domináns halmazt mutat, amely egyszerre összefüggő domináns halmaz és teljes domináns halmaz is. Az (a) és (b) ábrákon a domináns halmazok egyike sem.

A k-sor domináns halmaz  olyan csúcsok halmaza, ahol a gráf minden csúcsának legalább k szomszédja van a halmazban. Egy minimális k-sor domináns halmaz (1+log n) közelítése megtalálható polinomidőben [20] . Hasonlóképpen, a k-domináns halmaz  csúcsok halmaza úgy, hogy minden olyan csúcsnak, amely nincs a halmazban, van legalább k szomszédja a halmazban. Bár minden gráf elfogad egy k-domináns halmazt, csak a minimális k-1 fokú gráfok engednek k-soros domináns halmazt. Azonban még ha a gráf megenged is egy k-sor domináns halmazt, a minimális k-sor domináns halmaz majdnem k-szorosa lehet ugyanazon gráf minimális k-sorának domináns halmazának [21] . A minimális k-domináns halmaz (1,7+log Δ)-közelítése polinomidőben is megtalálható.

A domatikus dekompozíció  a csúcsok nem átfedő domináns halmazokra bontása. A domatikus szám a domatikus bővítmény maximális mérete.

Az örök domináns halmaz  a dominancia dinamikus változata, amelyben a domináns D halmazban egy v csúcsot választanak ki, és egy szomszédos u -val ( u nem D -ben) helyettesítik oly módon, hogy a módosított D halmaz is dominál, és ez a folyamat meg kell ismételni a csúcsválasztások bármely véges sorozatára v.

Szoftver a minimális domináns halmaz megtalálásához

Név Engedély Felhasználói nyelv rövid tájékoztatás
openopt BSD Piton NetworkX grafikonokat használ . Használhat ingyenes és kereskedelmi csomagokat. Részletekért és példákért lásd a domináns készletoldalt.

Lásd még

Jegyzetek

  1. ↑ Gary, Johnson, 1982 , p. 235, TG2 feladat.
  2. ↑ Hedetniemi, Laskar, 1990 .
  3. ↑ Haynes, Hedetniemi, Slater, 1998a , p. 2. fejezet.
  4. ↑ Gyakran összekeverik a legnagyobb halmaz és a maximum halmaz kifejezéseket . Ebben a cikkben a legnagyobb készlet alatt azt a halmazt értjük, amely nem bővíthető a tulajdonának megőrzése mellett. A maximális halmaz egy adott tulajdonsággal rendelkező halmaz, amelynek maximális mérete van.
  5. ↑ Allan, Laskar, 1978 .
  6. ↑ Faudree, Flandrin, Ryjaček, 1997 .
  7. ↑ 1 2 Kann, 1992 , p. 108–109.
  8. ↑ Escoffier, Paschos, 2006 , p. 369–377.
  9. ↑ Raz, Safra, 1997 .
  10. ↑ Parekh, 1991 , p. 237-240.
  11. ↑ Papadimitriou, Yannakakis, 1991 , p. 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, Sztepanov, 2008 .
  17. ↑ Alber, Fellows, Niedermeier, 2004 .
  18. ↑ Fomin, Thilikos, 2006 .
  19. ↑ Telle, Villager, 2012 .
  20. ↑ Klasing, Laforest, 2004 .
  21. ↑ Forster, 2013 .

Irodalom