У теорији графова, доминанти скуп за граф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 = {S1, S2, ..., Sn} тако да се Sv састоји од чвора v и свих чворова придруженим v у G.
Сада, ако је D доминантан скуп за G, онда C = { Sv: v ∈ D} је изводљиво решење проблема скупа покривача, са |C| = |D|. С друге стране, ако је C = {Sv: v ∈ D} изводљиво решење проблема скупа покривача, онда је D доминантан скуп за G, са |D| = |C|.
Отуда је величина минимума доминантог скупа за G једнака величини минимума скупа покривача за (S, U). Осим тога, постоји једноставан алгоритам који води од доминантаног скупа до скупа прекривача исте величине и обрнуто. Конкретно, ефикасан α-апроксимиран алгоритам за покривање обезбеђује ефикасна алгоритам α-апроксимације за минимуме доминантних скупова
На пример, дат је граф G приказан на десној страни, ми конструишемо инстанцу скупа покривача са универзумом U = {1, 2, ..., 6} и подгрупе S1 = {1, 2, 5}, S2 = { 1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5, 6}, и S6 = {3, 5, 6 }. У овом примеру, D = {3, 5} је доминантан скуп за G - то одговара скупу прекривача C = { S3, S5 }. На пример, чвор 3 ∈ D доминира чвором 4 ∈ V, и елемент 4 ∈ U је садржан у скупу S3 ∈ C.
Од скупа покривања до доминантог скупа .Нека (S, U) буде инстанца проблема скупа покривача са универзумом U и породицом подскупа S = { Si: i ∈ I}; претпостављамо да су U и индекс I раздвојени. Изградити граф G = (V, Е) на следећи начин: скуп чворова је V = I ∪ U, ту је грана {i, ј} ∈ E између сваког чвора i, j ∈ I, а ту је грана {i, u} за свако i ∈ I и u ∈ Si. То је, G је подељен граф: I је клика, а U је независан скуп.
Сада, ако је C = {Si:i ∈ D} изводљиво решење проблема скупа чворова за неки подскуп D ⊆ I, онда је D доминанатан скуп за G, са |D| = |C|: Прво, за сваку u ∈ U постоји i ∈ D, тако да u ∈ Si и изградњом , u и i су повезани у G ; стога и доминира у i. Друго, будући да D мора бити непразан, свако i ∈ I је суседан чвору у D.
Насупрот томе, нека је D доминанатан скуп за G. Тада је могуће изградити још један доминантан скуп X тако да |X| ≤ |D| и X ⊆ I: једноставно заменити сваки u ∈ D ∩ U комшијом i ∈ I у. Затим, C = { Si: i ∈ X} је изводљиво решењепроблема скупа прекривача, са |C| = |X| ≤ |D|.
Илустрација на десној страни показује изградњу за U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S1= {a, b, c}, S2 = {a, b}, S3= {b, c, d}, и S4 = {c, d, e}.
У овом примеру, C = { S1, S4} је скуп прекривача; то одговара доминантном скупу D= {1, 4}.
D = {a, 3, 4} је још један доминантан скуп за граф G.Ако узмемо D, можемо изградити доминантан скуп X = {1, 3, 4} који није већи од D и који је подскуп од D. Доминантан скуп X одговара скупу прекирвача C = { S1, S3, S4}.
Тачни алгоритми
Минимум доминантног скупа са n чворова графа може се наћи у времену O (2nn) проласком кроз све чворове подгрупе. Фомин, Грандони и Крач Fomin,[7] (2009) показују како пронаћи минимум доминантног скупа у времену O(1.5137n) и експоненцијалне просторне сложености, као и у временуO(1.5264n) и полиномијалне просторне сложености. Бржи алгоритам, користећи O(1.5048n) времена је пронашао ван Рој, Недерлоф и ван Дијк van Rooij,[8] (2009), који је такође показао да се број минимума доминантног скупа може израчунати у том тренутку. Број минималних доминантних скупова је највише 1.7159n и сви такви скупови се могу навести временски O(1.7159n) (Фомин 2008.[9]).
Параметризована комплексност
Проналажење доминаног скупа величине k игра централну улогу у теорији параметризоване сложености. То је највише познат проблем и користи се у многим редукцијама да се покаже тврдоглавост других проблема. Посебно, проблем није фиксно параметарски решив у смислу да нема алгоритма са трајањем од f(k)nO(1) за било коју функцију f. С друге стране, ако је улазни граф планаран, проблем остаје NP-тежак, али фиксна параметризација алгоритма је позната. У ствари, проблем има језгро величине линеарно у к (Албер, Фелоус и Нидермеир[10] 2004) и трајање које је експоненцијално у √к и кубно у н може се добити применом динамичког програмирања (Фомин & Тхиликос[11] 2006).
Софтвери за проналажење минимума доминантног скупа