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

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

ग्राफ सिद्धांत में, ग्राफ के लिए प्रभावी समुच्चय (असतत गणित) G का उपसमुच्चय है, इस प्रकार इसके शीर्ष 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$. और इस रूचिकर अनुभूति के लिए प्रधान समुच्च्यों को प्राप्त किया जाता है। जिसका प्रभुत्व संख्या $\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$. उपरोक्त चित्र (c) प्रधान समुच्चय दिखाता है जो जुड़ा हुआ प्रधान समुच्चय और कुल प्रधान समुच्चय है, इन आंकड़ों के आधार पर (a) और (b) में कोई उदाहरण नहीं हैं। साधारण प्रधान समुच्चय के विपरीत, कुल प्रधान समुच्चय सम्मिलित नहीं हो सकते हैं। उदाहरण के लिए इसके अधिक शीर्षों और बिना किनारों वाले ग्राफ़ में कुल प्रभावी समुच्चय नहीं होते हैं। इसका शक्तिशाली वर्चस्व संख्या 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$ कम से कम है।

इसके विपरीत, एज डोमिनेटिंग समुच्चय या एज-डोमिनेटिंग समुच्चय किनारों का समुच्चय d है, जैसे कि d में नहीं हर किनारा d में कम से कम किनारे से संयोजित रहता है, ऐसा समुच्चय सदैव सम्मिलित होता है (उदाहरण के लिए, सभी किनारों का समुच्चय एज-डोमिनेटिंग समुच्चय होता है)।

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

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

डोमैटिक विभाजन उर्ध्वाधर का विभाजन है जो अलग-अलग वर्चस्व वाले समुच्च्यों में होता है। डोमैटिक संख्या डोमेटिक विभाजन का अधिकतम आकार है।

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

प्रधान और स्वतंत्र समुच्चय

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

स्वतंत्र समुच्च्यों द्वारा प्रभुत्व

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

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

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

एल से होने वाली कमी

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

दबंग समुच्चय से समुच्चय कवरिंग तक

एक ग्राफ दिया 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). इसके अतिरिक्त, सरल एल्गोरिथ्म है जो प्रधान समुच्चय को समान आकार के समुच्चय कवर और इसके विपरीत मैप करता है। विशेष रूप से, कुशल समुच्चय को कवर करने के लिए } एल्गोरिथ्म कुशल प्रदान करता है α-सन्निकटन न्यूनतम प्रधान समुच्चय के लिए एल्गोरिथम का प्रतिनिधित्व करता हैं।

:: उदाहरण के लिए, ग्राफ दिया गया 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| का व्यवहारिक समाधान है।

:: दाहिनी ओर दिया गया चित्रण इसके निर्माण को दर्शाता है 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) को स्वीकार करती है। श्रृंखला-समानांतर ग्राफ़ में रैखिक समय में न्यूनतम प्रभावी समुच्चय पाया जा सकता है।

त्रुटिहीन एल्गोरिदम

इस प्रकार सभी वर्टेक्स उपसमुच्चयों का निरीक्षण करके समय O(2ⁿn) के मान में n-वर्टेक्स ग्राफ का न्यूनतम प्रभावी समुच्चय पाया जा सकता है, फाॅमिन, ग्रैनडोनी & क्रैट्स्च (2009) के द्वारा दिखाएं गए समय में न्यूनतम प्रधान समुच्चय O(1.5137ⁿ) कैसे प्राप्त करें और घातीय स्थान, और समय में O(1.5264ⁿ) और बहुपद स्थान को कैसे प्राप्त करते हैं। इस प्रकार तेज एल्गोरिदम, का उपयोग कर O(1.5048ⁿ) समय वैन रोइजी, नेजेरलाॅफ & वैन डिजिक (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.