प्रभावी समुच्चय

For Dominator in control flow graphs, see Dominator (graph theory).

Error creating thumbnail:

एक ही ग्राफ के तीन प्रभावशाली सेट (लाल रंग में)। इस ग्राफ की वर्चस्व संख्या 2 है: (बी) और (सी) से पता चलता है कि 2 शीर्षों के साथ एक प्रभावशाली सेट है, और केवल 1 शीर्ष के साथ कोई हावी सेट नहीं है।

ग्राफ सिद्धांत में, ग्राफ के लिए एक प्रभावी सेट (असतत गणित) G एक उपसमुच्चय है {{math|1=D}इसके शीर्षों का }, जैसे कि कोई भी शीर्ष G या तो अंदर है D, या उसका कोई पड़ोसी है D. प्रभुत्व संख्या γ(G) सबसे छोटे प्रभुत्व वाले सेट में शीर्षों की संख्या है G.

हावी सेट समस्या परीक्षण की चिंता करती है कि क्या γ(G) ≤ K दिए गए ग्राफ के लिए G और इनपुट K; कम्प्यूटेशनल जटिलता सिद्धांत में यह एक शास्त्रीय एनपी-पूर्ण निर्णय समस्या है। इसलिए यह माना जाता है कि कोई बहुपद-समय एल्गोरिदम नहीं हो सकता है जो गणना कर सके γ(G) सभी रेखांकन के लिए G. हालांकि, कुशल सन्निकटन एल्गोरिदम हैं, साथ ही कुछ ग्राफ वर्गों के लिए कुशल सटीक एल्गोरिदम भी हैं।

हावी होने वाले सेट कई क्षेत्रों में व्यावहारिक रुचि रखते हैं। वायरलेस नेटवर्किंग में, तदर्थ मोबाइल नेटवर्क के भीतर कुशल मार्ग खोजने के लिए प्रमुख सेट का उपयोग किया जाता है। उनका उपयोग दस्तावेज़ सारांश में और विद्युत ग्रिड के लिए सुरक्षित सिस्टम डिजाइन करने में भी किया गया है।

औपचारिक परिभाषा

एक अप्रत्यक्ष ग्राफ दिया G = (V, E), शीर्षों का एक उपसमुच्चय $D\subseteq V$ प्रत्येक शीर्ष के लिए प्रभुत्वशाली समुच्चय कहा जाता है $u\in V\setminus D$, एक शिखर है $v\in D$ ऐसा है कि $(u,v)\in E$.

हर ग्राफ में कम से कम एक प्रभावशाली सेट होता है: यदि $D=V=$ सभी शीर्षों का समुच्चय है, तो परिभाषा के अनुसार D एक प्रभावी समुच्चय है, क्योंकि कोई शीर्ष नहीं है $u\in V\setminus D$. एक और दिलचस्प चुनौती छोटे हावी सेटों को ढूंढना है। का प्रभुत्व संख्या G परिभाषित किया जाता है: $\gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}$.

वेरिएंट

एक जुड़ा हुआ हावी सेट एक हावी सेट है जो जुड़ा हुआ है (ग्राफ सिद्धांत)। यदि S एक जुड़ा हुआ वर्चस्व वाला सेट है, तो कोई G का एक फैले हुए पेड़ का निर्माण कर सकता है जिसमें S पेड़ के गैर-पत्ती के शीर्ष का सेट बनाता है; इसके विपरीत, यदि T दो से अधिक शीर्षों वाले ग्राफ़ में कोई भी फैला हुआ वृक्ष है, तो T के गैर-पत्ती शीर्ष एक जुड़े हुए प्रभावी सेट का निर्माण करते हैं। इसलिए, न्यूनतम जुड़े हुए वर्चस्व वाले सेटों को खोजना पत्तियों की अधिकतम संभव संख्या वाले फैले हुए पेड़ों को खोजने के बराबर है।

टोटल डोमिनेटिंग सेट (या स्ट्रॉन्गली-डोमिनेटिंग सेट) वर्टिकल का एक सेट है, जैसे कि ग्राफ में सभी वर्टिकल, सहित डोमिनेटिंग सेट में वर्टिकल, डोमिनेटिंग सेट में एक पड़ोसी है। वह है: प्रत्येक शीर्ष के लिए $u\in V$, एक शिखर है $v\in D$ ऐसा है कि $(u,v)\in E$. उपरोक्त चित्र (सी) एक हावी सेट दिखाता है जो एक जुड़ा हुआ हावी सेट और कुल हावी सेट है; आंकड़े (ए) और (बी) में उदाहरण न तो हैं। एक साधारण हावी सेट के विपरीत, कुल हावी सेट मौजूद नहीं हो सकता है। उदाहरण के लिए, एक या अधिक शीर्षों और बिना किनारों वाले ग्राफ़ में कुल प्रभावी सेट नहीं होता है। का मजबूत वर्चस्व संख्या G परिभाषित किया जाता है: $\gamma ^{strong}(G):=\min\{|D|:D{\text{ is a strongly-dominating set of }}G\}$; ज़ाहिर तौर से, $\gamma ^{strong}(G)\geq \gamma (G)$.

एक हावी एज-सेट किनारों (शीर्ष जोड़े) का एक सेट है जिसका संघ एक प्रभावशाली सेट है; इस तरह का एक सेट मौजूद नहीं हो सकता है (उदाहरण के लिए, एक ग्राफ जिसमें एक या अधिक कोने हैं और कोई किनारा नहीं है)। यदि यह अस्तित्व में है, तो इसके सभी किनारों का मिलन एक अत्यधिक प्रभावशाली सेट है। इसलिए, एज-डोमिनेटिंग सेट का सबसे छोटा आकार कम से कम है $\gamma ^{strong}(G)/2$.

इसके विपरीत, एक एज डोमिनेटिंग सेट | एज-डोमिनेटिंग सेट किनारों का एक सेट डी है, जैसे कि डी में नहीं हर किनारा डी में कम से कम एक किनारे से सटा हुआ है; ऐसा सेट हमेशा मौजूद होता है (उदाहरण के लिए, सभी किनारों का सेट एज-डोमिनेटिंग सेट होता है)।

एक k-डोमिनेटिंग सेट वर्टिकल का एक सेट है जैसे कि सेट में मौजूद प्रत्येक वर्टेक्स में सेट में कम से कम k पड़ोसी होते हैं (एक मानक डोमिनेटिंग सेट 1-डोमिनेटिंग सेट होता है)। इसी तरह, एक k-टपल डोमिनेटिंग सेट वर्टिकल का एक सेट है जैसे कि ग्राफ में प्रत्येक वर्टेक्स में सेट में कम से कम k पड़ोसी होते हैं (कुल डोमिनेटिंग सेट 1-ट्यूपल डोमिनेटिंग सेट होता है)। एक (1 + log n)-बहुपद समय में न्यूनतम k-tuple हावी सेट का सन्निकटन पाया जा सकता है। प्रत्येक ग्राफ एक k-प्रभुत्व सेट को स्वीकार करता है (उदाहरण के लिए, सभी शीर्षों का सेट); लेकिन केवल न्यूनतम डिग्री वाले रेखांकन k − 1 k-tuple हावी सेट को स्वीकार करें। हालाँकि, भले ही ग्राफ k-tuple हावी सेट को स्वीकार करता हो, एक न्यूनतम k-tuple हावी सेट समान ग्राफ़ के लिए न्यूनतम k- हावी सेट से लगभग k गुना बड़ा हो सकता है; एक (1.7 + log Δ)-न्यूनतम k-प्रभुत्व वाले सेट का सन्निकटन बहुपद समय में भी पाया जा सकता है।

एक 'स्टार-डोमिनेटिंग सेट' V का एक उपसमुच्चय है, जैसे कि V में प्रत्येक शीर्ष v के लिए, v का तारा (ग्राफ़ सिद्धांत) (v से सटे किनारों का सेट) D में किसी शीर्ष के तारे को काटता है। स्पष्ट रूप से , यदि G के पास अलग-थलग शीर्ष है तो इसका कोई सितारा-वर्चस्व वाला सेट नहीं है (चूंकि अलग-अलग शीर्षों का तारा खाली है)। यदि G का कोई पृथक शीर्ष नहीं है, तो प्रत्येक प्रभावी सेट एक स्टार-प्रभुत्व सेट है और इसके विपरीत। स्टार-वर्चस्व और सामान्य वर्चस्व के बीच का अंतर तब अधिक महत्वपूर्ण होता है जब उनके भिन्नात्मक रूपों पर विचार किया जाता है। एक डोमैटिक विभाजन वर्टिकल का विभाजन है जो अलग-अलग वर्चस्व वाले सेटों में होता है। डोमैटिक संख्या एक डोमेटिक विभाजन का अधिकतम आकार है।

एक शाश्वत हावी सेट वर्चस्व का एक गतिशील संस्करण है जिसमें हावी सेट डी में एक शीर्ष वी को चुना जाता है और एक पड़ोसी यू (यू में नहीं है) के साथ बदल दिया जाता है। D) ऐसा है कि संशोधित D भी एक प्रभावशाली सेट है और इस प्रक्रिया को कोने के विकल्पों v के किसी भी अनंत अनुक्रम पर दोहराया जा सकता है।

हावी और स्वतंत्र सेट

डोमिनेटिंग सेट स्वतंत्र सेट (ग्राफ थ्योरी) से निकटता से संबंधित हैं: एक स्वतंत्र सेट भी एक हावी सेट है अगर और केवल अगर यह एक अधिकतम स्वतंत्र सेट है, तो एक ग्राफ में कोई भी अधिकतम स्वतंत्र सेट आवश्यक रूप से एक न्यूनतम हावी सेट भी है।

स्वतंत्र सेटों द्वारा प्रभुत्व

प्रभावशाली समुच्चय स्वतंत्र समुच्चय हो भी सकता है और नहीं भी। उदाहरण के लिए, उपरोक्त आंकड़े (ए) और (बी) स्वतंत्र प्रभावशाली सेट दिखाते हैं, जबकि आंकड़ा (सी) एक प्रभावशाली सेट दिखाता है जो एक स्वतंत्र सेट नहीं है।

'स्वतंत्र प्रभुत्व संख्या' i(G) ग्राफ का G सबसे छोटे हावी होने वाले सेट का आकार है जो एक स्वतंत्र सेट है। समतुल्य रूप से, यह सबसे छोटे अधिकतम स्वतंत्र सेट का आकार है। न्यूनतम में i(G) कम तत्वों पर लिया जाता है (केवल स्वतंत्र सेट माने जाते हैं), इसलिए γ(G) ≤ i(G) सभी रेखांकन के लिए G.

असमानता सख्त हो सकती है - रेखांकन हैं G जिसके लिए γ(G) < i(G). उदाहरण के लिए, चलो G डबल स्टार ग्राफ बनें जिसमें वर्टिकल हों $x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}$, कहाँ p, q > 1. के किनारे G को इस प्रकार परिभाषित किया गया है: प्रत्येक x_i लगी हुई है a, a लगी हुई है b, और b प्रत्येक के निकट है y_j. तब γ(G) = 2 तब से {a, b} सबसे छोटा प्रभावशाली सेट है। अगर p ≤ q, तब i(G) = p + 1 तब से $\{x_{1},\ldots ,x_{p},b\}$ एक सबसे छोटा प्रभावी सेट है जो स्वतंत्र भी है (यह सबसे छोटा अधिकतम स्वतंत्र सेट है)।

ऐसे ग्राफ परिवार हैं जिनमें γ(G) = i(G), यानी हर न्यूनतम अधिकतम स्वतंत्र सेट एक न्यूनतम हावी सेट है। उदाहरण के लिए, γ(G) = i(G) अगर G पंजा मुक्त ग्राफ है।

एक ग्राफ G को वर्चस्व-पूर्ण ग्राफ़ कहा जाता है यदि γ(H) = i(H) हर प्रेरित सबग्राफ में H का G. चूंकि क्लॉ-फ्री ग्राफ का एक प्रेरित सबग्राफ क्लॉ-फ्री है, इसलिए यह इस प्रकार है कि प्रत्येक क्लॉ-फ्री ग्राफ भी वर्चस्व-परिपूर्ण है।

किसी भी ग्राफ के लिए G, इसका लाइन ग्राफ L(G) पंजा-मुक्त है, और इसलिए एक न्यूनतम अधिकतम स्वतंत्र सेट है L(G) भी एक न्यूनतम हावी सेट है L(G). में एक स्वतंत्र सेट L(G) में एक मिलान (ग्राफ सिद्धांत) से मेल खाता है G, और एक हावी सेट में L(G) एक किनारे पर हावी सेट से मेल खाता है G. इसलिए एक न्यूनतम अधिकतम मिलान का आकार न्यूनतम किनारे पर हावी होने वाले सेट के समान होता है।

स्वतंत्र सेटों का वर्चस्व

'स्वतंत्रता प्रभुत्व संख्या' iγ(G) ग्राफ का G सभी स्वतंत्र सेटों में अधिकतम है A का G, हावी होने वाले सबसे छोटे सेट का A. वर्टिकल के सबसेट पर हावी होने के लिए सभी वर्टिकल पर हावी होने की तुलना में संभावित रूप से कम वर्टिकल की आवश्यकता होती है, इसलिए iγ(G) ≤ γ(G) सभी रेखांकन के लिए G.

असमानता सख्त हो सकती है - रेखांकन हैं G जिसके लिए iγ(G) < γ(G). उदाहरण के लिए, कुछ पूर्णांक के लिए n, होने देना G एक ऐसा ग्राफ़ हो जिसमें कोने a की पंक्तियाँ और स्तंभ हों n-द्वारा-n बोर्ड, और ऐसे दो शीर्ष जुड़े हुए हैं यदि और केवल यदि वे प्रतिच्छेद करते हैं। केवल स्वतंत्र सेट केवल पंक्तियों या केवल स्तंभों के सेट होते हैं, और उनमें से प्रत्येक पर एक एकल शीर्ष (एक स्तंभ या एक पंक्ति) का प्रभुत्व हो सकता है, इसलिए iγ(G) = 1. हालाँकि, सभी शीर्षों पर हावी होने के लिए हमें कम से कम एक पंक्ति और एक स्तंभ की आवश्यकता होती है, इसलिए γ(G) = 2. इसके अलावा, के बीच का अनुपात γ(G) / iγ(G) मनमाने ढंग से बड़ा हो सकता है। उदाहरण के लिए, यदि के शिखर G a के वर्गों के सभी उपसमुच्चय हैं n-द्वारा-n बोर्ड, फिर भी iγ(G) = 1, लेकिन γ(G) = n.

द्वि-स्वतंत्र वर्चस्व संख्या iγi(G) ग्राफ का G सभी स्वतंत्र सेटों में अधिकतम है A का G, सबसे छोटे स्वतंत्र सेट का प्रभुत्व A. निम्नलिखित संबंध किसी भी ग्राफ के लिए मान्य हैं G:

$${\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}$$

इतिहास

1950 के दशक के बाद से वर्चस्व की समस्या का अध्ययन किया गया, लेकिन 1970 के दशक के मध्य में प्रभुत्व पर शोध की दर में काफी वृद्धि हुई। 1972 में, रिचर्ड कार्प ने सेट कवर समस्या को एनपी-पूर्ण साबित कर दिया। हावी होने वाली सेट समस्या के लिए इसका तत्काल प्रभाव पड़ा, क्योंकि दो समस्याओं के बीच गैर-विच्छेद-चौराहे के विभाजन को सेट करने और किनारे करने के लिए सीधा शीर्ष है। यह हावी होने वाली सेट समस्या को एनपी-पूर्ण भी साबित करता है।

एल्गोरिदम और कम्प्यूटेशनल जटिलता

सेट कवर समस्या एक प्रसिद्ध एनपी कठिन समस्या है - सेट कवरिंग का निर्णय संस्करण कार्प की 21 एनपी-पूर्ण समस्याओं में से एक था। न्यूनतम हावी सेट समस्या और सेट कवर समस्या के बीच बहुपद-समय एल-कटौती की एक जोड़ी मौजूद है। ये कटौती (#एल-कटौती) दर्शाती हैं कि न्यूनतम हावी सेट समस्या के लिए एक कुशल एल्गोरिदम सेट कवर समस्या के लिए एक कुशल एल्गोरिदम प्रदान करेगा, और इसके विपरीत। इसके अलावा, कटौती सन्निकटन एल्गोरिथ्म को संरक्षित करती है: किसी भी α के लिए, एक बहुपद-समय α-approximation न्यूनतम वर्चस्व वाले सेट के लिए एल्गोरिदम एक बहुपद-समय प्रदान करेगा α-approximation सेट कवर समस्या के लिए एल्गोरिदम और इसके विपरीत। दोनों समस्याएं वास्तव में एपीएक्स # संबंधित जटिलता वर्ग हैं | लॉग-एपीएक्स-पूर्ण।

सेट कवरिंग की अनुमानितता भी अच्छी तरह से समझी जाती है: एक सेट कवर समस्या # लालची एल्गोरिदम का उपयोग करके लॉगरिदमिक सन्निकटन कारक पाया जा सकता है, और एक सबलॉगरिदमिक सन्निकटन कारक खोजना एनपी-हार्ड है। अधिक विशेष रूप से, लालची एल्गोरिथ्म एक कारक प्रदान करता है 1 + log|V| न्यूनतम वर्चस्व वाले सेट का सन्निकटन, और कोई बहुपद समय एल्गोरिथ्म इससे बेहतर सन्निकटन कारक प्राप्त नहीं कर सकता है c log|V| कुछ के लिए c > 0 जब तक पी = एनपी।

एल-कटौती

निम्नलिखित दो कटौती से पता चलता है कि न्यूनतम हावी सेट समस्या और सेट कवर समस्या एल-कटौती के तहत समान हैं: एक समस्या का उदाहरण दिया गया है, हम दूसरी समस्या के समकक्ष उदाहरण का निर्माण कर सकते हैं।

दबंग सेट से सेट कवरिंग तक

एक ग्राफ दिया G = (V, E) साथ V = {1, 2, ..., n}, एक सेट कवर उदाहरण बनाएँ (U, S) निम्नानुसार: ब्रह्मांड (गणित) 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 न्यूनतम सेट कवर के आकार के बराबर है (U, S). इसके अलावा, एक सरल एल्गोरिथ्म है जो एक हावी सेट को समान आकार के सेट कवर और इसके विपरीत मैप करता है। विशेष रूप से, एक कुशल {{nowrap|α-approximation}सेट को कवर करने के लिए } एल्गोरिथ्म एक कुशल प्रदान करता है α-approximation न्यूनतम हावी सेट के लिए एल्गोरिथम।

File:Dominating-set-2.svg

:: उदाहरण के लिए, ग्राफ दिया गया 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₅}. उदाहरण के लिए, शीर्ष 4 ∈ V शीर्ष पर हावी है 3 ∈ D, और तत्व 4 ∈ U सेट में निहित है S₃ ∈ C.

सेट कवरिंग से लेकर डॉमिनेटिंग सेट तक

होने देना (S, U) ब्रह्मांड के साथ सेट कवर समस्या का उदाहरण बनें U और सबसेट का परिवार S = {S_i : i ∈ I}; हम मानते हैं कि U और इंडेक्स सेट I असंबद्ध हैं। एक ग्राफ बनाएँ G = (V, E) निम्नानुसार है: वर्टिकल का सेट है V = I ∪ U, एक किनारा है {i, j} ∈ 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; इस तरह u का प्रभुत्व है i. दूसरा, चूंकि D गैर-खाली होना चाहिए, प्रत्येक i ∈ I में एक शीर्ष के निकट है D.

इसके विपरीत, चलो D के लिए एक हावी सेट हो G. तब एक और प्रभावशाली सेट का निर्माण संभव है X ऐसा है कि |X| ≤ |D| और X ⊆ I: बस प्रत्येक को बदलें u ∈ D ∩ U एक पड़ोसी द्वारा i ∈ I का u. तब C = {S_i : i ∈ X} सेट कवर समस्या का एक व्यवहार्य समाधान है |C| = |X| ≤ |D|.

File:Dominating-set-reduction.svg

:: दाहिनी ओर दिया गया चित्रण इसके निर्माण को दर्शाता है 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 और जो का एक सबसेट है I. हावी सेट X सेट कवर से मेल खाती है C = {S₁, S₃, S₄}.

विशेष मामले

यदि ग्राफ में अधिकतम डिग्री Δ है, तो लालची सन्निकटन एल्गोरिथम एक पाता है O(log Δ)-न्यूनतम हावी सेट का अनुमान। इसके अलावा, चलो d_g लालची सन्निकटन का उपयोग करके प्राप्त हावी होने वाले सेट की प्रमुखता हो तो निम्नलिखित संबंध धारण करता है, $d_{g}\leq N+1-{\sqrt {2M+1}}$, कहाँ N नोड्स की संख्या है और M दिए गए अप्रत्यक्ष ग्राफ़ में किनारों की संख्या है। निश्चित Δ के लिए, यह APX सदस्यता के लिए एक प्रभावशाली सेट के रूप में योग्य है; वास्तव में, यह APX-पूर्ण है।

समस्या विशेष मामलों जैसे यूनिट डिस्क ग्राफ़ और प्लेनर ग्राफ ़ के लिए एक बहुपद-समय सन्निकटन योजना (PTAS) को स्वीकार करती है। श्रृंखला-समानांतर ग्राफ़ में रैखिक समय में एक न्यूनतम प्रभावी सेट पाया जा सकता है।

सटीक एल्गोरिदम

एक का एक न्यूनतम हावी सेट n-वरटेक्स ग्राफ समय में पाया जा सकता है O(2ⁿn) सभी वर्टेक्स सबसेट का निरीक्षण करके। Fomin, Grandoni & Kratsch (2009) दिखाएं कि समय में न्यूनतम हावी सेट कैसे प्राप्त करें O(1.5137ⁿ) और घातीय स्थान, और समय में O(1.5264ⁿ) और बहुपद स्थान। एक तेज एल्गोरिदम, का उपयोग कर O(1.5048ⁿ) समय द्वारा पाया गया van Rooij, Nederlof & van Dijk (2009), जो यह भी दिखाते हैं कि इस समय में न्यूनतम प्रभावी सेटों की संख्या की गणना की जा सकती है। कम से कम हावी होने वाले सेटों की संख्या अधिक से अधिक है 1.7159ⁿ और ऐसे सभी सेटों को समय पर सूचीबद्ध किया जा सकता है O(1.7159ⁿ).

पैरामीटरयुक्त जटिलता

आकार का एक प्रभावशाली सेट ढूँढना k पैरामिट्रीकृत जटिलता के सिद्धांत में एक केंद्रीय भूमिका निभाता है। W(2)|W[2] वर्ग के लिए यह सबसे प्रसिद्ध समस्या है और अन्य समस्याओं की जटिलता दिखाने के लिए कई कटौती में उपयोग किया जाता है। विशेष रूप से, समस्या फिक्स्ड-पैरामीटर ट्रैक्टेबल नहीं है, इस अर्थ में कि चलने वाले समय के साथ कोई एल्गोरिदम नहीं है f(k)n^O(1) किसी भी समारोह के लिए f तब तक मौजूद रहता है जब तक कि W-पदानुक्रम FPT=W[2] तक गिर न जाए।

दूसरी ओर, यदि इनपुट ग्राफ़ प्लानर है, तो समस्या एनपी-हार्ड रहती है, लेकिन एक निश्चित-पैरामीटर एल्गोरिथम ज्ञात है। वास्तव में, समस्या में रैखिक आकार का एक कर्नेल है k, और रनिंग टाइम जो एक्सपोनेंशियल हैं √k और क्यूबिक इन n कर्नेल के शाखा-अपघटन में गतिशील प्रोग्रामिंग लागू करके प्राप्त किया जा सकता है। अधिक आम तौर पर, हावी सेट समस्या और समस्या के कई प्रकार निश्चित-पैरामीटर ट्रैक्टेबल होते हैं जब हावी सेट के आकार और सबसे छोटे वर्जित ग्राफ लक्षण वर्णन पूर्ण द्विदलीय ग्राफ के आकार दोनों द्वारा पैरामीटर किए जाते हैं; यानी, समस्या द्वि-विक्षिप्त ग्राफ़ पर FPT है, विरल ग्राफ़ का एक बहुत ही सामान्य वर्ग जिसमें प्लानर ग्राफ़ शामिल हैं।

एक प्रभावशाली सेट, एक गैर-अवरोधक के लिए पूरक सेट, किसी भी ग्राफ़ पर एक निश्चित-पैरामीटर एल्गोरिथम द्वारा पाया जा सकता है।

यह भी देखें

• विजिंग का अनुमान - ग्राफ के कार्टेशियन उत्पाद की प्रभुत्व संख्या को इसके कारकों की प्रभुत्व संख्या से संबंधित करता है।
• कवर समस्या सेट करें
• बंधन संख्या
• नॉनब्लॉकर - एक हावी सेट का पूरक।

संदर्भ

• Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), "Polynomial-time data reduction for dominating set", Journal of the ACM, 51 (3): 363–384, arXiv:cs/0207066, doi:10.1145/990308.990309, S2CID 488501.
• Allan, Robert B.; Laskar, Renu (1978), "On domination and independent domination numbers of a graph", Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X.
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum dominating set", A Compendium of NP Optimization Problems.
• Dehne, Frank; Fellows, Michael; Fernau, Henning; Prieto, Elena; Rosamond, Frances (2006), "Nonblocker: Parameterized algorithmics for minimum dominating set" (PDF), SOFSEM 2006: 32nd Conference on Current Trends in Theory and Practice of Computer Science, Merin, Czech Republic, January 21-27, 2006, Proceedings, Lecture Notes in Computer Science, vol. 3831, Springer, pp. 237–245, doi:10.1007/11611257_21.
• Escoffier, Bruno; Paschos, Vangelis Th. (2006), "Completeness in approximation classes beyond APX", Theoretical Computer Science, 359 (1–3): 369–377, doi:10.1016/j.tcs.2006.05.023
• Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Claw-free graphs — A survey", Discrete Mathematics, 164 (1–3): 87–147, doi:10.1016/S0012-365X(96)00045-3, MR 1432221.
• Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286, S2CID 1186651.
• Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), "Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications", ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384, S2CID 2489447.
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), "Dominating sets in planar graphs: branch-width and exponential speed-up", SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649, S2CID 5232238.
• Förster, Klaus-Tycho. (2013), "Approximating Fault-Tolerant Domination in General Graphs", Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO, SIAM, pp. 25–32, doi:10.1137/1.9781611973037.4, ISBN 978-1-61197-254-2.
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, p. 190, problem GT2.
• Hedetniemi, S. T.; Laskar, R. C. (1990), "Bibliography on domination in graphs and some basic definitions of domination parameters", Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O.
• Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm{{citation}}: CS1 maint: postscript (link).
• Klasing, Ralf; Laforest, Christian (2004), "Hardness results and approximation algorithms of k-tuple domination in graphs", Information Processing Letters, 89 (2): 75–83, doi:10.1016/j.ipl.2003.10.004.
• Papadimitriou, Christos H.; Yannakakis, Mihailis (1991), "Optimization, Approximation, and Complexity Classes", Journal of Computer and System Sciences, 43 (3): 425–440, doi:10.1016/0022-0000(91)90023-X
• Parekh, Abhay K. (1991), "Analysis of a greedy heuristic for finding small dominating sets in graphs", Information Processing Letters, 39 (5): 237–240, doi:10.1016/0020-0190(91)90021-9
• Raz, R.; Safra, S. (1997), "A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP", Proc. 29th Annual ACM Symposium on Theory of Computing, ACM, pp. 475–484, doi:10.1145/258533.258641, ISBN 0-89791-888-6, S2CID 15457604.
• Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328, S2CID 16082154.
• Telle, Jan Arne; Villanger, Yngve (2012), "FPT algorithms for domination in biclique-free graphs", in Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10–12, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7501, Springer, pp. 802–812, doi:10.1007/978-3-642-33090-2_69.
• van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), "Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets", Proc. 17th Annual European Symposium on Algorithms, ESA 2009, Lecture Notes in Computer Science, vol. 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50, ISBN 978-3-642-04127-3.

अग्रिम पठन

• Grandoni, F. (2006), "A note on the complexity of minimum dominating set", Journal of Discrete Algorithms, 4 (2): 209–214, CiteSeerX 10.1.1.108.3223, doi:10.1016/j.jda.2005.03.002.
• Guha, S.; Khuller, S. (1998), "Approximation algorithms for connected dominating sets" (PDF), Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201, hdl:1903/830, S2CID 1249122.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN 0-8247-0033-3, OCLC 37903553.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, Marcel Dekker, ISBN 0-8247-0034-1, OCLC 38201061.
• West, Douglas B. (2001), Introduction to Graph Theory (2 ed.), Pearson Education.