Twin-width
एक दिशाहीन ग्राफ की जुड़वां चौड़ाई ग्राफ से जुड़ी एक प्राकृतिक संख्या है, जिसका उपयोग ग्राफ एल्गोरिदम की मानकीकृत जटिलता का अध्ययन करने के लिए किया जाता है। सहज रूप से, यह मापता है कि ग्राफ एक ग्राफ के समान है, एक प्रकार का ग्राफ जिसे बार-बार जुड़वां, शीर्षों को एक साथ मिलाकर एकल शीर्ष तक कम किया जा सकता है, जिनके समान पड़ोसी हैं। जुड़वां-चौड़ाई को बार-बार विलय के एक क्रम से परिभाषित किया जाता है जहां शीर्षों को जुड़वां होने की आवश्यकता नहीं होती है, लेकिन पड़ोसियों के लगभग बराबर समूह होते हैं। परिभाषा जुड़वां चौड़ाई को सीमित सरल दिशाहीन ग्राफ के लिए परिभाषित किया गया है। इनमें शीर्षों का एक सीमित समूह होता है, और किनारों का एक समूह होता है जो शीर्षों के अनियमित जोड़े होते हैं। किसी भी शीर्ष का खुला पड़ोस अन्य शीर्षों का समूह है जिसके साथ इसे ग्राफ के किनारों में जोड़ा जाता है; बंद पड़ोस खुले पड़ोस से शीर्ष को शामिल करके बनाया जाता है। दो शीर्ष सच्चे जुड़वाँ होते हैं जब उनके पास एक ही बंद पड़ोस होता है, और झूठे जुड़वाँ जब उनके पास एक ही खुला पड़ोस होता है; आम तौर पर, सच्चे जुड़वाँ और झूठे जुड़वाँ दोनों को बिना योग्यता के जुड़वाँ कहा जा सकता है। ग्राफों की कई समतुल्य परिभाषाएँ हैं, लेकिन उनमें से एक यह है कि ये ऐसे ग्राफ हैं जिन्हें बार-बार किसी भी दो जुड़वां शीर्षों को खोजने और उन्हें एक ही शीर्ष में विलय करने की प्रक्रिया द्वारा एक ही शीर्ष तक कम किया जा सकता है। एक ग्राफ के लिए, यह कमी प्रक्रिया हमेशा सफल होगी, इससे कोई फर्क नहीं पड़ता कि प्रत्येक चरण में जुड़वा बच्चों का विलय करने के लिए कौन सा विकल्प बनाया जाता है। एक ग्राफ के लिए जो एक ग्राफ नहीं है, यह हमेशा एक उपग्राफ में अटक जाएगा जिसमें दो से अधिक शीर्ष होंगे जिनमें कोई जुड़वां नहीं होगा। जुड़वां चौड़ाई की परिभाषा इस कमी प्रक्रिया की नकल करती है। एक संकुचन अनुक्रम, इस संदर्भ में, चरणों का एक क्रम है, जो दिए गए ग्राफ से शुरू होता है, जिसमें प्रत्येक चरण शीर्षों की एक जोड़ी को एक शीर्ष द्वारा प्रतिस्थापित करता है। यह लाल और काले रंग के किनारों के साथ ग्राफ का एक क्रम उत्पन्न करता है; दिए गए ग्राफ में, सभी किनारों को काला माना जाता है। जब दो शीर्षों को एक शीर्ष द्वारा प्रतिस्थापित किया जाता है, तो नए शीर्ष का पड़ोस प्रतिस्थापित शीर्षों के पड़ोस का संघ होता है। इस नए पड़ोस में, दोनों शीर्षों के पड़ोस में काले किनारों से आने वाला एक किनारा काला रहता है; अन्य सभी किनारे लाल रंग के होते हैं। एक संकुचन अनुक्रम को एक-अनुक्रम कहा जाता है यदि, पूरे अनुक्रम में, प्रत्येक शीर्ष अधिकतम लाल किनारों को छूता है। ग्राफ की जुड़वां चौड़ाई सबसे छोटा मान है जिसके लिए इसका अनुक्रम होता है। एक घने ग्राफ में अभी भी जुड़वां चौड़ाई हो सकती है; उदाहरण के लिए, ग्राफ में सभी पूर्ण ग्राफ शामिल हैं। जुड़वां-चौड़ाई, विरल जुड़वां-चौड़ाई की भिन्नता, व्यक्तिगत ग्राफ के बजाय ग्राफ के परिवारों पर लागू होती है। ग्राफ के एक परिवार के लिए जो प्रेरित उपग्राफ लेने के तहत बंद होता है और जिसमें जुड़वां चौड़ाई होती है, निम्नलिखित गुण समतुल्य हैंः परिवार में ग्राफ विरल होते हैं, जिसका अर्थ है कि उनके पास उनके शीर्षों की संख्या के रैखिक कार्य से बंधे कई किनारे होते हैं। परिवार में सभी पूर्ण द्विदलीय ग्राफ शामिल नहीं हैं। दिए गए परिवार में ग्राफ के सभी उपग्राफों के परिवार ने जुड़वां चौड़ाई को सीमित किया है। परिवार ने सीमित विस्तार किया है, जिसका अर्थ है कि इसके सभी उथले नाबालिग विरल हैं। कहा जाता है कि इस तरह के परिवार में विरल जुड़वां चौड़ाई होती है। जुड़वां-चौड़ाई की अवधारणा को ग्राफ से लेकर विभिन्न पूरी तरह से क्रमबद्ध संरचनाओं (उनके शीर्षों पर कुल क्रम से सुसज्जित ग्राफ सहित) तक सामान्यीकृत किया जा सकता है, और कई मायनों में क्रमबद्ध संरचनाओं के लिए अनियमित ग्राफ की तुलना में सरल है। सीमित डिग्री होने की तुलना में विभिन्न आवश्यकताओं के साथ संकुचन अनुक्रमों का उपयोग करके ग्राफ चौड़ाई की अन्य धारणाओं के लिए समतुल्य परिभाषाएँ तैयार करना भी संभव है। बाउंडेड ट्विन-विड्थ ग्राफ के ग्राफ में ट्विन-विड्थ शून्य होता है। ग्राफ के लिए कटौती प्रक्रिया में, कोई लाल किनारे नहीं होंगेः जब दो शीर्षों को मिला दिया जाता है, तो उनके पड़ोस बराबर होते हैं, इसलिए दो पड़ोसों में से केवल एक से आने वाले किनारे लाल रंग के नहीं होते हैं। किसी भी अन्य ग्राफ में, कोई भी संकुचन अनुक्रम कुछ लाल किनारों का उत्पादन करेगा, और जुड़वां चौड़ाई शून्य से अधिक होगी। अधिक से अधिक तीन शीर्षों वाले पथ ग्राफ ग्राफ होते हैं, लेकिन प्रत्येक बड़े पथ ग्राफ में दोहरी चौड़ाई होती है। एक संकुचन अनुक्रम के लिए जो बार-बार पथ के अंतिम दो किनारों को मिलाता है, केवल एकल विलय किए गए शीर्ष के किनारे की घटना लाल होगी, इसलिए यह एक 1-अनुक्रम है। पेड़ों की अधिकतम दो चौड़ाई होती है, और कुछ पेड़ों के लिए यह तंग होता है। किसी भी पेड़ के लिए 2-संकुचन अनुक्रम एक जड़ का चयन करके पाया जा सकता है, और फिर बार-बार दो पत्तियों को मिलाया जा सकता है जिनमें एक ही मूल होता है या, यदि यह संभव नहीं है, तो सबसे गहरे पत्ते को उसके मूल में मिला दिया जाता है। केवल लाल किनारे पत्तियों को उनके माता-पिता से जोड़ते हैं, और जब एक ही माता-पिता में दो होते हैं तो उन्हें मिलाया जा सकता है, लाल डिग्री को अधिकतम दो पर रखा जा सकता है। अधिक आम तौर पर, ग्राफ के निम्नलिखित वर्गों में बंधी हुई जुड़वां-चौड़ाई होती है, और उनके लिए बंधी हुई चौड़ाई का एक संकुचन अनुक्रम बहुपद समय में पाया जा सकता हैः बंधी हुई गुट-चौड़ाई, या बंधी हुई श्रेणी-चौड़ाई के प्रत्येक ग्राफ में भी बंधी हुई जुड़वां-चौड़ाई होती है। जुड़वां-चौड़ाई समूह-चौड़ाई में सबसे अधिक घातीय होती है, और श्रेणी-चौड़ाई में सबसे अधिक दोगुनी घातीय होती है। इन ग्राफों में, उदाहरण के लिए, दूरी-वंशानुगत ग्राफ, के सीमित मूल्यों के लिए-पत्ती की शक्तियाँ, और सीमित त्रि-चौड़ाई के ग्राफ शामिल हैं। उदासीनता ग्राफ (समान रूप से, इकाई अंतराल ग्राफ या उचित अंतराल ग्राफ) में अधिकतम दो में दोहरी चौड़ाई होती है। इकाई डिस्क के सेट से परिभाषित इकाई डिस्क ग्राफ जो तल के प्रत्येक बिंदु को कई बार सीमित संख्या में कवर करते हैं, वे जुड़वां-चौड़ाई से बंधे होते हैं। उच्च आयामों में इकाई गेंद ग्राफ के लिए भी यही सच है। एक निषिद्ध क्रमपरिवर्तन पैटर्न के साथ क्रमपरिवर्तन से आने वाले क्रमपरिवर्तन ग्राफ में जुड़वां-चौड़ाई होती है। यह वर्जित पैटर्न के साथ क्रमपरिवर्तन पर एल्गोरिथमिक समस्याओं पर जुड़वां-चौड़ाई लागू करने की अनुमति देता है। वर्जित नाबालिगों द्वारा परिभाषित आलेखों के प्रत्येक परिवार में जुड़वां चौड़ाई होती है। उदाहरण के लिए, वैगनर के प्रमेय के अनुसार, समतलीय ग्राफ के लिए निषिद्ध लघु दो ग्राफ हैं और इसलिए समतलीय ग्राफ में जुड़वां-चौड़ाई है। बाउंडेड स्टैक नंबर या बाउंडेड क्यू नंबर के प्रत्येक ग्राफ में भी बाउंडेड ट्विन-विड्थ होती है। बाउंडेड स्पार्स ट्विन-विड्थ के ग्राफ के परिवार मौजूद हैं जिनमें बाउंडेड स्टैक नंबर नहीं है, लेकिन कतार संख्या के लिए संबंधित प्रश्न खुला रहता है। बाउंडेड ट्विन-विड्थ के किसी भी दो ग्राफ का मजबूत उत्पाद, जिसमें से एक बाउंडेड डिग्री है, फिर से बाउंडेड ट्विन-विड्थ है। इसका उपयोग उन ग्राफों के वर्गों की बंधी हुई दोहरी-चौड़ाई को साबित करने के लिए किया जा सकता है जिनमें पथों और बंधी हुई-त्रि-चौड़ाई वाले ग्राफों के मजबूत उत्पादों में अपघटन होते हैं, जैसे कि-समतलीय ग्राफ। आलेखों के शब्दकोश उत्पाद के लिए, जुड़वां चौड़ाई ठीक दो कारक आलेखों की चौड़ाई का अधिकतम है। जुड़वां-चौड़ाई भी कई अन्य मानक ग्राफ उत्पादों के तहत अच्छी तरह से व्यवहार करती है, लेकिन ग्राफ के मॉड्यूलर उत्पाद के तहत नहीं। बंधे हुए जुड़वां चौड़ाई के ग्राफ के प्रत्येक वंशानुगत परिवार में, इसके ग्राफ के शीर्षों के लिए कुल आदेशों का एक परिवार खोजना संभव है ताकि एक प्रेरित उपग्राफ पर विरासत में प्राप्त क्रम भी परिवार में एक क्रम हो, और ताकि परिवार इन आदेशों के संबंध में छोटा हो। इसका मतलब है कि, शीर्षों पर कुल क्रम के लिए, उस क्रम के अनुरूप परिवार में ग्राफ की संख्या सबसे अधिक एकल रूप से घातीय है। इसके विपरीत, इस अर्थ में छोटे क्रमबद्ध आलेखों के प्रत्येक वंशानुगत परिवार ने जुड़वां चौड़ाई को सीमित किया है। मूल रूप से यह अनुमान लगाया गया था कि लेबल किए गए आलेखों का प्रत्येक वंशानुगत परिवार जो छोटा है, इस अर्थ में कि आलेखों की संख्या अधिक से अधिक एक एकल घातीय कारक समय है, ने जुड़वां-चौड़ाई को सीमित किया है। हालांकि, इस अनुमान को एक अनंत केली ग्राफ के प्रेरित उपग्राफ के एक परिवार का उपयोग करके गलत साबित किया गया था जो लेबल किए गए ग्राफ के रूप में छोटे हैं लेकिन इसमें बंधी हुई जुड़वां-चौड़ाई नहीं है। ग्राफ के निम्नलिखित परिवारों के भीतर असीम जुड़वां-चौड़ाई के ग्राफ मौजूद हैंः सीमित डिग्री के ग्राफ। अंतराल ग्राफ। यूनिट डिस्क ग्राफ। इनमें से प्रत्येक मामले में, परिणाम एक गणना तर्क द्वारा अनुसरण किया जाता हैः दिए गए प्रकार के अधिक ग्राफ हैं जो कि बंधे हुए जुड़वां चौड़ाई के ग्राफ हो सकते हैं। गुण यदि एक ग्राफ में जुड़वां चौड़ाई है, तो संकुचन का एक बहुमुखी वृक्ष खोजना संभव है। यह संकुचन अनुक्रमों का एक बड़ा परिवार है, सभी कुछ (बड़ी) बंधी हुई चौड़ाई है, ताकि प्रत्येक अनुक्रम में प्रत्येक चरण पर रैखिक रूप से शीर्षों के कई असंबद्ध जोड़े हों, जिनमें से प्रत्येक को अनुक्रम में अगले चरण में अनुबंधित किया जा सकता है। इससे यह पता चलता है कि दिए गए शीर्षों के किसी भी समूह पर बंधे हुए जुड़वां-चौड़ाई के ग्राफ की संख्या केवल एक एकल घातीय कारक से बड़ी होती है, कि बंधे हुए जुड़वां-चौड़ाई के ग्राफ में प्रति शीर्ष बिट्स की केवल एक लघुगणक संख्या के साथ एक निकटता लेबलिंग योजना होती है, और उनके पास बहुपद आकार के सार्वभौमिक ग्राफ होते हैं जिसमें बंधे हुए जुड़वां-चौड़ाई के प्रत्येक-वर्टेक्स ग्राफ को एक प्रेरित उपग्राफ के रूप में पाया जा सकता है। एल्गोरिदम बहुपद समय में अधिकतम एक पर जुड़वां चौड़ाई के ग्राफ को पहचाना जा सकता है। हालांकि, यह निर्धारित करने के लिए एन. पी.-पूर्ण है कि क्या दिए गए ग्राफ में अधिकतम चार पर जुड़वां-चौड़ाई है, और 5/4 से बेहतर सन्निकटन अनुपात के साथ जुड़वां-चौड़ाई का अनुमान लगाने के लिए एन. पी.-कठिन है। घातीय समय परिकल्पना के तहत, जुड़वां-चौड़ाई की गणना करने के लिए-वर्टेक्स ग्राफ में कम से कम घातीय समय की आवश्यकता होती है। व्यवहार में, एस. ए. टी. समाधानकों का उपयोग करके मध्यम आकार के ग्राफ की दोहरी चौड़ाई की गणना करना संभव है। बाउंडेड ट्विन-विड्थ के ग्राफ के अधिकांश ज्ञात परिवारों के लिए, बहुपद समय में बाउंडेड विड्थ के संकुचन अनुक्रम का निर्माण करना संभव है। एक बार संकुचन अनुक्रम दिए जाने या बनाए जाने के बाद, कई अलग-अलग एल्गोरिदमिक समस्याओं को इसका उपयोग करके हल किया जा सकता है, कई मामलों में उन ग्राफों के लिए अधिक कुशलता से संभव है जिनमें बंधी हुई दोहरी चौड़ाई नहीं है। जैसा कि नीचे विस्तृत किया गया है, इनमें एन. पी.-कठिन समस्याओं के लिए सटीक मानकीकृत एल्गोरिदम और सन्निकटन एल्गोरिदम शामिल हैं, साथ ही कुछ समस्याएं जिनमें शास्त्रीय बहुपद समय एल्गोरिदम हैं, लेकिन फिर भी बंधी हुई जुड़वां-चौड़ाई की धारणा का उपयोग करके गति बढ़ाई जा सकती है। मानकीकृत एल्गोरिदम एक संबंधित पैरामीटर वाले ग्राफ पर एक एल्गोरिदमिक समस्या को फिक्स्ड-पैरामीटर ट्रैक्टेबल कहा जाता है यदि इसमें एक एल्गोरिदम है, जो शीर्ष और पैरामीटर मूल्य वाले ग्राफ पर, कुछ स्थिर और कम्प्यूटेबल फ़ंक्शन के लिए समय पर चलता है। उदाहरण के लिए, का एक चलने का समय इस अर्थ में निश्चित-पैरामीटर ट्रैक्टेबल होगा। विश्लेषण की इस शैली को आम तौर पर उन समस्याओं पर लागू किया जाता है जिनमें ज्ञात बहुपद-समय एल्गोरिदम नहीं होता है, क्योंकि अन्यथा निश्चित-पैरामीटर ट्रैक्टेबिलिटी तुच्छ होगी। ऐसी कई समस्याओं को एक पैरामीटर के रूप में जुड़वां चौड़ाई के साथ निश्चित-पैरामीटर ट्रैक्टेबल दिखाया गया है, जब बाउंडेड चौड़ाई का एक संकुचन अनुक्रम इनपुट के हिस्से के रूप में दिया जाता है। यह, विशेष रूप से, ऊपर सूचीबद्ध बंधी हुई जुड़वां-चौड़ाई के ग्राफ परिवारों पर लागू होता है, जिसके लिए एक संकुचन अनुक्रम का कुशलता से निर्माण किया जा सकता है। हालाँकि, यह ज्ञात नहीं है कि कम जुड़वां-चौड़ाई के मनमाने ग्राफ के लिए एक अच्छा संकुचन अनुक्रम कैसे पाया जाए, जबकि ग्राफ में कोई अन्य संरचना ज्ञात नहीं है। दिए गए संकुचन अनुक्रमों के साथ बंधे हुए जुड़वां-चौड़ाई के ग्राफ के लिए निश्चित-पैरामीटर ट्रैक्टेबल समस्याओं में शामिल हैंः यह परीक्षण करना कि क्या दिया गया ग्राफ ग्राफ के प्रथम-क्रम तर्क में किसी भी दिए गए गुण को मॉडल करता है। यहाँ, संपत्ति की दोहरी चौड़ाई और विवरण की लंबाई दोनों विश्लेषण के मापदंड हैं। इस प्रकार की समस्याओं में बाउंडेड साइज के सबग्राफ के लिए सबग्राफ आइसोमोर्फिज्म, और बाउंडेड साइज के कवर या डोमिनेंट सेट के लिए वर्टेक्स कवर और डोमिनेंट सेट प्रॉब्लम्स शामिल हैं। गुण का वर्णन करने वाले तार्किक सूत्र की लंबाई पर इन सामान्य विधियों की निर्भरता चतुष्कोणीय है, लेकिन स्वतंत्र सेट, हावी सेट और संबंधित समस्याओं के लिए इसे स्वतंत्र या हावी सेट के आकार में घातीय तक कम किया जा सकता है, और उपग्राफ समरूपता के लिए इसे उपग्राफ के शीर्षों की संख्या में भाज्य तक कम किया जा सकता है। उदाहरण के लिए, एक दिए गए अनुक्रम के साथ एक-वर्टेक्स ग्राफ के लिए एक-वर्टेक्स स्वतंत्र सेट खोजने का समय, एक गतिशील प्रोग्रामिंग एल्गोरिथ्म द्वारा है जो संकुचन अनुक्रम की आगे की दिशा में लाल ग्राफ के छोटे जुड़े उपग्राफ पर विचार करता है। घातीय समय परिकल्पना के तहत, ये समय सीमाएं घातांक में लघुगणक कारकों तक इष्टतम हैं। पूरी तरह से क्रमबद्ध शीर्षों के साथ ग्राफ के लिए ग्राफ के प्रथम-क्रम तर्क के विस्तार के लिए, और तार्किक भविष्यवाणी जो इस क्रम का परीक्षण कर सकते हैं, मॉडल जाँच अभी भी बंधे हुए जुड़वां-चौड़ाई के वंशानुगत ग्राफ परिवारों के लिए निश्चित-पैरामीटर ट्रैक्टेबल है, लेकिन (मानक जटिलता-सैद्धांतिक धारणाओं के तहत) असीम जुड़वां-चौड़ाई के वंशानुगत परिवारों के लिए नहीं। बंधे हुए जुड़वां-चौड़ाई के रंग ग्राफ, कई रंगों का उपयोग करते हुए जो उनकी जुड़वां-चौड़ाई और उनके सबसे बड़े गुट के आकार के एक कार्य से बंधे होते हैं। उदाहरण के लिए, जुड़वां चौड़ाई के त्रिभुज-मुक्त ग्राफ को एक लालची रंग एल्गोरिदम द्वारा रंगीन किया जा सकता है जो शीर्षों को उस क्रम के विपरीत रंग देता है जिस क्रम में उन्हें संकुचित किया गया था। इस परिणाम से पता चलता है कि बंधे हुए जुड़वां-चौड़ाई के ग्राफ χ-बंधे हैं। बाउंडेड स्पार्स ट्विन-विड्थ के ग्राफ परिवारों के लिए, सामान्यीकृत रंग संख्याएँ बाउंडेड हैं। यहाँ, सामान्यीकृत रंग संख्या अधिक से अधिक है यदि शीर्षों को इस तरह से रैखिक रूप से क्रमबद्ध किया जा सकता है कि प्रत्येक शीर्ष क्रम में सबसे पहले के शीर्षों तक पहुँच सके, क्रम में बाद के शीर्षों के माध्यम से लंबाई के पथ के माध्यम से। शास्त्रीय एल्गोरिदम की गति बढ़ाना बंधे हुए जुड़वां-चौड़ाई वाले ग्राफों में, शीर्षों वाले ग्राफ पर, समय के साथ, चौड़ाई-पहली खोज करना संभव है, तब भी जब ग्राफ घना हो और इस समय सीमा से अधिक किनारे हों। सन्निकटन एल्गोरिदम में जुड़वां चौड़ाई वाले सन्निकटन एल्गोरिदम को भी लागू किया गया है। विशेष रूप से, बंधे हुए जुड़वां-चौड़ाई के ग्राफ में, बंधे हुए सन्निकटन अनुपात के साथ न्यूनतम हावी सेट के लिए एक सन्निकटन खोजना संभव है। यह अधिक सामान्य आलेखों के विपरीत है, जिसके लिए लघुगणक की तुलना में बेहतर सन्निकटन अनुपात प्राप्त करना एन. पी.-कठिन है। अधिकतम स्वतंत्र सेट और ग्राफ रंग समस्याओं को बंधे हुए जुड़वां चौड़ाई के ग्राफ पर बहुपद समय में, प्रत्येक के लिए, एक अनुमानित अनुपात के भीतर अनुमानित किया जा सकता है। इसके विपरीत, बंधी हुई जुड़वां-चौड़ाई की धारणा के बिना, इस रूप के किसी भी सन्निकटन अनुपात को प्राप्त करना एन. पी.-कठिन है। संदर्भ आगे पढ़ने के लिए ग्राफ अपरिवर्तनीय