फीडबैक आर्क सेट

एक दिष्ट ग्राफ़ का न्यूनतम फीडबैक चाप समुच्चय (लाल डैशित किनारे) और अधिकतम अचक्रीय उपग्राफ (नीला ठोस किनारा) में विभाजन

ग्राफ़ सिद्धांत और ग्राफ एल्गोरिथ्म में, एक दिष्ट ग्राफ में फीडबैक चाप समुच्चय या फीडबैक किनारा समुच्चय ग्राफ़ के किनारों का एक उपसमूह होता है जिसमें ग्राफ़ के प्रत्येक चक्र में से कम से कम एक किनारा होता है। ग्राफ़ से इन किनारों को हटाने से सभी चक्र टूट जाते हैं, जिससे एक दिष्ट अचक्रीय ग्राफ बनता है, जो दिए गए ग्राफ़ का एक अचक्रीय उपग्राफ होता है। सबसे कम संभावित किनारों के साथ समुच्चय किया गया फीडबैक चाप न्यूनतम फीडबैक चाप समुच्चय है और इसका अपनेय (रिमूवल) अधिकतम अचक्रीय उपग्राफ छोड़ता है; इन इष्टमीकरण समस्याओं के भारित संस्करणों का भी उपयोग किया जाता है। यदि फीडबैक चाप समुच्चय न्यूनतम है, जिसका अर्थ है कि इसमें से किसी भी किनारे को हटाने से एक उपसमुच्चय उत्पन्न होता है जो फीडबैक चाप समुच्चय नहीं है, तो इसमें एक अतिरिक्त गुण होता है: इसके सभी किनारों को हटाने के बजाय उन्हें उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता है।

फीडबैक चाप समुच्चय में परिपथ विश्लेषण, रासायनिक अभियांट्रिकी, गतिरोध वियोजन, कोटिकृत वोटिंग, गणितीय मनोविज्ञान, व्यावहारिकी और ग्राफ आरेखण में अनुप्रयोग होते हैं। न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ खोज NP-कठिन है; इसे बिल्कुल घातांकी समय में, या निश्चित-प्राचल ट्रैक्टेबल समय में हल किया जा सकता है। बहुपद काल में, न्यूनतम फीडबैक चाप समुच्चय को एक बहुगणितीय सन्निकटन अनुपात के भीतर सन्निकटित किया जा सकता है, और अधिकतम अचक्रीय उपग्राफ को एक नियत घटक के भीतर सन्निकटित किया जा सकता है। दोनों को कुछ नियत घटकों की तुलना में समीप लाना कठिन है, एक अप्रत्याशितता परिणाम जिसे अद्वितीय गेम निराधार के अंतर्गत मजबूत किया जा सकता है। टूर्नामेंट ग्राफों के लिए, न्यूनतम फीडबैक चाप समुच्चय का सन्निकट अधिक सटीक रूप से लगाया जा सकता है, और समतल ग्राफों के लिए दोनों समस्याओं को बहुपद काल में बिल्कुल हल किया जा सकता है।

एक निकट से संबंधित समस्या, फीडबैक शीर्ष समुच्चय, एक दिष्ट या अदिष्‍ट ग्राफ में प्रत्येक चक्र से कम से कम एक शीर्ष युक्त शीर्षों का एक समुच्चय है। अदिष्‍ट ग्राफों में, विस्तरित वृक्ष सबसे बड़े चक्रीय उपग्राफ होते हैं, और एक विस्तरित वृक्ष को बनाने में हटाए गए किनारों की संख्या परिपथ कोटि होती है।

अनुप्रयोग

2016 ओलंपिक में पुरुषों के बीच वॉलीबॉल के स्कोर, पूल एफ, और इन स्कोरों के लिए न्यूनतम-अपसैट (परिवर्तन) रैंकिंग थी। प्रत्येक मैच में हारने वाले से विजेता की ओर तीर लगाए जाते हैं, और जब परिणाम रैंकिंग के अनुरूप होता है तो उन्हें नीला रंग दिया जाता है और परिवर्तन के लिए लाल रंग दिया जाता है, जो परिणाम रैंकिंग के साथ असंगत होता है। इस रैंकिंग के साथ, केवल एक मैच परिवर्तन वाला है, जिसमें यूएसए ने क्यूएटी को हराया था। ओलंपिक में उपयोग की जाने वाली वास्तविक रैंकिंग निर्धारित अनुपात पर ईएसपी को क्यूएटी से आगे रखने से भिन्न थी, जिससे उनके मैच को एक और परिवर्तन के रूप में स्थान दिया गया।

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

• राउंड-रॉबिन खेल वाली खेल संबन्धी प्रतिस्पर्धाओं में, प्रत्येक गेम के परिणामों को प्रत्येक गेम के हारने वाले से विजेता की ओर दिष्ट करके दर्ज किया जा सकता है। परिणामी ग्राफ़ में न्यूनतम फीडबैक चाप समुच्चय खोजना, उसके किनारों को उत्क्रमी करना, और सांस्थितिक क्रमण, सभी प्रतिस्पर्धियों पर एक रैंकिंग तैयार करता है। रैंकिंग चुनने के विभिन्न तरीकों के मध्य, यह अप्सेट की कुल संख्या को कम करता है, ऐसे खेल जिनमें कम रैंक वाले प्रतियोगी ने उच्च रैंक वाले प्रतियोगी को हराया है। कई स्पोर्टस प्रत्येक गेम के लिए दिए गए अंकों के आधार पर समूह टूर्नामेंट रैंकिंग पद्धतियों के लिए सरल तरीकों का उपयोग करते हैं; ये तरीके न्यूनतम-अप्सेट रैंकिंग का निरंतर सन्निकटन प्रदान कर सकते हैं।
• प्राइमेटविज्ञान में और आम तौर पर व्यावहारिकी में, प्रभाविता पदानुक्रम अधिकतर देखे गए प्रभाविता व्यवहार में सबसे कम परिवर्तन के साथ एक अनुक्रम की खोज करके निर्धारित किया जाता है, जो न्यूनतम फीडबैक चाप समुच्चय समस्या का दूसरा रूप है।
• गणितीय मनोविज्ञान में, किसी दिए गए निकष के अनुसार विषयों की वस्तुओं के समुच्चय की रैंकिंग निर्धारित करना दिलचस्प है, जैसे कि उनकी अधिमान्यता या प्रत्यक्षण की उनकी धारणा, वस्तुओं के सभी युग्मों के मध्य युग्‍मानूसार तुलना के आधार पर है। टूर्नामेंट ग्राफ़ में निर्धारित न्यूनतम फीडबैक चाप एक रैंकिंग प्रदान करता है जो यथासंभव कुछ युग्‍मानूसार परिणामों से असहमत होता है। वैकल्पिक रूप से, इन तुलनाओं के परिणामस्वरूप प्रत्येक युग्‍मानूसार अनुक्रम के लिए स्वतंत्र प्रायिकताऐं होती हैं|
• अधिकतम-संभाव्यता क्रमण का उपयोग क्रमबंधन, सांख्यिकी में समस्या और अवयवों को रैखिक अनुक्रम में व्यवस्थि करने के अन्वेषी डेटा विश्लेषण के लिए किया जा सकता है, ऐसी स्थितियों में जहां डेटा उपलब्ध है जो अवयवों के मध्य युग्‍मानूसार तुलना प्रदान करता है।
• रैंकिंग वोटिंग में, केमेनी-यंग पद्धति को एक ऐसे क्रम की खोज के रूप में वर्णित किया जा सकता है जो उस युग्म के लिए विपरीत अनुक्रम को अधिमान करने वाले मतदाताओं की संख्या के उम्मीदवारों के युग्मों के योग को कम करता है। इसे न्यूनतम-वजन फीडबैक चाप समुच्चय समस्या के रूप में तैयार और हल किया जा सकता है, जिसमें कोने उम्मीदवारों का प्रतिनिधित्व करते हैं, किनारों को प्रत्येक आमने-सामने की प्रतियोगिता के विजेता का प्रतिनिधित्व करने के लिए दिष्ट किया जाता है, और प्रत्येक किनारे की लागत संख्या का प्रतिनिधित्व करती है आमने-सामने हारने वाले को ऊंची रैंकिंग देने से मतदाता नाखुश हो जाएंगे।

फीडबैक चाप समुच्चय का एक और प्रारंभिक अनुप्रयोग अनुक्रमिक लॉजिक सर्किट के डिजाइन से संबंधित है, जिसमें सिग्नल हमेशा इनपुट से आउटपुट तक बढ़ने के बजाय सर्किट के माध्यम से चक्र में फैल सकते हैं। ऐसे सर्किट में, न्यूनतम फीडबैक चाप समुच्चय उन बिंदुओं की संख्या को दर्शाता है जिन पर सूचना के नुकसान के बिना संकेतों को प्रसारित करने की अनुमति देने के लिए प्रवर्धन आवश्यक है। एसिंक्रोनस घटकों से बने तुल्यकालिक सर्किट में, फीडबैक चाप समुच्चय के किनारों पर क्लॉक्ड गेट लगाकर सिंक्रोनाइज़ेशन प्राप्त किया जा सकता है। इसके अतिरिक्त, एक फीडबैक चाप समुच्चय पर एक सर्किट को काटने से शेष सर्किट संयोजन तर्क में कम हो जाता है, जिससे इसका विश्लेषण सरल हो जाता है, और फीडबैक चाप समुच्चय का आकार नियंत्रित करता है कि कट में सर्किट के व्यवहार को समझने के लिए कितने अतिरिक्त विश्लेषण की आवश्यकता है। इसी तरह, केमिकल इंजीनियरिंग में प्रक्रिया फ़्लोशीटिंग में, फीडबैक चाप समुच्चय पर प्रोसेस फ्लो आरेख के किनारों को तोड़ना, और उन किनारों पर मूल्यों के लिए सभी संभावनाओं का अनुमान लगाना या प्रयास करना, बाकी प्रक्रिया को व्यवस्थित तरीके से विश्लेषण करने की अनुमति देता है क्योंकि इसकी चक्रीयता का. इस एप्लिकेशन में, किनारों को इस तरह से तोड़ने के विचार को फाड़ना कहा जाता है।

स्तरित ग्राफ ड्राइंग में, किसी दिए गए दिष्ट ग्राफ के शीर्षों को उपसमुच्चय (ड्राइंग की परतें) के एक क्रमबद्ध अनुक्रम में विभाजित किया जाता है, और प्रत्येक उपसमुच्चय को इस ड्राइंग की क्षैतिज रेखा के साथ रखा जाता है, जिसके किनारे ऊपर और नीचे की ओर बढ़ते हैं। परतें. इस प्रकार की ड्राइंग में, यह वांछनीय है कि अधिकांश या सभी किनारों को ऊपर और नीचे के किनारों को मिलाने के बजाय लगातार नीचे की ओर उन्मुख किया जाए, ताकि ड्राइंग में रीचैबिलिटी संबंध अधिक स्पष्ट रूप से स्पष्ट हो सकें। यह एक न्यूनतम या न्यूनतम फीडबैक चाप समुच्चय ढूंढकर, उस समुच्चय में किनारों को उलट कर, और फिर परतों में विभाजन को इस तरह से चुनकर प्राप्त किया जाता है जो परिणामी अचक्रीयग्राफ के टोपोलॉजिकल क्रम के अनुरूप हो। फीडबैक चाप समुच्चय का उपयोग स्तरित ग्राफ ड्राइंग की एक अलग उपसमस्या के लिए भी किया गया है, परतों के लगातार जोड़े के भीतर शीर्षों का क्रम।

ऑपरेटिंग सिस्टम में गतिरोध समाधान में, गतिरोध को तोड़ने के लिए निर्भरता की सबसे छोटी संख्या को हटाने की समस्या को न्यूनतम फीडबैक चाप समुच्चय खोजने में से एक के रूप में तैयार किया जा सकता है। हालाँकि, इस समुच्चय को खोजने की कम्प्यूटेशनल कठिनाई और ऑपरेटिंग सिस्टम घटकों के भीतर गति की आवश्यकता के कारण, इस एप्लिकेशन में अक्सर सटीक एल्गोरिदम के बजाय अनुमान का उपयोग किया जाता है।

एल्गोरिदम

समतुल्यताएं

सटीक अनुकूलन के प्रयोजनों के लिए न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ समतुल्य हैं, क्योंकि एक दूसरे का पूरक समुच्चय है। हालाँकि, पैरामीटरयुक्त जटिलता और सन्निकटन के लिए, वे भिन्न होते हैं, क्योंकि उन प्रकार के एल्गोरिदम के लिए उपयोग किया जाने वाला विश्लेषण समाधान के आकार पर निर्भर करता है, न कि केवल इनपुट ग्राफ़ के आकार पर, और न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ अलग-अलग होते हैं एक दूसरे से आकार.

किसी दिए गए ग्राफ़ का फीडबैक चाप समुच्चय $G$ दिष्ट रेखा ग्राफ़ के फीडबैक शीर्ष समुच्चय के समान है of $G$. यहां, एक फीडबैक वर्टेक्स समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है, ग्राफ के शीर्षों के एक उपसमुच्चय के रूप में जिसका विलोपन सभी चक्रों को खत्म कर देगा। दिष्ट ग्राफ़ का रेखा ग्राफ़ $G$ प्रत्येक किनारे के लिए एक शीर्ष है of $G$, और प्रत्येक दो-किनारे पथ के लिए एक किनारा in $G$. दूसरी दिशा में, किसी दिए गए ग्राफ़ का न्यूनतम फीडबैक शीर्ष समुच्चय $G$ के प्रत्येक शीर्ष को विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या का समाधान प्राप्त किया जा सकता है $G$ दो शीर्षों में, एक आने वाले किनारों के लिए और एक बाहर जाने वाले किनारों के लिए। ये परिवर्तन फीडबैक चाप समुच्चय और फीडबैक वर्टेक्स समुच्चय के लिए सटीक एल्गोरिदम को उनकी जटिलता सीमाओं के उचित अनुवाद के साथ एक-दूसरे में परिवर्तित करने की अनुमति देते हैं। हालाँकि, यह परिवर्तन अधिकतम अचक्रीयउपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।

तीन दृढ़ता से संयोजित घटकों के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष $d$ पर द्वियोजी घटकों में विभाजित किया जा सकता है, प्रत्येक दो शीर्षों का एक चक्र है। फीडबैक चाप समुच्चय समस्या को प्रत्येक मजबूती से जुड़े घटक में और मजबूती से जुड़े घटक के प्रत्येक द्वि-कनेक्टेड घटक में अलग से हल किया जा सकता है।

फीडबैक चाप समुच्चय समस्या के सटीक और अनुमानित दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक मजबूती से जुड़े घटक को अलग से हल करना और इन दृढ़ता से जुड़े घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके द्वि-जुड़े घटकों को और भी दूर तक तोड़ना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटक में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में शामिल करने के लिए बेकार हैं। जब इन घटकों में से एक को दो शीर्षों को हटाकर दो डिस्कनेक्ट किए गए उपग्राफ में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है, जिससे समस्या को इसके दृढ़ता से जुड़े घटकों के एसपीक्यूआर पेड़ से प्राप्त उप-समस्याओं में विभाजित किया जा सकता है।

सटीक

न्यूनतम फीडबैक चाप समुच्चय को खोजने का एक तरीका शीर्षों के क्रम की खोज करना है, ताकि क्रम में यथासंभव कुछ किनारों को बाद के शीर्षों से पहले के शीर्षों की ओर दिष्ट किया जा सके। एक के सभी क्रमपरिवर्तन खोज रहे हैं $n$-vertex ग्राफ लगेगा time $O(n!)$, लेकिन हेल्ड-कार्प एल्गोरिदम पर आधारित एक गतिशील प्रोग्रामिंग विधि इष्टतम क्रमपरिवर्तन पा सकती है time $O(n2^{n})$, स्थान की घातीय मात्रा का भी उपयोग कर रहा है। एक फूट डालो और जीतो एल्गोरिथ्म जो शीर्षों के सभी विभाजनों को दो समान उपसमुच्चयों में परीक्षण करता है और प्रत्येक उपसमुच्चय के भीतर पुनरावृत्ति करता है, समस्या को हल कर सकता है time $O(4^{n}/{\sqrt {n}})$, बहुपद स्थान का उपयोग करना।

पैरामीटरयुक्त जटिलता में, एल्गोरिदम के लिए समय को न केवल इनपुट ग्राफ़ के आकार के संदर्भ में मापा जाता है, बल्कि ग्राफ़ के एक अलग पैरामीटर के संदर्भ में भी मापा जाता है। विशेष रूप से, न्यूनतम फीडबैक चाप समुच्चय समस्या के लिए, तथाकथित प्राकृतिक पैरामीटर न्यूनतम फीडबैक चाप समुच्चय का आकार है। के साथ ग्राफ़ पर $n$ शिखर, प्राकृतिक के साथ parameter $k$, फीडबैक चाप समुच्चय समस्या को हल किया जा सकता है time $O(n^{4}4^{k}k^{3}k!)$, इसे समतुल्य फीडबैक वर्टेक्स समुच्चय समस्या में परिवर्तित करके और एक पैरामीटरयुक्त फीडबैक वर्टेक्स समुच्चय एल्गोरिदम लागू करके। क्योंकि के प्रतिपादक $n$ इस एल्गोरिथ्म में है constant $4$, स्वतंत्र of $k$, इस एल्गोरिदम को फिक्स्ड-पैरामीटर ट्रैक्टेबल कहा जाता है।

प्राकृतिक मापदण्ड के अतिरिक्त अन्य मापदण्डों का भी अध्ययन किया गया है। डायनेमिक प्रोग्रामिंग का उपयोग करके एक निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम न्यूनतम फीडबैक चाप समुच्चय पा सकता है time $O(2^{r}m^{4}\log m)$, कहाँ $r$ अंतर्निहित अप्रत्यक्ष ग्राफ़ का सर्किट रैंक है। सर्किट रैंक फीडबैक चाप समुच्चय का एक अप्रत्यक्ष एनालॉग है, किनारों की न्यूनतम संख्या जिसे ग्राफ़ से एक फैले हुए पेड़ तक कम करने के लिए हटाने की आवश्यकता होती है; न्यूनतम फीडबैक चाप समुच्चय की तुलना में इसकी गणना करना बहुत आसान है। के ग्राफ़ के लिए treewidth $t$, ग्राफ़ के पेड़ के अपघटन पर गतिशील प्रोग्रामिंग ग्राफ़ आकार और घातांक में समय बहुपद में निर्धारित न्यूनतम फीडबैक चाप पा सकती है in $O(t\log t)$.घातांकीय समय परिकल्पना के अंतर्गत, इससे बेहतर कोई निर्भरता नहीं $t$ संभव है।

फीडबैक चाप समुच्चय के आकार को कम करने के बजाय, शोधकर्ताओं ने किसी भी शीर्ष से हटाए गए किनारों की अधिकतम संख्या को कम करने पर भी ध्यान दिया है। समस्या की इस भिन्नता को रैखिक समय में हल किया जा सकता है। सभी न्यूनतम फीडबैक चाप समुच्चय को प्रति समुच्चय बहुपद विलंब के साथ एक एल्गोरिदम द्वारा सूचीबद्ध किया जा सकता है।

अनुमानित

Unsolved problem in mathematics:

Does the feedback arc set problem have an approximation algorithm with a constant approximation ratio?

(more unsolved problems in mathematics)

फीडबैक चाप समुच्चय के लिए सबसे प्रसिद्ध बहुपद-समय सन्निकटन एल्गोरिथ्म में गैर-स्थिर सन्निकटन अनुपात है $O(\log n\log \log n)$. इसका मतलब यह है कि फीडबैक चाप समुच्चय का आकार जो इसे मिलता है वह अधिकतम इस कारक से इष्टतम से बड़ा है। यह निर्धारित करना कि क्या फीडबैक चाप समुच्चय में एक स्थिर-अनुपात सन्निकटन एल्गोरिथ्म है, या क्या एक गैर-स्थिर अनुपात आवश्यक है, एक खुली समस्या बनी हुई है।

अधिकतम अचक्रीयउपग्राफ समस्या में एक आसान सन्निकटन एल्गोरिथ्म है जो एक सन्निकटन अनुपात प्राप्त करता है of ${\tfrac {1}{2}}$:

• शीर्षों का मनमाना क्रम ठीक करें
• किनारों को दो अचक्रीय उपसमूहों में विभाजित करें, एक में किनारे क्रम के अनुरूप दिष्ट होते हैं, और दूसरे में क्रम के विपरीत दिशा में दिष्ट किनारे होते हैं।
• दो उपग्राफों में से बड़े को लौटाएँ।

ऑर्डर चुनने के लिए एक लालची एल्गोरिदम का उपयोग करके इसे बेहतर बनाया जा सकता है। यह एल्गोरिदम एक शीर्ष को ढूंढता है और हटा देता है जिसके आने वाले और बाहर जाने वाले किनारों की संख्या यथासंभव दूर होती है, शेष ग्राफ़ को पुनरावर्ती रूप से ऑर्डर करती है, और फिर हटाए गए शीर्ष को परिणामी क्रम के एक छोर पर रखती है। के साथ ग्राफ़ के लिए $m$ किनारों और $n$ शीर्षों पर, यह एक चक्रीय उपग्राफ उत्पन्न करता है $m/2+n/6$ किनारे, रैखिक समय में, एक सन्निकटन अनुपात देते हैं of ${\tfrac {1}{2}}+\Omega (n/m)$. एक और, अधिक जटिल, बहुपद समय सन्निकटन एल्गोरिदम अधिकतम वाले ग्राफ़ पर लागू होता है degree $\Delta$, और एक अचक्रीयउपग्राफ़ पाता है $m/2+\Omega (m/{\sqrt {\Delta }})$ किनारों, का एक सन्निकटन अनुपात दे रहा है form ${\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})$. कब $\Delta =3$, सन्निकटन अनुपात $8/9$ हासिल किया जा सकता है।

प्रतिबंधित इनपुट

दिष्ट समतलीय ग्राफ़ में, फीडबैक चाप समुच्चय समस्या परिणामी ग्राफ़ को मजबूती दृढ़ता से जुड़ा हुआ ग्राफ़ बनाने के लिए किनारों के एक समुच्चय (एक डाइजॉइन) को अनुबंधित करने की समस्या का दोहरा ग्राफ़ है। यह दोहरी समस्या बहुपद रूप से हल करने योग्य है, और इसलिए समतल न्यूनतम फीडबैक चाप समुच्चय समस्या भी है।इसमें समाधान किया जा सकता है time $O(n^{5/2}\log n)$. समस्या का एक भारित संस्करण हल किया जा सकता है time $O(n^{3})$, या जब भार धनात्मक पूर्णांक होते हैं जो अधिकतम a होते हैं number $N$, में time $O(n^{5/2}\log nN)$. इन समतल एल्गोरिदम को उन ग्राफ़ों तक बढ़ाया जा सकता है जिनमें उपयोगिता ग्राफ़ नहीं है $K_{3,3}$ एक ग्राफ लघु के रूप में, इस तथ्य का उपयोग करते हुए कि इन ग्राफ़ के त्रिकोणीय घटक या तो समतल या परिबद्ध आकार के हैं। प्लेनर ग्राफ़ को दिष्ट ग्राफ़ के एक वर्ग के लिए एक अलग तरीके से सामान्यीकृत किया गया है जिसे कमजोर अचक्रीयडिग्राफ कहा जाता है, जिसे एक निश्चित पॉलीहेड्रल कॉम्बिनेटरिक्स के अभिन्न पॉलीटोप द्वारा परिभाषित किया गया है। प्रत्येक तलीय दिष्ट ग्राफ इस अर्थ में कमजोर रूप से चक्रीय है, और फीडबैक चाप समुच्चय समस्या को सभी कमजोर चक्रीय डिग्राफ के लिए बहुपद समय में हल किया जा सकता है।

नियंत्रण-प्रवाह ग्राफ#रिड्यूसिबिलिटी दिष्ट ग्राफ़ का एक अन्य वर्ग है जिस पर फीडबैक चाप समुच्चय समस्या को बहुपद समय में हल किया जा सकता है। ये ग्राफ़ कई प्रोग्रामिंग भाषाओं के लिए संरचित कार्यक्रमों में नियंत्रण के प्रवाह का वर्णन करते हैं। हालाँकि संरचित कार्यक्रम अक्सर समतल दिष्ट प्रवाह ग्राफ़ उत्पन्न करते हैं, रिड्यूसिबिलिटी की परिभाषा के लिए ग्राफ़ का समतल होना आवश्यक नहीं है।

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

कठोरता

एनपी-कठोरता

एनपी-पूर्णता में कमी, बड़े पीले ग्राफ के शीर्ष कवर से लेकर छोटे नीले ग्राफ में न्यूनतम फीडबैक चाप समुच्चय तक, प्रत्येक पीले शीर्ष को दो आसन्न नीले ग्राफ कोने में विस्तारित करती है, और प्रत्येक अप्रत्यक्ष पीला किनारा दो विपरीत दिशा वाले किनारों में। न्यूनतम शीर्ष कवर (ऊपरी बाएँ और निचले दाएँ पीले कोने) लाल न्यूनतम फीडबैक चाप समुच्चय से मेल खाता है।

एनपी-पूर्णता के सिद्धांत को न्यूनतम फीडबैक चाप समुच्चय पर लागू करने के लिए, समस्या को एक अनुकूलन समस्या (सभी चक्रों को तोड़ने के लिए कुछ किनारों को कैसे हटाया जा सकता है) से समतुल्य निर्णय संस्करण में संशोधित करना आवश्यक है, हाँ के साथ या कोई उत्तर नहीं (क्या इसे हटाना संभव है $k$ किनारों)। इस प्रकार, फीडबैक चाप समुच्चय समस्या का निर्णय संस्करण एक दिष्ट ग्राफ और ए दोनों को इनपुट के रूप में लेता है number $k$. यह पूछता है कि क्या सभी चक्रों को अधिक से अधिक हटाकर तोड़ा जा सकता है $k$ किनारों, या समकक्ष रूप से क्या कम से कम एक अचक्रीयउपग्राफ है $|E(G)|-k$ किनारों. यह समस्या एनपी-पूर्ण है, जिसका अर्थ है कि न तो इसमें और न ही अनुकूलन समस्या में बहुपद समय एल्गोरिदम होने की उम्मीद है। यह रिचर्ड एम. कार्प के कार्प की 21 एनपी-पूर्ण समस्याओं के मूल समुच्चय में से एक था|21 एनपी-पूर्ण समस्याएं; इसकी एनपी-पूर्णता कार्प और यूजीन लॉलर द्वारा साबित की गई थी कि एक और कठिन समस्या, वर्टेक्स कवर समस्या के लिए इनपुट को फीडबैक चाप समुच्चय निर्णय समस्या के समकक्ष इनपुट में परिवर्तित (कम) किया जा सकता है।

कुछ एनपी-पूर्ण समस्याएं तब आसान हो सकती हैं जब उनके इनपुट विशेष मामलों तक सीमित हों। लेकिन फीडबैक चाप समुच्चय समस्या के सबसे महत्वपूर्ण विशेष मामले, टूर्नामेंट के मामले में, समस्या एनपी-पूर्ण बनी हुई है।

अप्राप्यता

जटिलता वर्ग APX को अनुकूलन समस्याओं से युक्त के रूप में परिभाषित किया गया है जिसमें एक बहुपद समय सन्निकटन एल्गोरिथ्म होता है जो एक स्थिर सन्निकटन अनुपात प्राप्त करता है। हालाँकि फीडबैक चाप समुच्चय समस्या के लिए ऐसे सन्निकटन ज्ञात नहीं हैं, समस्या को APX-हार्ड के रूप में जाना जाता है, जिसका अर्थ है कि इसके लिए सटीक सन्निकटन का उपयोग APX में अन्य सभी समस्याओं के लिए समान सटीक सन्निकटन प्राप्त करने के लिए किया जा सकता है। इसके कठोरता प्रमाण के परिणामस्वरूप, जब तक कि पी = एनपी न हो, इसका कोई बहुपद समय सन्निकटन अनुपात 1.3606 से बेहतर नहीं है। यह सन्निकटन की कठोरता के लिए वही सीमा है जो वर्टेक्स कवर के लिए जानी जाती है, और प्रमाण वर्टेक्स कवर से फीडबैक चाप समुच्चय तक कार्प-लॉलर कमी (जटिलता) का उपयोग करता है, जो सन्निकटन की गुणवत्ता को संरक्षित करता है। एक अलग कमी से, अधिकतम अचक्रीयउपग्राफ समस्या भी एपीएक्स-हार्ड है, और एनपी-हार्ड को इष्टतम के 65/66 के कारक के भीतर अनुमानित किया जा सकता है।

इन समस्याओं के सन्निकटन की कठोरता का अध्ययन अप्रमाणित कम्प्यूटेशनल कठोरता मान्यताओं के तहत भी किया गया है जो कम्प्यूटेशनल जटिलता सिद्धांत में मानक हैं लेकिन पी ≠ एनपी से अधिक मजबूत हैं। यदि अद्वितीय गेम का अनुमान सत्य है, तो न्यूनतम फीडबैक चाप समुच्चय समस्या को किसी भी स्थिर कारक के भीतर बहुपद समय में अनुमानित करना कठिन है, और अधिकतम फीडबैक चाप समुच्चय समस्या को एक कारक के भीतर अनुमानित करना कठिन है। of ${\tfrac {1}{2}}+\varepsilon$, के लिए every $\varepsilon >0$. सन्निकटन एल्गोरिदम के लिए बहुपद समय से परे, यदि घातीय समय परिकल्पना सत्य है, तो प्रत्येक के लिए $\varepsilon >0$ न्यूनतम फीडबैक चाप समुच्चय में किसी कारक के भीतर कोई सन्निकटन नहीं होता है ${\tfrac {7}{6}}-\varepsilon$ जिसकी गणना उपघातीय समय सीमा में की जा सकती है $O(2^{n^{1-\varepsilon }})$.

सिद्धांत

समतल दिष्ट ग्राफों में, फीडबैक चाप समुच्चय समस्या न्यूनतम-अधिकतम प्रमेय का पालन करती है: फीडबैक चाप समुच्चय का न्यूनतम आमाप किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या के समान होता है जो ग्राफ़ में पाए जा सकते हैं। यह कुछ अन्य ग्राफों के लिए सत्य नहीं है; उदाहरण के लिए पहला चित्र असमतलीय ग्राफ़ $K_{3,3}$ का एक दिष्ट संस्करण दिखाता है जिसमें फीडबैक चाप समुच्चय का न्यूनतम आमाप दो है, जबकि किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या केवल एक है।

प्रत्येक टूर्नामेंट ग्राफ़ में एक हैमिल्टनियन पथ होता है, और हैमिल्टनियन पथ न्यूनतम फीडबैक चाप समुच्चय के साथ एक-के-लिए-एक के अनुरूप होते हैं, जो संबंधित पथ से अलग होते हैं। फीडबैक चाप समुच्चय के लिए हैमिल्टनियन पथ इसके चाप को उलट कर और परिणामी अचक्रीयटूर्नामेंट का टोपोलॉजिकल ऑर्डर ढूंढकर पाया जाता है। क्रम की प्रत्येक लगातार जोड़ी फीडबैक चाप समुच्चय से अलग होनी चाहिए, क्योंकि अन्यथा उस जोड़ी को उलट कर एक छोटा फीडबैक चाप समुच्चय मिल सकता है। इसलिए, यह क्रम सभी शीर्षों को कवर करते हुए, मूल टूर्नामेंट के चापों के माध्यम से एक पथ देता है। इसके विपरीत, किसी भी हैमिल्टनियन पथ से, किनारों का समुच्चय जो पथ में बाद के शीर्षों को पहले वाले शीर्षों से जोड़ता है, एक फीडबैक चाप समुच्चय बनाता है। यह न्यूनतम है, क्योंकि इसका प्रत्येक किनारा हैमिल्टनियन पथ किनारों वाले एक चक्र से संबंधित है जो ऐसे अन्य सभी चक्रों से अलग है। एक टूर्नामेंट में, ऐसा हो सकता है कि न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ दोनों आधे किनारों के करीब हों। अधिक सटीक रूप से, प्रत्येक टूर्नामेंट ग्राफ़ में आकार का फीडबैक चाप समुच्चय होता है ${\tbinom {n}{2}}/2-\Omega (n^{3/2})$, और कुछ टूर्नामेंटों के लिए आकार की आवश्यकता होती है ${\tbinom {n}{2}}/2-O(n^{3/2})$. लगभग सभी टूर्नामेंटों के लिए, आकार कम से कम होता है ${\tbinom {n}{2}}/2-1.73n^{3/2}$. प्रत्येक दिष्ट चक्रीय ग्राफ $D$ इसे एक बड़े टूर्नामेंट ग्राफ के उपग्राफ के रूप में इस तरह से एम्बेड किया जा सकता है $D$ टूर्नामेंट का अद्वितीय न्यूनतम फीडबैक चाप समुच्चय है। इस टूर्नामेंट के आकार को उलटी संख्या के रूप में परिभाषित किया गया है of $D$, और शीर्षों की समान संख्या वाले दिष्ट चक्रीय ग्राफों में यह सबसे बड़ा है जब $D$ यह अपने आप में एक (एसाइक्लिक) टूर्नामेंट है।

एक दिष्ट ग्राफ़ में एक यूलर टावर होता है जब भी यह दृढ़ता से जुड़ा होता है और प्रत्येक शीर्ष पर आने वाले और बाहर जाने वाले किनारों की समान संख्या होती है। ऐसे ग्राफ़ के लिए, साथ $m$ किनारों और $n$ शीर्षों पर, न्यूनतम फीडबैक चाप समुच्चय का आकार हमेशा कम से कम होता है $(m^{2}+mn)/2n^{2}$. ऐसे अनगिनत यूलेरियन दिष्ट ग्राफ़ हैं जिनके लिए यह सीमा तंग है। यदि एक दिष्ट ग्राफ है $n$ शीर्ष, प्रति शीर्ष अधिकतम तीन किनारों के साथ, तो इसमें अधिकतम फीडबैक चाप समुच्चय होता है $n/3$ किनारों, और कुछ ग्राफ़ के लिए इतने की आवश्यकता होती है। यदि एक दिष्ट ग्राफ है $m$ किनारों, प्रति शीर्ष अधिकतम चार किनारों के साथ, तो इसमें अधिकतम फीडबैक चाप समुच्चय होता है $m/3$ किनारों, और कुछ ग्राफ़ के लिए इतने की आवश्यकता होती है।