कुशलतापूर्वक सभी जुड़े प्रेरित सबग्राफ

Question

क्या एक कनेक्टेड अप्रत्यक्ष वर्टेक्स-लेबल वाले ग्राफ़ के सभी जुड़े (प्रेरित) उपग्राफ खोजने के लिए एक कुशल (*) एल्गोरिदम है?

(*) मैं सराहना करता हूं कि, सामान्य स्थिति में, इस तरह के किसी भी एल्गोरिदम में ओ (2^एन) जटिलता हो सकती है क्योंकि, एक क्लिक (एन) के लिए, 2^एन जुड़े सबग्राफ होते हैं। हालांकि, जिन ग्राफों के साथ मैं आमतौर पर काम कर रहा हूं, उनके पास बहुत कम जुड़े सबग्राफ होंगे, इसलिए मैं उन्हें सभी 2^एन सबग्राफ पर विचार किए बिना उत्पन्न करने का तरीका ढूंढ रहा हूं और उनसे दूर नहीं हूं जो कि जुड़े नहीं हैं (जैसा कि समाधान this question)।

एक एल्गोरिदम जिसमें समाधान की संख्या में रैखिक चलने वाला समय चल रहा है (यानी यह सभी गैर-समाधानों पर विचार करने में समय बर्बाद किए बिना सीधे ग्राफ की संरचना से समाधान उत्पन्न कर सकता है) स्पष्ट रूप से आदर्श होगा। नोड्स की संख्या में बहुपद है जो एक अतिरिक्त कदम भी ठीक होगा (उदाहरण के लिए ग्राफ के पारगमन बंद करने की पूर्व-कंप्यूटिंग - ऐसा नहीं है कि मुझे लगता है कि इस मामले में मदद मिलेगी)।

वैकल्पिक रूप से, एक सबूत है कि ऐसा कोई समाधान नहीं है, कम से कम मुझे अपने दुख से बाहर कर देगा।

Answer 1

पुनरावर्ती स्यूडोकोड में, 2^n एल्गोरिथ्म

GenerateAndTest(verticesNotYetConsidered, subsetSoFar): 
    if verticesNotYetConsidered is empty: 
     yield subsetSoFar if it induces a connected subgraph 
    else: 
     choose a vertex v in verticesNotYetConsidered 
     GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar) 
     GenerateAndTest(verticesNotYetConsidered - {v}, subsetSoFar union {v}) 

यह कोई फर्क नहीं पड़ता जो शीर्ष वी चुना जाता है; हम भी दो भाई कॉल में अलग-अलग चुन सकते हैं। हम रिकर्सन पेड़ को काटकर लगभग रैखिक-समय एल्गोरिदम (समाधानों की संख्या एन बार) प्राप्त करने के लिए इस स्वतंत्रता का फायदा उठाते हैं।

यदि subsetSoFar खाली है, तो विकल्प अभी भी अनजान है। अन्यथा, हम subsetSoFar में एक कोष्ठक के निकट होने के लिए v चुनते हैं। यदि ऐसा कोई v मौजूद नहीं है, तो हम subsetSoFar उत्पन्न करते हैं और वापस आते हैं, क्योंकि इस उप-क्षेत्र में कोई अन्य समाधान नहीं है।

नया इन्वेरिएंट नोट करें कि subsetSoFar हमेशा कनेक्ट होता है, इसलिए हम स्पष्ट कनेक्टिविटी परीक्षण को समाप्त कर सकते हैं। हम ओ (एन) रिकर्सन पेड़ के प्रत्येक नोड पर काम करते हैं (naively O (n^2) लेकिन हम निकटवर्ती शिखर के सेट को लगातार बढ़ा सकते हैं), जो पूर्ण बाइनरी है और जिनके पत्ते प्रत्येक उपज वास्तव में एक समाधान उत्पन्न करते हैं, इसलिए कुल काम के रूप में दावा किया जाता है (याद रखें कि आंतरिक नोड्स की संख्या पत्तियों की संख्या से कम है)।

नए आविष्कार के कारण, कोई डिस्कनेक्टेड सबग्राफ उत्पन्न नहीं हुआ है।

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

नया छद्म कोड निम्नानुसार है। N(v)v के पड़ोसियों के सेट को दर्शाता है।

GenerateConnectedSubgraphs(verticesNotYetConsidered, subsetSoFar, neighbors): 
    if subsetSoFar is empty: 
     let candidates = verticesNotYetConsidered 
    else 
     let candidates = verticesNotYetConsidered intersect neighbors 
    if candidates is empty: 
     yield subsetSoFar 
    else: 
     choose a vertex v from candidates 
     GenerateConnectedSubgraphs(verticesNotYetConsidered - {v}, 
            subsetSoFar, 
            neighbors) 
     GenerateConnectedSubgraphs(verticesNotYetConsidered - {v}, 
            subsetSoFar union {v}, 
            neighbors union N(v)) 

संपादित करें: अधिकतम डिग्री हे (1) के रेखांकन के लिए, हम verticesNotYetConsidered intersect neighbors को बनाए रखने, जो मैं स्पष्टता के लिए ऐसा नहीं किया द्वारा इस सही मायने में रेखीय समय कर सकते हैं। यदि आप ग्राफ को एक आसन्न मैट्रिक्स के रूप में प्रतिनिधित्व करके शब्द-समांतरता का शोषण करते हैं तो यह अनुकूलन शायद अधिक मूल्यवान नहीं है, जहां प्रत्येक पंक्ति को एक या दो-शब्द बिटमैप के रूप में संग्रहीत किया जाता है।