Dominantni skup

Dominating sets (red vertices).

U teoriji grafova, dominanti skup za graf G = (V, E) je podskup D od V takav da svaki čvor koji nije u D je susedan najmanje jednom članu iz D. Dominantni broj γ(G) je broj čvorova u najmanjem dominantnom skupu za G.

Problem dominantnog skupa se tiče provere da li važi γ(G) ≤ K za dati graf G i ulaz K; to je klasičan NP-kompletan problem odlučivanja u računarskoj teoriji kompleksnosti {{sfn|Garey|Johnson|1979|pp=. Stoga se veruje da ne postoji efikasan algoritam koji pronalazi najmanji dominantni skup za dati graf.

Postavke (a)-(c) na desnoj strani pokazuju tri primera dominantnog skupa za graf. U svakom primeru, svaki beli čvor je susedan najmanje jednom crvenom čvoru, a rečeno je da crveni čvor dominira belim čvorom. Dominantni broj ovog grafa je 2: primeri (b) i (c) pokazuju da postoji dominantni skupovi sa 2 čvora, a može da se proveri da nema dominantnog skupa sa samo jednim čvorom za ovaj graf.

Istorija

Kao Hedetniemi & Laskara (1990) beleška, problem dominacije se proučava od 1950. pa nadalje, ali stopa istraživanja o dominaciji je znatno porasla sredinom 1970-ih. Njihova bibliografija uključuje preko 300 radova u vezi sa dominacijom u grafovima.

Granice

Neka je G graf sa n ≥ 1 temena i neka je Δ maksimalni stepen grafa. Sledeće granice na γ(G) su poznate (Haines, Hedetniemi i Slater 1998a, poglavlje 2):

• Jedan čvor može da dominira u većini Δ drugih čvorova; Stoga γ(G) ≥ n / (1 + Δ).
• Skup svih čvorova je dominantni skup u bilo kom grafu; Stoga γ(G) ≤ n.
• Ako nema izolovanih čvorova u G, onda postoje dva razdvojena dominantna skupa u G. Zato u svakom grafiku bez izolovanim čvorova se smatra da je γ(G) ≤ n/2’’.

Nezavisna dominacija

Dominantni skupovi su blisko povezani sa nezavisnim skupovima: nezavisan skup je takođe dominantan skup ako i samo ako je maksimalni nezavisan skup, tako da bilo koji maksimalno nezavisan skup u grafikonu je nužno i minimalni dominantan skup. Prema tome, najmanji maksimalni nezavisan skup je takođe i najmanji nezavisan dominantan skup.’’’ Nezavisan dominantni broj i(G) grafa G je veličina najmanjeg nezavisnog dominantog skupa (ili, ekvivalentno, veličina najmanjeg maksimalnog nezavisnog skupa).

Minimalni dominantni skup u grafu ne mora biti nezavisan, ali veličina minimalnog dominantog skupa je uvek manja ili jednaka od veličine minimuma maksimalnog nezavisnog skupa, to jest, γ(G) ≤ i(G). Postoje porodice grafova u kojima je minimum maksimalno nezavisnog skupa minimum dominantnog skupa. Na primer, Alan i Laskar (1978) pokazuju da γ(G) = i(G) ako je G neuklješten graf.

Graf G se zove dominantno-savršen graf , ako važi γ(H) = i(H) u svakom indukovanom podgrafu H od G. Pošto je indukovani podgraf neuklještenog grafaneuklješten graf, sledi da svaki neuklješten graf je takođe dominantno-savršen (Faudre, Flandrin i Rijaček 1997 - ).

Primeri

Postavke (a) i (b) su nezavisni dominantni skupovi, dok postavka (C) ilustruje dominantni skup koji nije nezavisan skup.

Za svaki graf G, njegova linija grafa L(G) je neuklještena, a samim tim i minimum maksimalno nezavisnog skupa u L(G) je takođe minimalan dominantan skup u L(G). Nezavisan skup u L(G) odgovara poklapanju u G, i dominantni skup u L(G) odgovara ivici dominantnog skupa u G. Stoga minimum maksimalnog preklapanja imaju istu veličinu kao minimum ivice dominantnog skupa.

Algoritmi i kompjuterska kompleksnost

Postoji par L-redukcija (linearnih složenosti) u polinomijalnom vremenu između problema minimuma dominantog skupa i problema skupa poklopca. Ove redukcije pokazuju da bi efikasan algoritam za problem minimuma dominantnog skupa obezbedio efikasan algoritam za problem skupa poklopca i obrnuto. Oba problema su u stvari polinomijalno logaritamske složenosti.

Problem skup pokrivača je dobro poznat NP-težak problem – odlučena verzija skupa pokrivača je bila jedna od Karpovih 21 NP-kompletnih problema, koje se pokazalo da su NP-kompletni već 1972. Otuda redukcija pokazuje da problem dominantnog skupa jeste NP-težak takođe.

Approkimacija problema prekrivača je takođe proučena: faktor logaritamske aproksimacije može se rešiti pomoću jednostavnog pohlepog algoritma, i pronalaženje sublogaritamskog približnog faktora je NP-teško. Preciznije, pohlepni algoritam daje faktor 1 + log|V| aproksimacije minimuma dominantog skupa, i Raz i Safra (1997) pokazuju da nijedan algoritam ne može dostići faktor aproksimacije bolji od c’’ log|V| za neke c> 0 osim ako je P = NP.

L-redukcije

Sledeći par redukcija ( Kan 1992, str 108-109) pokazuje da su problem minimuma dominantnog skupa i problem skupa pokrivača ekvivalentni u L-redukciji: ukoliko damo instancu jednog problema, možemo izgraditi ekvivalentnu instancu drugog problema.

Od dominantog skupa do skupa pokrivanja. Dat je graf G = (V, E) sa V = {1, 2, ..., n}, koji gradi instancu skupa pokrivanja (S, U) na sledeći način: univerzum U je V, i porodica podskupa je S = {S₁, S₂, ..., S_n} tako da se S_v sastoji od čvora v i svih čvorova pridruženim v u G. Sada, ako je D dominantan skup za G, onda C = { S_v: v ∈ D} je izvodljivo rešenje problema skupa pokrivača, sa |C| = |D|. S druge strane, ako je C = {S_v: v ∈ D} izvodljivo rešenje problema skupa pokrivača, onda je D dominantan skup za G, sa |D| = |C|.

Otuda je veličina minimuma dominantog skupa za G jednaka veličini minimuma skupa pokrivača za (S, U). Osim toga, postoji jednostavan algoritam koji vodi od dominantanog skupa do skupa prekrivača iste veličine i obrnuto. Konkretno, efikasan α-aproksimiran algoritam za pokrivanje obezbeđuje efikasna algoritam α-aproksimacije za minimume dominantnih skupova

Na primer, dat je graf G prikazan na desnoj strani, mi konstruišemo instancu skupa pokrivača sa univerzumom U = {1, 2, ..., 6} i podgrupe S₁ = {1, 2, 5}, S₂ = { 1, 2, 3, 5}, S₃ = {2, 3, 4, 6}, S₄ = {3, 4}, S₅ = {1, 2, 5, 6}, i S₆ = {3, 5, 6 }. U ovom primeru, D = {3, 5} je dominantan skup za G - to odgovara skupu prekrivača C = { S₃, S₅ }. Na primer, čvor 3 ∈ D dominira čvorom 4 ∈ V, i element 4 ∈ U je sadržan u skupu S₃ ∈ C.

Od skupa pokrivanja do dominantog skupa .Neka (S, U) bude instanca problema skupa pokrivača sa univerzumom U i porodicom podskupa S = { S_i: i ∈ I}; pretpostavljamo da su U i indeks I razdvojeni. Izgraditi graf G = (V, E) na sledeći način: skup čvorova je V = I ∪ U, tu je grana {i, j} ∈ E između svakog čvora i, j ∈ I, a tu je grana {i, u} za svako i ∈ I i u ∈ S_i. To je, G je podeljen graf: I je klika, a U je nezavisan skup.

Sada, ako je C = {S_i:i ∈ D} izvodljivo rešenje problema skupa čvorova za neki podskup D ⊆ I, onda je D dominanatan skup za G, sa |D| = |C|: Prvo, za svaku u ∈ U postoji i ∈ D, tako da u ∈ S_i i izgradnjom , u i i su povezani u G ; stoga i dominira u i. Drugo, budući da D mora biti neprazan, svako i ∈ I je susedan čvoru u D.

Nasuprot tome, neka je D dominanatan skup za G. Tada je moguće izgraditi još jedan dominantan skup X tako da |X| ≤ |D| i X ⊆ I: jednostavno zameniti svaki u ∈ D ∩ U komšijom i ∈ I u. Zatim, C = { S_i: i ∈ X} je izvodljivo rešenjeproblema skupa prekrivača, sa |C| = |X| ≤ |D|.

Ilustracija na desnoj strani pokazuje izgradnju za U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S₁= {a, b, c}, S₂ = {a, b}, S₃= {b, c, d}, i S₄ = {c, d, e}.

U ovom primeru, C = { S₁, S₄} je skup prekrivača; to odgovara dominantnom skupu D= {1, 4}.

D = {a, 3, 4} je još jedan dominantan skup za graf G.Ako uzmemo D, možemo izgraditi dominantan skup X = {1, 3, 4} koji nije veći od D i koji je podskup od D. Dominantan skup X odgovara skupu prekirvača C = { S₁, S₃, S₄}.

Tačni algoritmi

Minimum dominantnog skupa sa n čvorova grafa može se naći u vremenu O (2ⁿn) prolaskom kroz sve čvorove podgrupe. Fomin, Grandoni i Krač Fomin, (2009) pokazuju kako pronaći minimum dominantnog skupa u vremenu O(1.5137ⁿ) i eksponencijalne prostorne složenosti, kao i u vremenuO(1.5264ⁿ) i polinomijalne prostorne složenosti. Brži algoritam, koristeći O(1.5048ⁿ) vremena je pronašao van Roj, Nederlof i van Dijk van Rooij, (2009), koji je takođe pokazao da se broj minimuma dominantnog skupa može izračunati u tom trenutku. Broj minimalnih dominantnih skupova je najviše 1.7159ⁿ i svi takvi skupovi se mogu navesti vremenski O(1.7159ⁿ) (Fomin 2008. ).

Parametrizovana kompleksnost

Pronalaženje dominanog skupa veličine k igra centralnu ulogu u teoriji parametrizovane složenosti. To je najviše poznat problem i koristi se u mnogim redukcijama da se pokaže tvrdoglavost drugih problema. Posebno, problem nije fiksno parametarski rešiv u smislu da nema algoritma sa trajanjem od f(k)n^O(1) za bilo koju funkciju f. S druge strane, ako je ulazni graf planaran, problem ostaje NP-težak, ali fiksna parametrizacija algoritma je poznata. U stvari, problem ima jezgro veličine linearno u k (Alber, Felous i Nidermeir 2004) i trajanje koje je eksponencijalno u √k i kubno u n može se dobiti primenom dinamičkog programiranja (Fomin & Thilikos 2006).

Softveri za pronalaženje minimuma dominantnog skupa

Ime (po abecednom redu)	Licenca	API jezik	Kratka informacija
OpenOpt	BSD	Python	Koristi NetworkX grafove, koristi se besplatno i u komercijalne svrhe, uključujući/isključujući čvorove