न्यूनतम सदस्यता प्रभुत्व सेट समस्या के लिए एल्गोरिदम

एक ग्राफ G = (V, E) और एक पूर्णांक k दिया गया है, न्यूनतम सदस्यता प्रभुत्व सेट समस्या एक सेट S V की गणना करने के लिए कहती है ताकि प्रत्येक v V के लिए, 1 |Nv S| k हो। इस समस्या को विभाजित ग्राफों और समतल द्विआधारी ग्राफों में भी NP-पूर्ण के रूप में जाना जाता है। इस पत्र में, हम समस्या के एल्गोरिदमिक दृष्टिकोण से संपर्क करते हैं और कई दिलचस्प परिणाम प्राप्त करते हैं। हम विभाजित ग्राफों के लिए समस्या के लिए एक O^* (1. 747ⁿ) समय एल्गोरिदम देते हैं। 1-in-3 SAT समस्या के एक विशेष मामले से पुनः कमी का पालन करते हुए, हम दिखाते हैं कि द्विआधारी ग्राफों के लिए, किसी भी k ≥ 2 के लिए O^* (2^o (n)) में चलने वाला कोई उप-एक्सपोनेंशियल समय एल्गोरिदम नहीं है। हम यह भी साबित करते हैं कि जब = k+2, तो समस्या NP-पूर्ण है, किसी भी k ≥ 5 के लिए, यहां तक कि द्विआधारी ग्राफों के लिए। हम समस्या की पैरामीटरयुक्त जटिलता की जांच करते हैं पैरामीटर ट्विन कवर और संयुक्त पैरामीटर क्लस्टर के लिए दूरी, सदस्यता (k) और साबित करते हैं कि समस्या निश्चित-पैरामीटर संभाल योग्य है। एक डायनामिक प्रोग्रामिंग आधारित दृष्टिकोण का उपयोग करते हुए, हम पेड़ों के लिए एक रैखिक-समय एल्गोरिदम प्राप्त करते हैं।