Доминантни скуп

У теорији графова, доминанти скуп за граф G = (V, E) је подскуп D од V такав да сваки чвор који није у D је суседан најмање једном члану из D. Доминантни број γ(G) је број чворова у најмањем доминантном скупу за G.

Проблем доминантног скупа се тиче провере да ли важи γ(G) ≤ K за дати граф G и улаз K; то је класичан NP-комплетан проблем одлучивања у рачунарској теорији комплексности {{sfn|Garey|Johnson|1979|pp=. Стога се верује да не постоји ефикасан алгоритам који проналази најмањи доминантни скуп за дати граф.

Поставке (а)-(ц) на десној страни показују три примера доминантног скупа за граф. У сваком примеру, сваки бели чвор је суседан најмање једном црвеном чвору, а речено је да црвени чвор доминира белим чвором. Доминантни број овог графа је 2: примери (б) и (ц) показују да постоји доминантни скупови са 2 чвора, а може да се провери да нема доминантног скупа са само једним чвором за овај граф.

Историја[уреди | уреди извор]

Као Хедетниеми & Ласкара (1990)^[1] белешка, проблем доминације се проучава од 1950. па надаље, али стопа истраживања о доминацији је знатно порасла средином 1970-их. Њихова библиографија укључује преко 300 радова у вези са доминацијом у графовима.

Границе[уреди | уреди извор]

Нека је G граф са n ≥ 1 темена и нека је Δ максимални степен графа. Следеће границе на γ(G) су познате (Хаинес, Хедетниеми и Слатер ^[2] 1998а, поглавље 2):

Један чвор може да доминира у већини Δ других чворова; Стога γ(G) ≥ n / (1 + Δ).
Скуп свих чворова је доминантни скуп у било ком графу; Стога γ(G) ≤ n.
Ако нема изолованих чворова у G, онда постоје два раздвојена доминантна скупа у G. Зато у сваком графику без изолованим чворова се сматра да је γ(G) ≤ n/2’’.

Независна доминација[уреди | уреди извор]

Доминантни скупови су блиско повезани са независним скуповима: независан скуп је такође доминантан скуп ако и само ако је максимални независан скуп, тако да било који максимално независан скуп у графикону је нужно и минимални доминантан скуп. Према томе, најмањи максимални независан скуп је такође и најмањи независан доминантан скуп.’’’ Независан доминантни број i(G) графа G је величина најмањег независног доминантог скупа (или, еквивалентно, величина најмањег максималног независног скупа).

Минимални доминантни скуп у графу не мора бити независан, али величина минималног доминантог скупа је увек мања или једнака од величине минимума максималног независног скупа, то јест, γ(G) ≤ i(G). Постоје породице графова у којима је минимум максимално независног скупа минимум доминантног скупа. На пример, Алан и Ласкар ^[3](1978) показују да γ(G) = i(G) ако је G неукљештен граф.

Граф G се зове доминантно-савршен граф , ако важи γ(H) = i(H) у сваком индукованом подграфу H од G. Пошто је индуковани подграф неукљештеног графанеукљештен граф, следи да сваки неукљештен граф је такође доминантно-савршен (Фаудре, Фландрин и Ријачек 1997 - ^[4]).

Примери[уреди | уреди извор]

Поставке (а) и (б) су независни доминантни скупови, док поставка (Ц) илуструје доминантни скуп који није независан скуп.

За сваки граф G, његова линија графа L(G) је неукљештена, а самим тим и минимум максимално независног скупа у L(G) је такође минималан доминантан скуп у L(G). Независан скуп у L(G) одговара поклапању у G, и доминантни скуп у L(G) одговара ивици доминантног скупа у G. Стога минимум максималног преклапања имају исту величину као минимум ивице доминантног скупа.

Алгоритми и компјутерска комплексност[уреди | уреди извор]

Постоји пар Л-редукција (линеарних сложености) у полиномијалном времену између проблема минимума доминантог скупа и проблема скупа поклопца^[5]. Ове редукције показују да би ефикасан алгоритам за проблем минимума доминантног скупа обезбедио ефикасан алгоритам за проблем скупа поклопца и обрнуто. Оба проблема су у ствари полиномијално логаритамске сложености.

Проблем скуп покривача је добро познат NP-тежак проблем – одлучена верзија скупа покривача је била једна од Карпових 21 НП-комплетних проблема, које се показало да су NP-комплетни већ 1972. Отуда редукција показује да проблем доминантног скупа јесте NP-тежак такође.

Аппрокимација проблема прекривача је такође проучена: фактор логаритамске апроксимације може се решити помоћу једноставног похлепог алгоритма, и проналажење сублогаритамског приближног фактора је NP-тешко. Прецизније, похлепни алгоритам даје фактор 1 + log|V| апроксимације минимума доминантог скупа, и Раз и Сафра ^[6] (1997) показују да ниједан алгоритам не може достићи фактор апроксимације бољи од c’’ log|V| за неке c> 0 осим ако је P = NP.

Л-редукције[уреди | уреди извор]

Следећи пар редукција ( Кан 1992, стр 108-109) показује да су проблем минимума доминантног скупа и проблем скупа покривача еквивалентни у Л-редукцији: уколико дамо инстанцу једног проблема, можемо изградити еквивалентну инстанцу другог проблема.

Од доминантог скупа до скупа покривања. Дат је граф G = (V, Е) са V = {1, 2, ..., n}, који гради инстанцу скупа покривања (S, U) на следећи начин: универзум U је V, и породица подскупа је S = {S₁, S₂, ..., S_n} тако да се S_v састоји од чвора v и свих чворова придруженим v у G. Сада, ако је D доминантан скуп за G, онда C = { S_v: v ∈ D} је изводљиво решење проблема скупа покривача, са |C| = |D|. С друге стране, ако је C = {S_v: v ∈ D} изводљиво решење проблема скупа покривача, онда је D доминантан скуп за G, са |D| = |C|.

Отуда је величина минимума доминантог скупа за G једнака величини минимума скупа покривача за (S, U). Осим тога, постоји једноставан алгоритам који води од доминантаног скупа до скупа прекривача исте величине и обрнуто. Конкретно, ефикасан α-апроксимиран алгоритам за покривање обезбеђује ефикасна алгоритам α-апроксимације за минимуме доминантних скупова

На пример, дат је граф G приказан на десној страни, ми конструишемо инстанцу скупа покривача са универзумом U = {1, 2, ..., 6} и подгрупе S₁ = {1, 2, 5}, S₂ = { 1, 2, 3, 5}, S₃ = {2, 3, 4, 6}, S₄ = {3, 4}, S₅ = {1, 2, 5, 6}, и S₆ = {3, 5, 6 }. У овом примеру, D = {3, 5} је доминантан скуп за G - то одговара скупу прекривача C = { S₃, S₅ }. На пример, чвор 3 ∈ D доминира чвором 4 ∈ V, и елемент 4 ∈ U је садржан у скупу S₃ ∈ C.

Од скупа покривања до доминантог скупа .Нека (S, U) буде инстанца проблема скупа покривача са универзумом U и породицом подскупа S = { S_i: i ∈ I}; претпостављамо да су U и индекс I раздвојени. Изградити граф G = (V, Е) на следећи начин: скуп чворова је V = I ∪ U, ту је грана {i, ј} ∈ E између сваког чвора i, j ∈ I, а ту је грана {i, u} за свако i ∈ I и u ∈ S_i. То је, G је подељен граф: I је клика, а U је независан скуп.

Сада, ако је C = {S_i:i ∈ D} изводљиво решење проблема скупа чворова за неки подскуп D ⊆ I, онда је D доминанатан скуп за G, са |D| = |C|: Прво, за сваку u ∈ U постоји i ∈ D, тако да u ∈ S_i и изградњом , u и i су повезани у G ; стога и доминира у i. Друго, будући да D мора бити непразан, свако i ∈ I је суседан чвору у D.

Насупрот томе, нека је D доминанатан скуп за G. Тада је могуће изградити још један доминантан скуп X тако да |X| ≤ |D| и X ⊆ I: једноставно заменити сваки u ∈ D ∩ U комшијом i ∈ I у. Затим, C = { S_i: i ∈ X} је изводљиво решењепроблема скупа прекривача, са |C| = |X| ≤ |D|.

Илустрација на десној страни показује изградњу за U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S₁= {a, b, c}, S₂ = {a, b}, S₃= {b, c, d}, и S₄ = {c, d, e}.

У овом примеру, C = { S₁, S₄} је скуп прекривача; то одговара доминантном скупу D= {1, 4}.

D = {a, 3, 4} је још један доминантан скуп за граф G.Ако узмемо D, можемо изградити доминантан скуп X = {1, 3, 4} који није већи од D и који је подскуп од D. Доминантан скуп X одговара скупу прекирвача C = { S₁, S₃, S₄}.

Тачни алгоритми[уреди | уреди извор]

Минимум доминантног скупа са n чворова графа може се наћи у времену O (2ⁿn) проласком кроз све чворове подгрупе. Фомин, Грандони и Крач Fomin, ^[7] (2009) показују како пронаћи минимум доминантног скупа у времену O(1.5137ⁿ) и експоненцијалне просторне сложености, као и у временуO(1.5264ⁿ) и полиномијалне просторне сложености. Бржи алгоритам, користећи O(1.5048ⁿ) времена је пронашао ван Рој, Недерлоф и ван Дијк van Rooij, ^[8] (2009), који је такође показао да се број минимума доминантног скупа може израчунати у том тренутку. Број минималних доминантних скупова је највише 1.7159ⁿ и сви такви скупови се могу навести временски O(1.7159ⁿ) (Фомин 2008. ^[9]).

Параметризована комплексност[уреди | уреди извор]

Проналажење доминаног скупа величине k игра централну улогу у теорији параметризоване сложености. То је највише познат проблем и користи се у многим редукцијама да се покаже тврдоглавост других проблема. Посебно, проблем није фиксно параметарски решив у смислу да нема алгоритма са трајањем од f(k)n^O(1) за било коју функцију f. С друге стране, ако је улазни граф планаран, проблем остаје NP-тежак, али фиксна параметризација алгоритма је позната. У ствари, проблем има језгро величине линеарно у к (Албер, Фелоус и Нидермеир ^[10] 2004) и трајање које је експоненцијално у √к и кубно у н може се добити применом динамичког програмирања (Фомин & Тхиликос ^[11] 2006).

Софтвери за проналажење минимума доминантног скупа[уреди | уреди извор]

Име (по абецедном реду)	Лиценца	API језик	Кратка информација
OpenOpt	BSD	Python	Користи NetworkX графове, користи се бесплатно и у комерцијалне сврхе, укључујући/искључујући чворове

Референце[уреди | уреди извор]

^ Hedetniemi & Laskar
^ Haynes, Hedetniemi & Slater
^ Allan & Laskar
^ Faudree, Flandrin & Ryjáček
^ Kann 1992, стр. 108–109.
^ Raz & Safra
^ Grandoni & Kratsch
^ Nederlof & van Dijk
^ Fomin et al. 2008
^ Alber, Fellows & Niedermeier
^ Fomin & Thilikos

[1] Hedetniemi & Laskar

[2] Haynes, Hedetniemi & Slater

[3] Allan & Laskar

[4] Faudree, Flandrin & Ryjáček

[FOOTNOTEKann1992108–109-5] Kann 1992, стр. 108–109.

[6] Raz & Safra

[7] Grandoni & Kratsch

[8] Nederlof & van Dijk

[9] Fomin et al. 2008

[10] Alber, Fellows & Niedermeier

[11] Fomin & Thilikos

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]