Кіріспе
Графтың түйіндерінің кіші жиыны, мұнда басқа барлық түйіндер кем дегенде бір доминатормен байланысты. Басқару ағыны графиктерінде, граф теориясында 1=G графигі үшін доминациялық жиын – оның 1=D төбелерінің кіші жиыны, яғни 1=G кез келген төбесі 1=D-де орналасқан немесе 1=D-де көршілес төбесі бар. Доминациялық сан γ(G) – G үшін ең кішкентай доминациялық жиынның төбелерінің саны. Доминациялық жиынтық мәселесі берілген G графигі және K енгізілімі үшін γ(G) ≤ K шартын тексеруге қатысты; бұл есептеу күрделілігі теориясындағы классикалық NP-толық шешім есептеуі. Сондықтан, 1=G барлық графтары үшін γ(G) есептейтін тиімді алгоритмнің жоқ болуы мүмкін деп есептеледі. Дегенмен, кейбір графтар кластары үшін тиімді жуықтау алгоритмдері, сондай-ақ тиімді нақты алгоритмдер бар. Доминациялық жиынтықтар бірнеше салаларда қолданыс табады. Сымсыз желілерде доминациялық жиынтықтар ad hoc мобильді желілердегі тиімді маршруттарды табу үшін пайдаланылады. Олар сондай-ақ құжаттарды қорытындылауда және электр желілері үшін қауіпсіз жүйелерді жобалауда қолданылған.
Dominator in control flow graphs
In graph theory, a dominating set for a graph 1=G is a subset 1=D of its vertices, such that any vertex of 1=G is in 1=D, or has a neighbor in 1=D. The domination number γ(G) is the number of vertices in a smallest dominating set for G.
The dominating set problem concerns testing whether γ(G) ≤ K for a given graph G and input K; it is a classical NP complete decision problem in computational complexity theory. Therefore it is believed that there may be no efficient algorithm that can compute γ(G) for all graphs 1=G. However, there are efficient approximation algorithms, as well as efficient exact algorithms for certain graph classes. Dominating sets are of practical interest in several areas. In wireless networking, dominating sets are used to find efficient routes within ad hoc mobile networks. They have also been used in document summarization, and in designing secure systems for electrical grids.
Ресми анықтама
Бағытталмаған график 1=G = (V, E) берілген болса, төбелердің ішкі жиыны доминантты жиын деп аталады, егер әрбір төбе үшін , осындай төбе бар болса .
Кез келген график кем дегенде бір доминантты жиынға ие: егер барлық төбелер жиыны болса, онда анықтама бойынша D доминантты жиын болып табылады, себебі мұндай төбе A жоқ. Қызығушылық тудыратын мәселе – кішкентай доминантты жиындарды табу. 1=G графигінің доминация саны былай анықталады: .
Тәуелсіз жиынтықтардың үстемдігі
Граф G-нің iγ(G) тәуелсіздік үстемдік саны – G-нің барлық тәуелсіз жиындары A үшін, A-ны үстемдік ететін ең кіші жиынның ең үлкен мәні. Түйіндердің ішкі жиынтығын үстемдік ету, барлық түйіндерді үстемдік етуге қарағанда аз түйіндерді қажет етеді, сондықтан iγ(G) ≤ γ(G) барлық G графтары үшін. Теңсіздік қатаң болуы мүмкін, яғни iγ(G) < γ(G) болатын графтар бар. Мысалы, n бүтін саны үшін, G графигінің түйіндері n×n тақтаның қатарлары мен бағаналары болсын, және егер олар қиылысса ғана екі түйін байланысқан болады. Бірден-бір тәуелсіз жиындар – тек қатарлар жиыны немесе тек бағаналар жиыны, және олардың әрқайсысын бір түйін (баған немесе қатар) үстемдік ете алады, сондықтан 1=iγ(G) = 1. Дегенмен, барлық түйіндерді үстемдік ету үшін кем дегенде бір қатар және бір баған қажет, сондықтан 1=γ(G) = 2. Сонымен қатар, γ(G) / iγ(G) арақатынасы кез келген деңгейде үлкен болуы мүмкін. Мысалы, егер G-нің түйіндері n×n тақтаның барлық квадраттар жиындары болса, онда 1=iγ(G) = 1, бірақ 1=γ(G) = n. G графигінің iγi(G) екі рет тәуелсіз үстемдік саны – G-нің барлық тәуелсіз жиындары A үшін, A-ны үстемдік ететін ең кіші тәуелсіз жиынның ең үлкен мәні. G кез келген граф үшін келесі қатынастар орындалады:
The inequality can be strict there are graphs G for which iγ(G) < γ(G). For example, for some integer n, let G be a graph in which the vertices are the rows and columns of an n by n board, and two such vertices are connected if and only if they intersect. The only independent sets are sets of only rows or sets of only columns, and each of them can be dominated by a single vertex (a column or a row), so 1=iγ(G) = 1. However, to dominate all vertices we need at least one row and one column, so 1=γ(G) = 2. Moreover, the ratio between γ(G) / iγ(G) can be arbitrarily large. For example, if the vertices of G are all the subsets of squares of an n by n board, then still 1=iγ(G) = 1, but 1=γ(G) = n.
The bi independent domination number iγi(G) of a graph G is the maximum, over all independent sets A of G, of the smallest independent set dominating A. The following relations hold for any graph G:
Тарих
Доминиру проблемасы 1950 жылдардан бастап зерттелді, бірақ доминиру бойынша зерттеулердің қарқыны 1970 жылдардың ортасында едәуір артты. 1972 жылы Ричард Карп жиынтықты жабу мәселесінің NP-толық екенін дәлелдеді. Бұл үстем жиын мәселесіне тікелей әсер етті, себебі екі мәселенің арасында төбелерді жиынға және қабырғаларды жиынға сәйкестікпен байланыстырудың қарапайым тәсілдері бар. Осының нәтижесінде үстем жиын мәселесі де NP-толық екені дәлелденді.
Алгоритмдер мен есептеу күрделілігі
Нысанды жабу мәселесі – жақсы белгілі NP қиын мәселе. Нысанды жабудың шешімдік нұсқасы Карптың 21 NP-толық мәселесінің бірі болды. Минималдық үстемдік жинағы мәселесі мен нысанды жабу мәселесі арасында полиномиалдық уақытта L-қайта келтірулер бар. Бұл қайта келтірулер (төменде қараңыз) минималдық үстемдік жинағы мәселесі үшін тиімді алгоритм болса, нысанды жабу мәселесі үшін де тиімді алгоритм болады, және керісінше екенін көрсетеді. Сонымен қатар, қайта келтірулер жуықтау қатынасын сақтайды: кез келген α үшін, минималдық үстемдік жинағы үшін полиномиалдық уақыттағы α-жуықтау алгоритмі нысанды жабу мәселесі үшін полиномиалдық уақыттағы α-жуықтау алгоритмін береді, және керісінше. Екі мәселе де іс жүзінде Log APX-толық. Нысанды жабудың жуықтау мүмкіндігі де жақсы түсініледі: қарапайым ашкөз алгоритмді қолдану арқылы логарифмдік жуықтау коэффициентін табуға болады, ал сублогарифмдік жуықтау коэффициентін табу NP қиын. Нақтырақ айтқанда, ашкөз алгоритм минималдық үстемдік жинағының жуықтау коэффициентін береді, ал P = NP болмаса, ешқандай полиномиалдық уақыт алгоритмі c > 0 үшін жақсы жуықтау коэффициентін алуға мүмкіндік бермейді.
L-кемулер
Келесі екі азайту L азайтулары арқылы ең кішкентай үстемдік жиыны және жиынтық жабу проблемаларының эквивалентті екенін көрсетеді: бір проблеманың мысалын бергенде, екінші проблеманың эквивалентті мысалын құруға болады.
Басым жиынтықтан жиынтыққа дейін
1=G = (V, E) графигін 1=V = {1, 2, ..., n} берілген кезде, жиынтық қаптамасының (U, S) мысалын келесідей құрастырамыз: ғалам U – V, ал кіші жиынтықтар отбасы G графигіндегі v төбесінен және v төбесіне іргелес жатқан барлық төбелерден тұрады.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Егер D, G үшін үстемдік жиын болса, онда жиынтық қаптамасының мәселесі үшін мүмкін болатын шешім болады. Керісінше, егер жиынтық қаптамасының мәселесі үшін мүмкін болатын шешім болса, онда D, G үшін үстемдік жиын болады.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Осылайша, G үшін ең кішкентай үстемдік жиынының мөлшері, (U, S) үшін ең кішкентай жиынтық қаптамасының мөлшерімен тең. Сонымен қатар, үстемдік жиынды бірдей өлшемдегі жиынтық қаптамасына және керісінше бейімдейтін қарапайым алгоритм бар. Атап айтқанда, жиынтықты жабу үшін тиімді α-аппроксимациялық алгоритм, ең кішкентай үстемдік жиындары үшін тиімді α-аппроксимациялық алгоритмді қамтамасыз етеді. Мысалы, оң жақта көрсетілген G графигін ескере отырып, біз ғалам 1=U = {1, 2, ..., 6} және кіші жиынтықтармен жиынтық қаптамасының мысалын құрастырамыз. Осы мысалда 1=D = {3, 5} G үшін үстемдік жиын болып табылады – бұл жиынтық қаптамасына сәйкес келеді. Мысалы, 4 ∈ V төбесі 3 ∈ D төбесімен үстемдік етеді, ал 4 ∈ U элементі жиынтығына кіреді.
Now if D is a dominating set for G, then is a feasible solution of the set cover problem, with Conversely, if is a feasible solution of the set cover problem, then D is a dominating set for G, with
Hence the size of a minimum dominating set for G equals the size of a minimum set cover for (U, S). Furthermore, there is a simple algorithm that maps a dominating set to a set cover of the same size and vice versa. In particular, an efficient α approximation algorithm for set covering provides an efficient α approximation algorithm for minimum dominating sets. For example, given the graph G shown on the right, we construct a set cover instance with the universe 1=U = {1, 2, , 6} and the subsets and In this example, 1=D = {3, 5} is a dominating set for G – this corresponds to the set cover For example, the vertex 4 ∈ V is dominated by the vertex 3 ∈ D, and the element 4 ∈ U is contained in the set .
Ерекше жағдайлар
Егер графтың ең жоғары дәрежесі Δ болса, онда ашкөздікпен жақындау алгоритмі ең кішкентай доминантты жиынның O(log Δ) жуықтауын табады. Сондай-ақ, ашкөздікпен жуықтап алынған доминантты жиынның кардиналдығы болсын, онда келесі қатынас орындалады, мұнда N – түйіндер саны және M – берілген бағытталмаған графтың қабырғаларының саны. Белгілі Δ үшін бұл APX мүшелігіне үміткер доминантты жиын ретінде жарамды; шындығында, ол APX-толық. Бұл мәселе бірлік дискілік графтар мен жазық графтар сияқты ерекше жағдайларда полиномиалдық уақытқа жуықтау схемасын (PTAS) қабылдайды. Минималды доминантты жиынды қатарлы-параллель графтарда сызықтық уақыт ішінде табуға болады.
Нақты алгоритмдер
n төбелі графтың ең кішкентай доминантты жиыны барлық төбелердің кіші жиындықтарын қарастыру арқылы табылуы мүмкін. Ең кішкентай доминантты жиынтықты уақыт пен экспоненциалдық жадта, және уақыт пен полиномиалдық жадта табу қалай болатынын көрсетіңіз. Уақытты қолданатын жылдам алгоритмді тапты, сонымен қатар, ең кішкентай доминантты жиынтықтардың санын осы уақытта есептеуге болатынын көрсетті. Ең кішкентай доминантты жиынтықтардың саны ең көп болса , барлық осындай жиынтықтарды уақыт ішінде тізімдеуге болады.
Параметрленген күрделілік
K өлшемінің үстемдік жиынын табу, параметрленген күрделілік теориясындағы маңызды рөл атқарады. Бұл W[2] класы үшін толық проблема ретінде ең жақсы танылған және басқа проблемалардың шешілмейтіндігін көрсету үшін көптеген түрлендірулерде қолданылады. Атап айтқанда, W иерархиясы FPT=W[2] дейін құламайынша, кез келген f функциясы үшін орындалу уақыты бар алгоритм жоқ, яғни проблема тұрақты параметрмен шешілмейді. Егер кіріс графигі жазық болса, проблема NP-қиын болып қалады, бірақ тұрақты параметрлік алгоритм бар. Шындығында, проблеманың k-ға қатысты сызықтық өлшемдегі ядросы бар, және ядроның тармақталуына динамикалық бағдарлама қолдану арқылы экспоненциалды және n-ға қатысты кубикалық орындалу уақытын алуға болады. Жалпы алғанда, үстемдік жиыны проблемасы және оның көптеген түрлері, үстемдік жиынының мөлшері және ең кішкентай тыйым салынған толық екі бөліктік кішграфтың мөлшері бойынша параметрленгенде тұрақты параметрлік болып табылады; яғни, проблема бикликтік бос графтарда FPT, бұл жазық графтарды қоса алғанда, сирек графтардың өте жалпы класы. Үстемдік жиынының толықтыру жиыны, яғни бұғаттаушы емес жиын, кез келген граф үшін тұрақты параметрлік алгоритммен табылуы мүмкін.