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

For नियंत्रण प्रवाह रेखांकन में प्रभुत्व, see प्रभुत्व (ग्राफ सिद्धांत).

एक ही ग्राफ के तीन प्रभावशाली समुच्चय (लाल रंग में)। इस ग्राफ की वर्चस्व संख्या 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$. और दिलचस्प चुनौती छोटे हावी सेटों को ढूंढना है। का प्रभुत्व संख्या 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 न्यूनतम हावी समुच्चय के लिए एल्गोरिथम।

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

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

एक का न्यूनतम हावी समुच्चय 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.