फीडबैक आर्क सेट: Difference between revisions

Latest revision as of 10:29, 18 July 2023

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

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

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

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

अनुप्रयोग

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

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

राउंड-रॉबिन खेल वाली खेल संबन्धी प्रतिस्पर्धाओं में, प्रत्येक गेम के परिणामों को प्रत्येक गेम के हारने वाले से विजेता की ओर दिष्ट करके दर्ज किया जा सकता है। परिणामी ग्राफ़ में न्यूनतम फीडबैक चाप समुच्चय खोजना, उसके किनारों को उत्क्रमी करना, और सांस्थितिक क्रमण, सभी प्रतिस्पर्धियों पर एक श्रेणीक्रम तैयार करता है। श्रेणीक्रम चुनने के विभिन्न तरीकों के मध्य, यह अप्सेट की कुल संख्या को कम करता है, ऐसे खेल जिनमें कम श्रेणी वाले प्रतियोगी ने उच्च रैंक वाले प्रतियोगी को हराया है।^[2]^[3]^[4] कई स्पोर्टस प्रत्येक गेम के लिए दिए गए अंकों के आधार पर समूह टूर्नामेंट श्रेणीक्रम पद्धतियों के लिए सरल तरीकों का उपयोग करते हैं;^[5] ये तरीके न्यूनतम-अप्सेट श्रेणीक्रम का निरंतर सन्निकटन प्रदान कर सकते हैं।^[6]
प्राइमेटविज्ञान में और आम तौर पर व्यावहारिकी में, प्रभाविता पदानुक्रम अधिकतर देखे गए प्रभाविता व्यवहार में सबसे कम परिवर्तन के साथ एक अनुक्रम की खोज करके निर्धारित किया जाता है, जो न्यूनतम फीडबैक चाप समुच्चय समस्या का दूसरा रूप है।^[7]^[8]^[9]
गणितीय मनोविज्ञान में, किसी दिए गए निकष के अनुसार विषयों की वस्तुओं के समुच्चय की रैंकिंग निर्धारित करना दिलचस्प है, जैसे कि उनकी अधिमान्यता या प्रत्यक्षण की धारणा, वस्तुओं के सभी युग्मों के मध्य युग्‍मानूसार तुलना के आधार पर है। टूर्नामेंट ग्राफ़ में निर्धारित न्यूनतम फीडबैक चाप एक रैंकिंग प्रदान करता है जो यथासंभव कुछ युग्‍मानूसार परिणामों से असहमत होता है।^[2]^[10] वैकल्पिक रूप से, इन तुलनाओं के परिणामस्वरूप प्रत्येक युग्‍मानूसार अनुक्रम के लिए स्वतंत्र प्रायिकताऐं होती हैं|^[2]^[3]
अधिकतम-संभाव्यता क्रमण का उपयोग क्रमबंधन, सांख्यिकी में समस्या और अवयवों को रैखिक अनुक्रम में व्यवस्थि करने के अन्वेषी डेटा विश्लेषण के लिए किया जा सकता है, ऐसी स्थितियों में जहां डेटा उपलब्ध है जो अवयवों के मध्य युग्‍मानूसार तुलना प्रदान करता है।^[3]^[11]^[12]
श्रेणीक्रम मतदान में, केमेनी-यंग पद्धति को एक ऐसे अनुक्रम की खोज के रूप में वर्णित किया जा सकता है जो उस युग्म के लिए विपरीत अनुक्रम को अधिमान करने वाले मतदाताओं की संख्या के योग को उम्मीदवारों के युग्मों से कम कर देता है।^[13] इसे न्यूनतम-भार फीडबैक चाप समुच्चय समस्या के रूप में तैयार और हल किया जा सकता है, जिसमें शीर्ष उम्मीदवारों का निरूपण करते हैं, किनारों को प्रत्येक आमने-सामने की प्रतियोगिता के विजेता को निरूपण करने के लिए निर्देशित किया जाता है, और प्रत्येक किनारे की लागत मतदाताओं की संख्या का निरूपण करती है जो आमने-सामने हारने वाले को उच्च रैंकिंग देकर प्रतिकूल हो जाता है।^[14]

फीडबैक चाप समुच्चय का एक और प्रारंभिक अनुप्रयोग अनुक्रमिक तर्क परिपथों के डिजाइन से संबंधित है, जिसमें संकेत सदैव इनपुट से आउटपुट तक वृद्धि के बजाय परिपथ के माध्यम से चक्र में फैल सकते हैं। ऐसे परिपथों में, न्यूनतम फीडबैक चाप समुच्चय उन बिंदुओं की संख्या को दर्शाता है जिन पर संकेतों को जानकारी की क्षति के बिना प्रसारित करने की अनुमति देने के लिए प्रवर्धन आवश्यक है।^[15] अतुल्यकाली घटकों से बने तुल्यकाली परिपथों में, फीडबैक चाप समुच्चय के किनारों पर कालबद्ध गेट लगाकर तुल्यकालन (सिंक्रोनाइज़ेशन) प्राप्त किया जा सकता है।^[16] इसके अतिरिक्त, एक फीडबैक चाप समुच्चय पर एक परिपथ को काटने से शेष परिपथ संयोजन तर्क में कम हो जाता है, इसका विश्लेषण सरल हो जाता है, और फीडबैक चाप समुच्चय का आमाप नियंत्रित करता है कि कट में परिपथ के व्यवहार को समझने के लिए कितने अतिरिक्त विश्लेषण की आवश्यकता है।^[15] इसी प्रकार, रासायनिक अभियांट्रिकी मेंप्रक्रिया फ़्लोशीटिंग में, फीडबैक चाप समुच्चय पर प्रक्रिया प्रवाह आरेख के किनारों को तोड़ना, और उन किनारों पर मूल्यों के लिए सभी संभावनाओं का अनुमान लगाना या प्रयास करना, बाकी प्रक्रिया को इसकी चक्रीयता के कारण व्यवस्थित तरीके से विश्लेषण करने की अनुमति देता है। इस अनुप्रयोग में, किनारों को इस प्रकार से तोड़ने के विचार को "अवखंडन" कहा जाता है।^[17]

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

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

एल्गोरिदम

समतुल्यताएं

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

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

तीन दृढ़ता से संयोजित घटकों के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष

d

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

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

यथार्थ (बिल्कुल ठीक)

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

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

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

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

सन्निकट

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

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

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

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

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

दिष्ट समतलीय ग्राफ़ में, फीडबैक चाप समुच्चय समस्या परिणामी ग्राफ़ को दृढ़ता से संयोजित करने के लिए किनारों के एक समुच्चय को अनुबंधित करने की समस्या से द्वैती होती है।^[39] यह द्वैती समस्या बहुपद रूप से हल करने योग्य है,^[40] और इसलिए समतल न्यूनतम फीडबैक चाप समुच्चय समस्या भी है।^[41]^[40]इसमें समय $O(n^{5/2}\log n)$ ^[42] में हल किया जा सकता है। समस्या का एक भारित संस्करण समय $O(n^{3})$ ^[39]में हल किया जा सकता है, या जब भार धनात्मक पूर्णांक होते हैं जो समय $O(n^{5/2}\log nN)$ ^[42]में अधिकतम संख्या N होते हैं। समतलीय ग्राफ़ को दिष्ट ग्राफ़ के एक वर्ग के लिए एक अलग तरीके से सामान्यीकृत किया गया है जिसे अल्प अचक्रीय द्विग्राफ कहा जाता है, जो उनके फीडबैक चाप समुच्चयों से संबद्ध एक निश्चित बहुतल के समाकलन द्वारा परिभाषित किया गया है।

प्रत्येक समतलीय दिष्ट ग्राफ इस अर्थ में अल्प रूप से चक्रीय है, और फीडबैक चाप समुच्चय समस्या को सभी अल्प चक्रीय द्विग्राफ के लिए बहुपद काल में हल किया जा सकता है।^[43]

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

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

कठोरता

एनपी-कठोरता

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

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

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

अप्राप्यता

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

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

सिद्धांत

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

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

^[60]^[61]

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

संदर्भ

↑ "Main draw – Men", Rio 2016, Fédération Internationale de Volleyball, archived from the original on 2016-12-23, retrieved 2021-11-14
↑ ^2.0 ^2.1 ^2.2 Hubert, Lawrence (1976), "Seriation using asymmetric proximity measures", British Journal of Mathematical and Statistical Psychology, 29 (1): 32–52, doi:10.1111/j.2044-8317.1976.tb00701.x, MR 0429180
↑ ^3.0 ^3.1 ^3.2 Remage, Russell Jr.; Thompson, W. A. Jr. (1966), "Maximum-likelihood paired comparison rankings", Biometrika, 53 (1–2): 143–149, doi:10.1093/biomet/53.1-2.143, JSTOR 2334060, MR 0196854, PMID 5964054
↑ Goddard, Stephen T. (1983), "Ranking in tournaments and group decisionmaking", Management Science, 29 (12): 1384–1392, doi:10.1287/mnsc.29.12.1384, MR 0809110; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect
↑ Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern; Morin, Thomas L. (January 2018), "Properties of sports ranking methods" (PDF), Journal of the Operational Research Society, 69 (5): 776–787, doi:10.1057/s41274-017-0266-8, S2CID 51887586
↑ Coppersmith, Don; Fleischer, Lisa K.; Rurda, Atri (2010), "Ordering by weighted number of wins gives a good ranking for weighted tournaments", ACM Transactions on Algorithms, 6 (3): A55:1–A55:13, doi:10.1145/1798596.1798608, MR 2682624, S2CID 18416
↑ Seyfarth, Robert M. (November 1976), "Social relationships among adult female baboons", Animal Behaviour, 24 (4): 917–938, doi:10.1016/s0003-3472(76)80022-x, S2CID 54284406
↑ Estep, D.Q.; Crowell-Davis, S.L.; Earl-Costello, S.-A.; Beatey, S.A. (January 1993), "Changes in the social behaviour of drafthorse (Equus caballus) mares coincident with foaling", Applied Animal Behaviour Science, 35 (3): 199–213, doi:10.1016/0168-1591(93)90137-e
↑ Eickwort, George C. (April 2019), "Dominance in a cockroach (Nauphoeta)", Insect Behavior, CRC Press, pp. 120–126, doi:10.1201/9780429049262-18, S2CID 203898549
↑ Slater, Patrick (1961), "Inconsistencies in a schedule of paired comparisons", Biometrika, 48 (3–4): 303–312, doi:10.1093/biomet/48.3-4.303, JSTOR 2332752
↑ Brunk, H. D. (1960), "Mathematical models for ranking from paired comparisons", Journal of the American Statistical Association, 55 (291): 503–520, doi:10.2307/2281911, hdl:2027/mdp.39015095254010, JSTOR 2281911, MR 0115242
↑ Thompson, W. A., Jr.; Remage, Russell, Jr. (1964), "Rankings from paired comparisons", Annals of Mathematical Statistics, 35 (2): 739–747, doi:10.1214/aoms/1177703572, JSTOR 2238526, MR 0161419{{citation}}: CS1 maint: multiple names: authors list (link)
↑ Kemeny, John G. (Fall 1959), "Mathematics without numbers", Daedalus, 88 (4): 577–591, JSTOR 20026529
↑ ^14.0 ^14.1 Karpinski, Marek; Schudy, Warren (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.), Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6506, Springer, pp. 3–14, arXiv:1006.4396, doi:10.1007/978-3-642-17517-6_3, S2CID 16512997
↑ ^15.0 ^15.1 Unger, Stephen H. (April 26, 1957), A study of asynchronous logical feedback networks, Technical reports, vol. 320, Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl:1721.1/4763
↑ Feehrer, John R.; Jordan, Harry F. (December 1995), "Placement of clock gates in time-of-flight optoelectronic circuits", Applied Optics, 34 (35): 8125–8136, Bibcode:1995ApOpt..34.8125F, doi:10.1364/ao.34.008125, PMID 21068927
↑ Rosen, Edward M.; Henley, Ernest J. (Summer 1968), "The New Stoichiometry", Chemical Engineering Education, 2 (3): 120–125, archived from the original on 2021-08-02, retrieved 2021-08-02
↑ Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 9780133016154
↑ Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5
↑ Demetrescu, Camil; Finocchi, Irene (2001), "Break the "right" cycles and get the "best" drawing", ACM Journal of Experimental Algorithmics, 6: 171–182, MR 2027115
↑ ^21.0 ^21.1 ^21.2 Even, G.; Naor, J.; Schieber, B.; Sudan, M. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica, 20 (2): 151–174, doi:10.1007/PL00009191, MR 1484534, S2CID 2437790
↑ ^22.0 ^22.1 Minoura, Toshimi (1982), "Deadlock avoidance revisited", Journal of the ACM, 29 (4): 1023–1048, doi:10.1145/322344.322351, MR 0674256, S2CID 5284738
↑ Mishra, Sounaka; Sikdar, Kripasindhu (2004), "On approximability of linear ordering and related NP-optimization problems on graphs", Discrete Applied Mathematics, 136 (2–3): 249–269, doi:10.1016/S0166-218X(03)00444-X, MR 2045215
↑ ^24.0 ^24.1 Hecht, Michael (2017), "Exact localisations of feedback sets", Theory of Computing Systems, 62 (5): 1048–1084, arXiv:1702.07612, doi:10.1007/s00224-017-9777-6, S2CID 18394348
↑ Park, S.; Akers, S.B. (1992), "An efficient method for finding a minimal feedback arc set in directed graphs", Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS '92), vol. 4, pp. 1863–1866, doi:10.1109/iscas.1992.230449, S2CID 122603659
↑ Nutov, Zeev; Penn, Michal (2000), "On integrality, stability and composition of dicycle packings and covers", Journal of Combinatorial Optimization, 4 (2): 235–251, doi:10.1023/A:1009802905533, MR 1772828, S2CID 207632524
↑ Younger, D. (1963), "Minimum feedback arc sets for a directed graph", IEEE Transactions on Circuit Theory, 10 (2): 238–245, doi:10.1109/tct.1963.1082116
↑ Lawler, E. (1964), "A comment on minimum feedback arc sets", IEEE Transactions on Circuit Theory, 11 (2): 296–297, doi:10.1109/tct.1964.1082291
↑ ^29.0 ^29.1 Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "A note on exact algorithms for vertex ordering problems on graphs", Theory of Computing Systems, 50 (3): 420–432, doi:10.1007/s00224-011-9312-0, hdl:1956/4556, MR 2885638, S2CID 9967521
↑ Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5): 1–19, doi:10.1145/1411509.1411511, S2CID 1547510
↑ Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018), "On directed feedback vertex set parameterized by treewidth", in Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11159, Springer, pp. 65–78, arXiv:1707.01470, doi:10.1007/978-3-030-00256-5_6, S2CID 8008855
↑ Lin, Lishin; Sahni, Sartaj (1989), "Fair edge deletion problems", IEEE Transactions on Computers, 38 (5): 756–761, doi:10.1109/12.24280, MR 0994519
↑ Schwikowski, Benno; Speckenmeyer, Ewald (2002), "On enumerating all minimal solutions of feedback problems", Discrete Applied Mathematics, 117 (1–3): 253–265, doi:10.1016/S0166-218X(00)00339-5, MR 1881280
↑ ^34.0 ^34.1 ^34.2 Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems, archived from the original on 2021-07-29, retrieved 2021-07-29
↑ Eades, Peter; Lin, Xuemin; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters, 47 (6): 319–323, doi:10.1016/0020-0190(93)90079-O, MR 1256786, archived from the original on 2020-10-22, retrieved 2021-08-01
↑ Berger, Bonnie; Shor, Peter W. (1997), "Tight bounds for the maximum acyclic subgraph problem", Journal of Algorithms, 25 (1): 1–18, doi:10.1006/jagm.1997.0864, MR 1474592
↑ Hassin, Refael; Rubinstein, Shlomi (1994), "Approximations for the maximum acyclic subgraph problem", Information Processing Letters, 51 (3): 133–140, doi:10.1016/0020-0190(94)00086-7, MR 1290207
↑ ^38.0 ^38.1 Newman, Alantha (June 2000), Approximating the maximum acyclic subgraph (Master’s thesis), Massachusetts Institute of Technology, hdl:1721.1/86548, as cited by Guruswami et al. (2011)
↑ ^39.0 ^39.1 Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365
↑ ^40.0 ^40.1 Frank, András (1981), "How to make a digraph strongly connected", Combinatorica, 1 (2): 145–153, doi:10.1007/BF02579270, MR 0625547, S2CID 27825518
↑ ^41.0 ^41.1 Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR 0500618
↑ ^42.0 ^42.1 Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842, MR 1328441, S2CID 32162097
↑ Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1985), "On the acyclic subgraph polytope", Mathematical Programming, 33 (1): 28–42, doi:10.1007/BF01582009, MR 0809747, S2CID 206798683
↑ Ramachandran, Vijaya (1988), "Finding a minimum feedback arc set in reducible flow graphs", Journal of Algorithms, 9 (3): 299–313, doi:10.1016/0196-6774(88)90022-3, MR 0955140
↑ Kenyon-Mathieu, Claire; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", in Johnson, David S.; Feige, Uriel (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 95–103, doi:10.1145/1250790.1250806, S2CID 9436948, ECCC TR06-144; see also author's extended version Archived 2009-01-15 at the Wayback Machine
↑ Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002), "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems", Mathematical Programming, 92 (1): 1–36, doi:10.1007/s101070100271, MR 1892295, S2CID 3207086, archived from the original on 2021-08-03, retrieved 2021-08-03
↑ Karp, Richard M. (1972), "Reducibility among combinatorial problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
↑ Garey, Michael R.; Johnson, David S. (1979), "A1.1: GT8", Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, p. 192, ISBN 0-7167-1045-5
↑ Alon, Noga (2006), "Ranking tournaments", SIAM Journal on Discrete Mathematics, 20 (1): 137–142, doi:10.1137/050623905, MR 2257251
↑ Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007), "The minimum feedback arc set problem is NP-hard for tournaments" (PDF), Combinatorics, Probability and Computing, 16 (1): 1–4, doi:10.1017/S0963548306007887, MR 2282830, S2CID 36539840
↑ Ausiello, G.; D'Atri, A.; Protasi, M. (1980), "Structure preserving reductions among convex optimization problems", Journal of Computer and System Sciences, 21 (1): 136–153, doi:10.1016/0022-0000(80)90046-X, MR 0589808
↑ Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF) (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, archived (PDF) from the original on 2010-12-29, retrieved 2007-10-11
↑ Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, archived (PDF) from the original on 2009-09-20, retrieved 2021-07-29; preliminary version in Dinur, Irit; Safra, Samuel (2002), "The importance of being biased", in Reif, John H. (ed.), Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pp. 33–42, doi:10.1145/509907.509915, S2CID 1235048
↑ Bonnet, Édouard; Paschos, Vangelis Th. (2018), "Sparsification and subexponential approximation", Acta Informatica, 55 (1): 1–15, doi:10.1007/s00236-016-0281-2, MR 3757549, S2CID 3136275
↑ Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses (2011), "Beating the random ordering is hard: every ordering CSP is approximation resistant" (PDF), SIAM Journal on Computing, 40 (3): 878–914, doi:10.1137/090756144, MR 2823511, archived (PDF) from the original on 2021-07-31, retrieved 2021-07-31
↑ Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi:10.1016/0095-8956(76)90049-6, MR 0427138
↑ Bar-Noy, Amotz; Naor, Joseph (1990), "Sorting, minimal feedback sets, and Hamilton paths in tournaments", SIAM Journal on Discrete Mathematics, 3 (1): 7–20, doi:10.1137/0403002, MR 1033709
↑ Spencer, J. (1980), "Optimally ranking unrankable tournaments", Periodica Mathematica Hungarica, 11 (2): 131–144, doi:10.1007/BF02017965, MR 0573525, S2CID 119894999
↑ Fernandez de la Vega, W. (1983), "On the maximum cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, Series B, 35 (3): 328–332, doi:10.1016/0095-8956(83)90060-6, MR 0735201
↑ Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth; Roberts, Fred S.; Tesman, Barry (1995), "The reversing number of a digraph", Discrete Applied Mathematics, 60 (1–3): 39–76, doi:10.1016/0166-218X(94)00042-C, MR 1339075
↑ Isaak, Garth; Narayan, Darren A. (2004), "A classification of tournaments having an acyclic tournament as a minimum feedback arc set", Information Processing Letters, 92 (3): 107–111, doi:10.1016/j.ipl.2004.07.001, MR 2095357
↑ Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny; Yuster, Raphael (2013), "Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs", Combinatorics, Probability and Computing, 22 (6): 859–873, arXiv:1202.2602, doi:10.1017/S0963548313000394, hdl:20.500.11850/73894, MR 3111546, S2CID 7967738
↑ Hanauer, Kathrin; Brandenburg, Franz-Josef; Auer, Christopher (2013), "Tight upper bounds for minimum feedback arc sets of regular graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 298–309, doi:10.1007/978-3-642-45043-3_26, MR 3139198

[fivb-1] "Main draw – Men", Rio 2016, Fédération Internationale de Volleyball, archived from the original on 2016-12-23, retrieved 2021-11-14

[hubert-2] 2.0 ^2.1 ^2.2 Hubert, Lawrence (1976), "Seriation using asymmetric proximity measures", British Journal of Mathematical and Statistical Psychology, 29 (1): 32–52, doi:10.1111/j.2044-8317.1976.tb00701.x, MR 0429180

[rt66-3] 3.0 ^3.1 ^3.2 Remage, Russell Jr.; Thompson, W. A. Jr. (1966), "Maximum-likelihood paired comparison rankings", Biometrika, 53 (1–2): 143–149, doi:10.1093/biomet/53.1-2.143, JSTOR 2334060, MR 0196854, PMID 5964054

[goddard-4] Goddard, Stephen T. (1983), "Ranking in tournaments and group decisionmaking", Management Science, 29 (12): 1384–1392, doi:10.1287/mnsc.29.12.1384, MR 0809110; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect

[vdym-5] Vaziri, Baback; Dabadghao, Shaunak; Yih, Yuehwern; Morin, Thomas L. (January 2018), "Properties of sports ranking methods" (PDF), Journal of the Operational Research Society, 69 (5): 776–787, doi:10.1057/s41274-017-0266-8, S2CID 51887586

[cfr-6] Coppersmith, Don; Fleischer, Lisa K.; Rurda, Atri (2010), "Ordering by weighted number of wins gives a good ranking for weighted tournaments", ACM Transactions on Algorithms, 6 (3): A55:1–A55:13, doi:10.1145/1798596.1798608, MR 2682624, S2CID 18416

[seyfarth-7] Seyfarth, Robert M. (November 1976), "Social relationships among adult female baboons", Animal Behaviour, 24 (4): 917–938, doi:10.1016/s0003-3472(76)80022-x, S2CID 54284406

[drafthorse-8] Estep, D.Q.; Crowell-Davis, S.L.; Earl-Costello, S.-A.; Beatey, S.A. (January 1993), "Changes in the social behaviour of drafthorse (Equus caballus) mares coincident with foaling", Applied Animal Behaviour Science, 35 (3): 199–213, doi:10.1016/0168-1591(93)90137-e

[cockroach-9] Eickwort, George C. (April 2019), "Dominance in a cockroach (Nauphoeta)", Insect Behavior, CRC Press, pp. 120–126, doi:10.1201/9780429049262-18, S2CID 203898549

[slater-10] Slater, Patrick (1961), "Inconsistencies in a schedule of paired comparisons", Biometrika, 48 (3–4): 303–312, doi:10.1093/biomet/48.3-4.303, JSTOR 2332752

[brunk-11] Brunk, H. D. (1960), "Mathematical models for ranking from paired comparisons", Journal of the American Statistical Association, 55 (291): 503–520, doi:10.2307/2281911, hdl:2027/mdp.39015095254010, JSTOR 2281911, MR 0115242

[rt64-12] Thompson, W. A., Jr.; Remage, Russell, Jr. (1964), "Rankings from paired comparisons", Annals of Mathematical Statistics, 35 (2): 739–747, doi:10.1214/aoms/1177703572, JSTOR 2238526, MR 0161419{{citation}}: CS1 maint: multiple names: authors list (link)

[kemeny-13] Kemeny, John G. (Fall 1959), "Mathematics without numbers", Daedalus, 88 (4): 577–591, JSTOR 20026529

[KarpinskiSchudy-14] 14.0 ^14.1 Karpinski, Marek; Schudy, Warren (2010), "Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament", in Cheong, Otfried; Chwa, Kyung-Yong; Park, Kunsoo (eds.), Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, Lecture Notes in Computer Science, vol. 6506, Springer, pp. 3–14, arXiv:1006.4396, doi:10.1007/978-3-642-17517-6_3, S2CID 16512997

[unger-15] 15.0 ^15.1 Unger, Stephen H. (April 26, 1957), A study of asynchronous logical feedback networks, Technical reports, vol. 320, Massachusetts Institute of Technology, Research Laboratory of Electronics, hdl:1721.1/4763

[clock-16] Feehrer, John R.; Jordan, Harry F. (December 1995), "Placement of clock gates in time-of-flight optoelectronic circuits", Applied Optics, 34 (35): 8125–8136, Bibcode:1995ApOpt..34.8125F, doi:10.1364/ao.34.008125, PMID 21068927

[rh68-17] Rosen, Edward M.; Henley, Ernest J. (Summer 1968), "The New Stoichiometry", Chemical Engineering Education, 2 (3): 120–125, archived from the original on 2021-08-02, retrieved 2021-08-02

[dett98-18] Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1998), "Layered Drawings of Digraphs", Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, pp. 265–302, ISBN 9780133016154

[bm01-19] Bastert, Oliver; Matuszewski, Christian (2001), "Layered drawings of digraphs", in Kaufmann, Michael; Wagner, Dorothea (eds.), Drawing Graphs: Methods and Models, Lecture Notes in Computer Science, vol. 2025, Springer-Verlag, pp. 87–120, doi:10.1007/3-540-44969-8_5

[df01-20] Demetrescu, Camil; Finocchi, Irene (2001), "Break the "right" cycles and get the "best" drawing", ACM Journal of Experimental Algorithmics, 6: 171–182, MR 2027115

[enss-21] 21.0 ^21.1 ^21.2 Even, G.; Naor, J.; Schieber, B.; Sudan, M. (1998), "Approximating minimum feedback sets and multicuts in directed graphs", Algorithmica, 20 (2): 151–174, doi:10.1007/PL00009191, MR 1484534, S2CID 2437790

[minoura-22] 22.0 ^22.1 Minoura, Toshimi (1982), "Deadlock avoidance revisited", Journal of the ACM, 29 (4): 1023–1048, doi:10.1145/322344.322351, MR 0674256, S2CID 5284738

[missik-23] Mishra, Sounaka; Sikdar, Kripasindhu (2004), "On approximability of linear ordering and related NP-optimization problems on graphs", Discrete Applied Mathematics, 136 (2–3): 249–269, doi:10.1016/S0166-218X(03)00444-X, MR 2045215

[Hecht-24] 24.0 ^24.1 Hecht, Michael (2017), "Exact localisations of feedback sets", Theory of Computing Systems, 62 (5): 1048–1084, arXiv:1702.07612, doi:10.1007/s00224-017-9777-6, S2CID 18394348

[pa92-25] Park, S.; Akers, S.B. (1992), "An efficient method for finding a minimal feedback arc set in directed graphs", Proceedings of the 1992 IEEE International Symposium on Circuits and Systems (ISCAS '92), vol. 4, pp. 1863–1866, doi:10.1109/iscas.1992.230449, S2CID 122603659

[np00-26] Nutov, Zeev; Penn, Michal (2000), "On integrality, stability and composition of dicycle packings and covers", Journal of Combinatorial Optimization, 4 (2): 235–251, doi:10.1023/A:1009802905533, MR 1772828, S2CID 207632524

[younger-27] Younger, D. (1963), "Minimum feedback arc sets for a directed graph", IEEE Transactions on Circuit Theory, 10 (2): 238–245, doi:10.1109/tct.1963.1082116

[lawler-28] Lawler, E. (1964), "A comment on minimum feedback arc sets", IEEE Transactions on Circuit Theory, 11 (2): 296–297, doi:10.1109/tct.1964.1082291

[bfkkt-29] 29.0 ^29.1 Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "A note on exact algorithms for vertex ordering problems on graphs", Theory of Computing Systems, 50 (3): 420–432, doi:10.1007/s00224-011-9312-0, hdl:1956/4556, MR 2885638, S2CID 9967521

[cllor-30] Chen, Jianer; Liu, Yang; Lu, Songjian; O'Sullivan, Barry; Razgon, Igor (2008), "A fixed-parameter algorithm for the directed feedback vertex set problem", Journal of the ACM, 55 (5): 1–19, doi:10.1145/1411509.1411511, S2CID 1547510

[bknpsw-31] Bonamy, Marthe; Kowalik, Lukasz; Nederlof, Jesper; Pilipczuk, Michal; Socala, Arkadiusz; Wrochna, Marcin (2018), "On directed feedback vertex set parameterized by treewidth", in Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus (eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings, Lecture Notes in Computer Science, vol. 11159, Springer, pp. 65–78, arXiv:1707.01470, doi:10.1007/978-3-030-00256-5_6, S2CID 8008855

[ls89-32] Lin, Lishin; Sahni, Sartaj (1989), "Fair edge deletion problems", IEEE Transactions on Computers, 38 (5): 756–761, doi:10.1109/12.24280, MR 0994519

[ss02-33] Schwikowski, Benno; Speckenmeyer, Ewald (2002), "On enumerating all minimal solutions of feedback problems", Discrete Applied Mathematics, 117 (1–3): 253–265, doi:10.1016/S0166-218X(00)00339-5, MR 1881280

[compendium-34] 34.0 ^34.1 ^34.2 Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems, archived from the original on 2021-07-29, retrieved 2021-07-29

[els-35] Eades, Peter; Lin, Xuemin; Smyth, W. F. (1993), "A fast and effective heuristic for the feedback arc set problem", Information Processing Letters, 47 (6): 319–323, doi:10.1016/0020-0190(93)90079-O, MR 1256786, archived from the original on 2020-10-22, retrieved 2021-08-01

[bs97-36] Berger, Bonnie; Shor, Peter W. (1997), "Tight bounds for the maximum acyclic subgraph problem", Journal of Algorithms, 25 (1): 1–18, doi:10.1006/jagm.1997.0864, MR 1474592

[hr94-37] Hassin, Refael; Rubinstein, Shlomi (1994), "Approximations for the maximum acyclic subgraph problem", Information Processing Letters, 51 (3): 133–140, doi:10.1016/0020-0190(94)00086-7, MR 1290207

[newman-38] 38.0 ^38.1 Newman, Alantha (June 2000), Approximating the maximum acyclic subgraph (Master’s thesis), Massachusetts Institute of Technology, hdl:1721.1/86548, as cited by Guruswami et al. (2011)

[gab95-39] 39.0 ^39.1 Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365

[frank-40] 40.0 ^40.1 Frank, András (1981), "How to make a digraph strongly connected", Combinatorica, 1 (2): 145–153, doi:10.1007/BF02579270, MR 0625547, S2CID 27825518

[ly78-41] 41.0 ^41.1 Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR 0500618

[gab93-42] 42.0 ^42.1 Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842, MR 1328441, S2CID 32162097

[gjr85-43] Grötschel, Martin; Jünger, Michael; Reinelt, Gerhard (1985), "On the acyclic subgraph polytope", Mathematical Programming, 33 (1): 28–42, doi:10.1007/BF01582009, MR 0809747, S2CID 206798683

[ramachandran-44] Ramachandran, Vijaya (1988), "Finding a minimum feedback arc set in reducible flow graphs", Journal of Algorithms, 9 (3): 299–313, doi:10.1016/0196-6774(88)90022-3, MR 0955140

[MathieuSchudy-45] Kenyon-Mathieu, Claire; Schudy, Warren (2007), "How to rank with few errors: a PTAS for weighted feedback arc set on tournaments", in Johnson, David S.; Feige, Uriel (eds.), Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 95–103, doi:10.1145/1250790.1250806, S2CID 9436948, ECCC TR06-144; see also author's extended version Archived 2009-01-15 at the Wayback Machine

[afk02-46] Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002), "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems", Mathematical Programming, 92 (1): 1–36, doi:10.1007/s101070100271, MR 1892295, S2CID 3207086, archived from the original on 2021-08-03, retrieved 2021-08-03

[karp-47] Karp, Richard M. (1972), "Reducibility among combinatorial problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103

[gj79-48] Garey, Michael R.; Johnson, David S. (1979), "A1.1: GT8", Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, p. 192, ISBN 0-7167-1045-5

[alon-49] Alon, Noga (2006), "Ranking tournaments", SIAM Journal on Discrete Mathematics, 20 (1): 137–142, doi:10.1137/050623905, MR 2257251

[cty-50] Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007), "The minimum feedback arc set problem is NP-hard for tournaments" (PDF), Combinatorics, Probability and Computing, 16 (1): 1–4, doi:10.1017/S0963548306007887, MR 2282830, S2CID 36539840

[adp80-51] Ausiello, G.; D'Atri, A.; Protasi, M. (1980), "Structure preserving reductions among convex optimization problems", Journal of Computer and System Sciences, 21 (1): 136–153, doi:10.1016/0022-0000(80)90046-X, MR 0589808

[kann-52] Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF) (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, archived (PDF) from the original on 2010-12-29, retrieved 2007-10-11

[ds05-53] Dinur, Irit; Safra, Samuel (2005), "On the hardness of approximating minimum vertex cover" (PDF), Annals of Mathematics, 162 (1): 439–485, doi:10.4007/annals.2005.162.439, archived (PDF) from the original on 2009-09-20, retrieved 2021-07-29; preliminary version in Dinur, Irit; Safra, Samuel (2002), "The importance of being biased", in Reif, John H. (ed.), Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pp. 33–42, doi:10.1145/509907.509915, S2CID 1235048

[bp18-54] Bonnet, Édouard; Paschos, Vangelis Th. (2018), "Sparsification and subexponential approximation", Acta Informatica, 55 (1): 1–15, doi:10.1007/s00236-016-0281-2, MR 3757549, S2CID 3136275

[ghmrc-55] Guruswami, Venkatesan; Håstad, Johan; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses (2011), "Beating the random ordering is hard: every ordering CSP is approximation resistant" (PDF), SIAM Journal on Computing, 40 (3): 878–914, doi:10.1137/090756144, MR 2823511, archived (PDF) from the original on 2021-07-31, retrieved 2021-07-31

[lovasz-56] Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi:10.1016/0095-8956(76)90049-6, MR 0427138

[bn90-57] Bar-Noy, Amotz; Naor, Joseph (1990), "Sorting, minimal feedback sets, and Hamilton paths in tournaments", SIAM Journal on Discrete Mathematics, 3 (1): 7–20, doi:10.1137/0403002, MR 1033709

[spencer-58] Spencer, J. (1980), "Optimally ranking unrankable tournaments", Periodica Mathematica Hungarica, 11 (2): 131–144, doi:10.1007/BF02017965, MR 0573525, S2CID 119894999

[fdlv-59] Fernandez de la Vega, W. (1983), "On the maximum cardinality of a consistent set of arcs in a random tournament", Journal of Combinatorial Theory, Series B, 35 (3): 328–332, doi:10.1016/0095-8956(83)90060-6, MR 0735201

[bhirt-60] Barthélémy, Jean-Pierre; Hudry, Olivier; Isaak, Garth; Roberts, Fred S.; Tesman, Barry (1995), "The reversing number of a digraph", Discrete Applied Mathematics, 60 (1–3): 39–76, doi:10.1016/0166-218X(94)00042-C, MR 1339075

[in04-61] Isaak, Garth; Narayan, Darren A. (2004), "A classification of tournaments having an acyclic tournament as a minimum feedback arc set", Information Processing Letters, 92 (3): 107–111, doi:10.1016/j.ipl.2004.07.001, MR 2095357

[hmssy-62] Huang, Hao; Ma, Jie; Shapira, Asaf; Sudakov, Benny; Yuster, Raphael (2013), "Large feedback arc sets, high minimum degree subgraphs, and long cycles in Eulerian digraphs", Combinatorics, Probability and Computing, 22 (6): 859–873, arXiv:1202.2602, doi:10.1017/S0963548313000394, hdl:20.500.11850/73894, MR 3111546, S2CID 7967738

[hba-63] Hanauer, Kathrin; Brandenburg, Franz-Josef; Auer, Christopher (2013), "Tight upper bounds for minimum feedback arc sets of regular graphs", in Brandstädt, Andreas; Jansen, Klaus; Reischuk, Rüdiger (eds.), Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lübeck, Germany, June 19-21, 2013, Revised Papers, Lecture Notes in Computer Science, vol. 8165, Springer, pp. 298–309, doi:10.1007/978-3-642-45043-3_26, MR 3139198

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]

[61]

[62]

[63]

@@ Line 1: / Line 1: @@
 {{good article}}
 {{Short description|Edges that hit all cycles in a graph}}
-[[File:Feedback arc set.svg|thumb|एक दिष्ट ग्राफ़ का न्यूनतम फीडबैक चाप समुच्चय (लाल डैशित किनारे) और अधिकतम अचक्रीय उपग्राफ (नीला ठोस किनारा) में विभाजन]]ग्राफ़ सिद्धांत और [[ग्राफ एल्गोरिथ्म]] में, एक [[निर्देशित ग्राफ|दिष्ट ग्राफ]] में '''फीडबैक चाप समुच्चय''' या '''फीडबैक किनारा समुच्चय''' ग्राफ़ के किनारों का एक उपसमूह होता है जिसमें ग्राफ़ के प्रत्येक चक्र में से कम से कम एक किनारा होता है। ग्राफ़ से इन किनारों को हटाने से सभी चक्र टूट जाते हैं, जिससे एक [[निर्देशित अचक्रीय ग्राफ|दिष्ट अचक्रीय ग्राफ]] बनता है, जो दिए गए ग्राफ़ का एक '''अचक्रीय उपग्राफ''' होता है। सबसे कम संभावित किनारों के साथ समुच्चय किया गया फीडबैक चाप '''न्यूनतम फीडबैक चाप समुच्चय''' है और इसका अपनेय (रिमूवल)  '''अधिकतम अचक्रीय''' उपग्राफ छोड़ता है; इन [[अनुकूलन समस्या|इष्टमीकरण समस्याओं]] के भारित संस्करणों का भी उपयोग किया जाता है। यदि फीडबैक चाप समुच्चय न्यूनतम है, जिसका अर्थ है कि इसमें से किसी भी किनारे को हटाने से एक उपसमुच्चय उत्पन्न होता है जो फीडबैक चाप समुच्चय नहीं है, तो इसमें एक अतिरिक्त गुण होता है: इसके सभी किनारों को हटाने के बजाय उन्हें उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता  है।
+[[File:Feedback arc set.svg|thumb|एक दिष्ट ग्राफ़ का न्यूनतम फीडबैक चाप समुच्चय (लाल डैशित किनारे) और अधिकतम अचक्रीय उपग्राफ (नीला ठोस किनारा) में विभाजन]]ग्राफ़ सिद्धांत और [[ग्राफ एल्गोरिथ्म]] में, एक [[निर्देशित ग्राफ|दिष्ट ग्राफ]] में '''फीडबैक चाप समुच्चय''' या '''फीडबैक किनारा समुच्चय''' ग्राफ़ के किनारों का एक उपसमूह होता है जिसमें ग्राफ़ के प्रत्येक चक्र में से कम से कम एक किनारा होता है। ग्राफ़ से इन किनारों को हटाने से सभी चक्र टूट जाते हैं, जिससे एक [[निर्देशित अचक्रीय ग्राफ|दिष्ट अचक्रीय ग्राफ]] बनता है, जो दिए गए ग्राफ़ का एक '''अचक्रीय उपग्राफ''' होता है। सबसे कम संभावित किनारों के साथ किया गया समुच्चय फीडबैक चाप '''न्यूनतम फीडबैक चाप समुच्चय''' है और इसका अपनेय (रिमूवल) '''अधिकतम अचक्रीय''' उपग्राफ छोड़ता है; इन [[अनुकूलन समस्या|इष्टमीकरण समस्याओं]] के भारित संस्करणों का भी उपयोग किया जाता है। यदि फीडबैक चाप समुच्चय न्यूनतम है, जिसका अर्थ है कि इसमें से किसी भी किनारे को हटाने से एक उपसमुच्चय उत्पन्न होता है जो फीडबैक चाप समुच्चय नहीं है, तो इसमें एक अतिरिक्त गुण होता है: इसके सभी किनारों को हटाने के बजाय उन्हें उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता है।
-फीडबैक चाप समुच्चय में परिपथ विश्लेषण, [[रासायनिक अभियांट्रिकी]], [[गतिरोध]] वियोजन, [[कोटिकृत वोटिंग]], [[गणितीय मनोविज्ञान]], [[व्यावहारिकी]] और [[ग्राफ ड्राइंग|ग्राफ आरेखण]] में अनुप्रयोग होते हैं। न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ खोज [[ एनपी कठिन |NP-कठिन]] है; इसे बिल्कुल [[घातीय समय|घातांकी समय]] में, या [[निश्चित-पैरामीटर ट्रैक्टेबल|निश्चित-प्राचल ट्रैक्टेबल]] समय में हल किया जा सकता है। [[बहुपद काल]] में, न्यूनतम फीडबैक चाप समुच्चय को एक बहुगणितीय [[सन्निकटन अनुपात]] के भीतर सन्निकटित किया जा सकता है, और अधिकतम अचक्रीय उपग्राफ को एक नियत घटक के भीतर सन्निकटित किया जा सकता है। दोनों को कुछ नियत घटकों की तुलना में समीप लाना कठिन है, एक [[अप्रत्याशितता]] परिणाम जिसे [[अद्वितीय गेम निराधार]] के अंतर्गत मजबूत किया जा सकता है। [[टूर्नामेंट ग्राफ|टूर्नामेंट ग्रा]][[फों]] के लिए, न्यूनतम फीडबैक चाप समुच्चय का सन्निकट अधिक सटीक रूप से लगाया जा सकता है, और [[समतल ग्राफ़|समतल]] [[टूर्नामेंट ग्राफ|ग्रा]][[फों]] के लिए दोनों समस्याओं को बहुपद काल में बिल्कुल हल किया जा सकता है।
+फीडबैक चाप समुच्चय में परिपथ विश्लेषण, [[रासायनिक अभियांट्रिकी]], [[गतिरोध]] वियोजन, [[कोटिकृत वोटिंग]], [[गणितीय मनोविज्ञान]], [[व्यावहारिकी]] और [[ग्राफ ड्राइंग|ग्राफ आरेखण]] में अनुप्रयोग होते हैं। न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ खोज [[ एनपी कठिन |NP-कठिन]] है; इसे बिल्कुल [[घातीय समय|घातांकी समय]] में, या [[निश्चित-पैरामीटर ट्रैक्टेबल|निश्चित-प्राचल ट्रैक्टेबल]] समय में हल किया जा सकता है। [[बहुपद काल]] में, न्यूनतम फीडबैक चाप समुच्चय को एक बहुगणितीय [[सन्निकटन अनुपात]] के भीतर सन्निकटित किया जा सकता है, और अधिकतम अचक्रीय उपग्राफ को एक नियत घटक के भीतर सन्निकटित किया जा सकता है। दोनों को कुछ नियत घटकों की तुलना में समीप लाना कठिन है, एक [[अप्रत्याशितता]] परिणाम जिसे [[अद्वितीय गेम निराधार]] के अंतर्गत मजबूत किया जा सकता है। [[टूर्नामेंट ग्राफ|टूर्नामेंट ग्रा]][[फों]] के लिए, न्यूनतम फीडबैक चाप समुच्चय का सन्निकट अधिक सटीक रूप से लगाया जा सकता है, और [[समतल ग्राफ़|समतल ग्राफों]] के लिए दोनों समस्याओं को बहुपद काल में बिल्कुल हल किया जा सकता है
-एक निकट से संबंधित समस्या, [[फीडबैक वर्टेक्स सेट|फीडबैक शीर्ष समुच्चय]], एक दिष्ट या [[अप्रत्यक्ष ग्राफ|अदिष्‍ट ग्राफ]] में प्रत्येक चक्र से कम से कम एक [[फीडबैक वर्टेक्स सेट|शीर्ष]] युक्त शीर्षों का एक समुच्चय है। [[अप्रत्यक्ष ग्राफ|अदिष्‍ट]] [[ग्राफ़|ग्राफों]] में, [[विस्तरित तरु|विस्तरित वृक्ष]] सबसे बड़े चक्रीय उपग्राफ होते हैं, और एक विस्तरित वृक्ष को बनाने में हटाए गए किनारों की संख्या [[सर्किट रैंक|परिपथ कोटि]] होती है।
+एक संवृत से संबंधित समस्या, [[फीडबैक वर्टेक्स सेट|फीडबैक शीर्ष समुच्चय]], एक दिष्ट या [[अप्रत्यक्ष ग्राफ|अदिष्‍ट ग्राफ]] में प्रत्येक चक्र से कम से कम एक [[फीडबैक वर्टेक्स सेट|शीर्ष]] युक्त शीर्षों का एक समुच्चय है। [[अप्रत्यक्ष ग्राफ|अदिष्‍ट]] [[ग्राफ़|ग्राफों]] में, [[विस्तरित तरु]] सबसे बड़े चक्रीय उपग्राफ होते हैं, और एक विस्तरित तरु को बनाने में हटाए गए किनारों की संख्या [[सर्किट रैंक|परिपथ कोटि]] होती है।
 ==अनुप्रयोग==
-[[File:Min-upset ranking MBV 2016 Pool F.svg|thumb|[[2016 ओलंपिक में]] [[पुरुषों के बीच]] [[वॉलीबॉल]] के स्कोर, पूल एफ, और इन स्कोरों के लिए न्यूनतम-अपसैट (परिवर्तन) रैंकिंग थी। प्रत्येक मैच में हारने वाले से विजेता की ओर तीर लगाए जाते हैं, और जब परिणाम रैंकिंग के अनुरूप होता है तो उन्हें नीला रंग दिया जाता है और परिवर्तन के लिए लाल रंग दिया जाता है, जो परिणाम रैंकिंग के साथ असंगत होता है। इस रैंकिंग के साथ, केवल एक मैच परिवर्तन वाला है, जिसमें यूएसए ने क्यूएटी को हराया था। ओलंपिक में उपयोग की जाने वाली वास्तविक रैंकिंग निर्धारित अनुपात पर ईएसपी को क्यूएटी से आगे रखने से भिन्न थी, जिससे उनके मैच को एक और परिवर्तन के रूप में स्थान दिया गया।{{r|fivb}}]]रैंकिंग या अनुक्रम खोजने से जुड़ी कई समस्याओं को [[टूर्नामेंट ग्राफ़]] पर समुच्चय फीडबैक चाप, प्रत्येक युग्म शीर्षों के मध्य एक किनारे वाला एक दिष्ट ग्राफ़ खोजकर हल किया जा सकता है। फीडबैक चाप समुच्चय के किनारों को उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता है जिसका अद्वितीय [[ टोपोलॉजिकल छँटाई |सांस्थितिक]] [[अनुक्रम]] वांछित रैंकिंग के रूप में उपयोग किया जा सकता है। इस पद्धति के अनुप्रयोगों में निम्नलिखित सम्मिलित हैं:
+[[File:Min-upset ranking MBV 2016 Pool F.svg|thumb|[[2016 ओलंपिक में]] [[पुरुषों के बीच]] [[वॉलीबॉल]] के स्कोर, पूल एफ, और इन स्कोरों के लिए न्यूनतम-अपसैट (परिवर्तन) रैंकिंग थी। प्रत्येक मैच में हारने वाले से विजेता की ओर तीर लगाए जाते हैं, और जब परिणाम रैंकिंग के अनुरूप होता है तो उन्हें नीला रंग दिया जाता है और परिवर्तन के लिए लाल रंग दिया जाता है, जो परिणाम रैंकिंग के साथ असंगत होता है। इस रैंकिंग के साथ, केवल एक मैच परिवर्तन वाला है, जिसमें यूएसए ने क्यूएटी को हराया था। ओलंपिक में उपयोग की जाने वाली वास्तविक रैंकिंग निर्धारित अनुपात पर ईएसपी को क्यूएटी से आगे रखने से भिन्न थी, जिससे उनके मैच को एक और परिवर्तन के रूप में स्थान दिया गया।{{r|fivb}}]]श्रेणीक्रम या अनुक्रम खोजने से जुड़ी कई समस्याओं को [[टूर्नामेंट ग्राफ़]] पर फीडबैक चाप समुच्चय, प्रत्येक युग्म शीर्षों के मध्य एक किनारे वाला एक दिष्ट ग्राफ़ खोजकर हल किया जा सकता है। फीडबैक चाप समुच्चय के किनारों को उत्क्रमी करने से एक दिष्ट अचक्रीय ग्राफ बनता है जिसका अद्वितीय [[ टोपोलॉजिकल छँटाई |सांस्थितिक]] [[अनुक्रम]] वांछित श्रेणीक्रम के रूप में उपयोग किया जा सकता है। इस पद्धति के अनुप्रयोगों में निम्नलिखित सम्मिलित हैं:
-*[[राउंड-रॉबिन खेल]] वाली खेल संबन्धी प्रतिस्पर्धाओं में, प्रत्येक गेम के परिणामों को प्रत्येक गेम के हारने वाले से विजेता की ओर दिष्ट करके दर्ज किया जा सकता है। परिणामी ग्राफ़ में न्यूनतम फीडबैक चाप समुच्चय खोजना, उसके किनारों को उत्क्रमी करना, और सांस्थितिक क्रमण, सभी प्रतिस्पर्धियों पर एक रैंकिंग तैयार करता है। रैंकिंग चुनने के विभिन्न तरीकों के मध्य, यह अप्सेट की कुल संख्या को कम करता है, ऐसे खेल जिनमें कम रैंक वाले प्रतियोगी ने उच्च रैंक वाले प्रतियोगी को हराया है।{{r|hubert|rt66|goddard}} कई स्पोर्टस प्रत्येक गेम के लिए दिए गए अंकों के आधार पर [[समूह टूर्नामेंट रैंकिंग प्रणाली|समूह टूर्नामेंट रैंकिंग पद्धतियों]] के लिए सरल तरीकों का उपयोग करते हैं;{{r|vdym}} ये तरीके न्यूनतम-अप्सेट रैंकिंग का निरंतर सन्निकटन प्रदान कर सकते हैं।{{r|cfr}}
+*[[राउंड-रॉबिन खेल]] वाली खेल संबन्धी प्रतिस्पर्धाओं में, प्रत्येक गेम के परिणामों को प्रत्येक गेम के हारने वाले से विजेता की ओर दिष्ट करके दर्ज किया जा सकता है। परिणामी ग्राफ़ में न्यूनतम फीडबैक चाप समुच्चय खोजना, उसके किनारों को उत्क्रमी करना, और सांस्थितिक क्रमण, सभी प्रतिस्पर्धियों पर एक श्रेणीक्रम तैयार करता है। श्रेणीक्रम चुनने के विभिन्न तरीकों के मध्य, यह अप्सेट की कुल संख्या को कम करता है, ऐसे खेल जिनमें कम श्रेणी वाले प्रतियोगी ने उच्च रैंक वाले प्रतियोगी को हराया है।{{r|hubert|rt66|goddard}} कई स्पोर्टस प्रत्येक गेम के लिए दिए गए अंकों के आधार पर [[समूह टूर्नामेंट रैंकिंग प्रणाली|समूह टूर्नामेंट श्रेणीक्रम पद्धतियों]] के लिए सरल तरीकों का उपयोग करते हैं;{{r|vdym}} ये तरीके न्यूनतम-अप्सेट श्रेणीक्रम का निरंतर सन्निकटन प्रदान कर सकते हैं।{{r|cfr}}
 *[[प्राइमेटोलॉजी|प्राइमेटविज्ञान]] में और आम तौर पर व्यावहारिकी में, [[प्रभुत्व पदानुक्रम|प्रभाविता पदानुक्रम]] अधिकतर देखे गए प्रभाविता व्यवहार में सबसे कम परिवर्तन के साथ एक अनुक्रम की खोज करके निर्धारित किया जाता है, जो न्यूनतम फीडबैक चाप समुच्चय समस्या का दूसरा रूप है।{{r|seyfarth|drafthorse|cockroach}}
-*[[गणितीय मनोविज्ञान]] में, किसी दिए गए निकष के अनुसार विषयों की वस्तुओं के समुच्चय की रैंकिंग निर्धारित करना दिलचस्प है, जैसे कि उनकी अधिमान्यता या प्रत्यक्षण की उनकी धारणा, वस्तुओं के सभी युग्मों के मध्य युग्‍मानूसार तुलना के आधार पर है। टूर्नामेंट ग्राफ़ में निर्धारित न्यूनतम फीडबैक चाप एक रैंकिंग प्रदान करता है जो यथासंभव कुछ युग्‍मानूसार परिणामों से असहमत होता है।{{r|hubert|slater}} वैकल्पिक रूप से, इन तुलनाओं के परिणामस्वरूप प्रत्येक युग्‍मानूसार अनुक्रम के लिए स्वतंत्र प्रायिकताऐं होती हैं|{{r|hubert|rt66}}
+*[[गणितीय मनोविज्ञान]] में, किसी दिए गए निकष के अनुसार विषयों की वस्तुओं के समुच्चय की रैंकिंग निर्धारित करना दिलचस्प है, जैसे कि उनकी अधिमान्यता या प्रत्यक्षण की धारणा, वस्तुओं के सभी युग्मों के मध्य युग्‍मानूसार तुलना के आधार पर है। टूर्नामेंट ग्राफ़ में निर्धारित न्यूनतम फीडबैक चाप एक रैंकिंग प्रदान करता है जो यथासंभव कुछ युग्‍मानूसार परिणामों से असहमत होता है।{{r|hubert|slater}} वैकल्पिक रूप से, इन तुलनाओं के परिणामस्वरूप प्रत्येक युग्‍मानूसार अनुक्रम के लिए स्वतंत्र प्रायिकताऐं होती हैं|{{r|hubert|rt66}}
 * अधिकतम-संभाव्यता क्रमण का उपयोग क्रमबंधन, [[सांख्यिकी]] में समस्या और अवयवों को रैखिक अनुक्रम में व्यवस्थि करने के [[अन्वेषी डेटा]] विश्लेषण के लिए किया जा सकता है, ऐसी स्थितियों में जहां डेटा उपलब्ध है जो अवयवों के मध्य युग्‍मानूसार तुलना प्रदान करता है।{{r|rt66|brunk|rt64}}
-*'''रैंकिंग वोटिंग में, केमेनी-यंग पद्धति को एक ऐसे क्रम की खोज के रूप में वर्णित किया जा सकता''' है जो उस युग्म के लिए विपरीत अनुक्रम को अधिमान करने वाले मतदाताओं की संख्या के उम्मीदवारों के युग्मों के योग को कम करता है।{{r|kemeny}} इसे न्यूनतम-वजन फीडबैक चाप समुच्चय समस्या के रूप में तैयार और हल किया जा सकता है, जिसमें कोने उम्मीदवारों का प्रतिनिधित्व करते हैं, किनारों को प्रत्येक आमने-सामने की प्रतियोगिता के विजेता का प्रतिनिधित्व करने के लिए दिष्ट किया जाता है, और प्रत्येक किनारे की लागत संख्या का प्रतिनिधित्व करती है आमने-सामने हारने वाले को ऊंची रैंकिंग देने से मतदाता नाखुश हो जाएंगे।{{r|KarpinskiSchudy}}
+*[[कोटिकृत मतदान|श्रेणीक्रम मतदान]] में, [[केमेनी-यंग पद्धति]] को एक ऐसे अनुक्रम की खोज के रूप में वर्णित किया जा सकता है जो उस युग्म के लिए विपरीत अनुक्रम को अधिमान करने वाले मतदाताओं की संख्या के योग को उम्मीदवारों के युग्मों से कम कर देता है।{{r|kemeny}} इसे न्यूनतम-भार फीडबैक चाप समुच्चय समस्या के रूप में तैयार और हल किया जा सकता है, जिसमें शीर्ष उम्मीदवारों का निरूपण करते हैं, किनारों को प्रत्येक आमने-सामने की प्रतियोगिता के विजेता को निरूपण करने के लिए निर्देशित किया जाता है, और प्रत्येक किनारे की लागत मतदाताओं की संख्या का निरूपण करती है  जो आमने-सामने हारने वाले को उच्च रैंकिंग देकर प्रतिकूल हो जाता है।{{r|KarpinskiSchudy}}
-फीडबैक चाप समुच्चय का एक और प्रारंभिक अनुप्रयोग अनुक्रमिक लॉजिक सर्किट के डिजाइन से संबंधित है, जिसमें सिग्नल हमेशा इनपुट से आउटपुट तक बढ़ने के बजाय सर्किट के माध्यम से चक्र में फैल सकते हैं। ऐसे सर्किट में, न्यूनतम फीडबैक चाप समुच्चय उन बिंदुओं की संख्या को दर्शाता है जिन पर सूचना के नुकसान के बिना संकेतों को प्रसारित करने की अनुमति देने के लिए प्रवर्धन आवश्यक है।{{r|unger}} एसिंक्रोनस घटकों से बने [[ तुल्यकालिक सर्किट ]] में, फीडबैक चाप समुच्चय के किनारों पर क्लॉक्ड गेट लगाकर सिंक्रोनाइज़ेशन प्राप्त किया जा सकता है।{{r|clock}} इसके अतिरिक्त, एक फीडबैक चाप समुच्चय पर एक सर्किट को काटने से शेष सर्किट [[संयोजन तर्क]] में कम हो जाता है, जिससे इसका विश्लेषण सरल हो जाता है, और फीडबैक चाप समुच्चय का आकार नियंत्रित करता है कि कट में सर्किट के व्यवहार को समझने के लिए कितने अतिरिक्त विश्लेषण की आवश्यकता है।{{r|unger}} इसी तरह, केमिकल इंजीनियरिंग में [[ प्रक्रिया फ़्लोशीटिंग ]] में, फीडबैक चाप समुच्चय पर प्रोसेस फ्लो आरेख के किनारों को तोड़ना, और उन किनारों पर मूल्यों के लिए सभी संभावनाओं का अनुमान लगाना या प्रयास करना, बाकी प्रक्रिया को व्यवस्थित तरीके से विश्लेषण करने की अनुमति देता है क्योंकि इसकी चक्रीयता का. इस एप्लिकेशन में, किनारों को इस तरह से तोड़ने के विचार को फाड़ना कहा जाता है।{{r|rh68}}
+फीडबैक चाप समुच्चय का एक और प्रारंभिक अनुप्रयोग [[अनुक्रमिक तर्क]] परिपथों के डिजाइन से संबंधित है, जिसमें संकेत सदैव इनपुट से आउटपुट तक वृद्धि के बजाय परिपथ के माध्यम से चक्र में फैल सकते हैं। ऐसे परिपथों में, न्यूनतम फीडबैक चाप समुच्चय उन बिंदुओं की संख्या को दर्शाता है जिन पर संकेतों को जानकारी की क्षति के बिना प्रसारित करने की अनुमति देने के लिए प्रवर्धन आवश्यक है।{{r|unger}} अतुल्यकाली घटकों से बने [[ तुल्यकालिक सर्किट |तुल्यकाली परिपथों]] में, फीडबैक चाप समुच्चय के किनारों पर कालबद्ध गेट लगाकर तुल्यकालन (सिंक्रोनाइज़ेशन) प्राप्त किया जा सकता है।{{r|clock}} इसके अतिरिक्त, एक फीडबैक चाप समुच्चय पर एक परिपथ को काटने से शेष परिपथ [[संयोजन तर्क]] में कम हो जाता है, इसका विश्लेषण सरल हो जाता है, और फीडबैक चाप समुच्चय का आमाप नियंत्रित करता है कि कट में परिपथ के व्यवहार को समझने के लिए कितने अतिरिक्त विश्लेषण की आवश्यकता है।{{r|unger}} इसी प्रकार, [[रासायनिक अभियांट्रिकी]] में[[ प्रक्रिया फ़्लोशीटिंग ]]में, फीडबैक चाप समुच्चय पर [[प्रक्रिया प्रवाह आरेख]] के किनारों को तोड़ना, और उन किनारों पर मूल्यों के लिए सभी संभावनाओं का अनुमान लगाना या प्रयास करना, बाकी प्रक्रिया को इसकी चक्रीयता के कारण व्यवस्थित तरीके से विश्लेषण करने की अनुमति देता है। इस अनुप्रयोग में, किनारों को इस प्रकार से तोड़ने के विचार को "अवखंडन" कहा जाता है।{{r|rh68}}
-[[स्तरित ग्राफ ड्राइंग]] में, किसी दिए गए दिष्ट ग्राफ के शीर्षों को उपसमुच्चय (ड्राइंग की परतें) के एक क्रमबद्ध अनुक्रम में विभाजित किया जाता है, और प्रत्येक उपसमुच्चय को इस ड्राइंग की क्षैतिज रेखा के साथ रखा जाता है, जिसके किनारे ऊपर और नीचे की ओर बढ़ते हैं। परतें. इस प्रकार की ड्राइंग में, यह वांछनीय है कि अधिकांश या सभी किनारों को ऊपर और नीचे के किनारों को मिलाने के बजाय लगातार नीचे की ओर उन्मुख किया जाए, ताकि ड्राइंग में रीचैबिलिटी संबंध अधिक स्पष्ट रूप से स्पष्ट हो सकें। यह एक न्यूनतम या न्यूनतम फीडबैक चाप समुच्चय ढूंढकर, उस समुच्चय में किनारों को उलट कर, और फिर परतों में विभाजन को इस तरह से चुनकर प्राप्त किया जाता है जो परिणामी अचक्रीयग्राफ के सांस्थितिकक्रम के अनुरूप हो।{{r|dett98|bm01}} फीडबैक चाप समुच्चय का उपयोग स्तरित ग्राफ ड्राइंग की एक अलग उपसमस्या के लिए भी किया गया है, परतों के लगातार जोड़े के भीतर शीर्षों का क्रम।{{r|df01}}
+[[स्तरित ग्राफ ड्राइंग|स्तरित ग्राफ आरेखन]] में, किसी दिए गए दिष्ट ग्राफ के शीर्षों को उपसमुच्चय (आरेखन की परतें) के एक क्रमबद्ध अनुक्रम में विभाजित किया जाता है, और प्रत्येक उपसमुच्चय को इस आरेखन की क्षैतिज रेखा के साथ रखा जाता है, जिसके किनारे इन परतों के मध्य ऊपर और नीचे की ओर विस्तृत हैं। इस प्रकार के आरेखन में, यह वांछनीय है कि अधिकांश या सभी किनारों को या ऊपर और नीचे के किनारों को मिलाने के बजाय उन्हे लगातार नीचे की ओर अभिविन्यस्त किया जाए, ताकि आरेखन में गम्यता संबंध अधिक स्पष्ट रूप से स्पष्ट हो सकें। यह एक न्यूनतम या न्यूनतम फीडबैक चाप समुच्चय खोजकर, उस समुच्चय में किनारों को उत्क्रमण कर, और फिर परतों में विभाजन को इस प्रकार से चुनकर प्राप्त किया जाता है जो परिणामी अचक्रीय ग्राफ के सांस्थितिक अनुक्रम के अनुरूप है।{{r|dett98|bm01}} फीडबैक चाप समुच्चय का उपयोग स्तरित ग्राफ आरेखन की एक अलग उपसमस्या के लिए भी किया गया है, परतों के क्रमागत युग्मों के भीतर शीर्षों का एक अनुक्रम है।{{r|df01}}
-[[ऑपरेटिंग सिस्टम]] में गतिरोध समाधान में, गतिरोध को तोड़ने के लिए निर्भरता की सबसे छोटी संख्या को हटाने की समस्या को न्यूनतम फीडबैक चाप समुच्चय खोजने में से एक के रूप में तैयार किया जा सकता है।{{r|enss|minoura}} हालाँकि, इस समुच्चय को खोजने की कम्प्यूटेशनल कठिनाई और ऑपरेटिंग सिस्टम घटकों के भीतर गति की आवश्यकता के कारण, इस एप्लिकेशन में अक्सर सटीक एल्गोरिदम के बजाय अनुमान का उपयोग किया जाता है।{{r|minoura}}
+[[ऑपरेटिंग सिस्टम|प्रचालन तंत्र]] में [[गतिरोध]] समाधान में, गतिरोध को तोड़ने के लिए आश्रितता की सबसे छोटी संख्या को हटाने की समस्या को न्यूनतम फीडबैक चाप समुच्चय खोजने में से एक के रूप में तैयार किया जा सकता है।{{r|enss|minoura}} हालाँकि, इस समुच्चय को खोजने की अभिकलनात्मक कठिनाई और [[ऑपरेटिंग सिस्टम|प्रचालन तंत्र]] घटकों के भीतर गति की आवश्यकता के कारण, इस अनुप्रयोग में अधिकतर सटीक एल्गोरिदम के बजाय स्वतः शोध प्रणाली का उपयोग किया जाता है।{{r|minoura}}
 ==एल्गोरिदम==
 ===समतुल्यताएं===
-सटीक अनुकूलन के प्रयोजनों के लिए न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ समतुल्य हैं, क्योंकि एक दूसरे का [[पूरक सेट|पूरक समुच्चय]] है। हालाँकि, पैरामीटरयुक्त जटिलता और सन्निकटन के लिए, वे भिन्न होते हैं, क्योंकि उन प्रकार के एल्गोरिदम के लिए उपयोग किया जाने वाला विश्लेषण समाधान के आकार पर निर्भर करता है, न कि केवल इनपुट ग्राफ़ के आकार पर, और न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीयउपग्राफ अलग-अलग होते हैं एक दूसरे से आकार.{{r|missik}}
+यथार्थ इष्टतमीकरण के उद्देश्यों के लिए न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ समतुल्य हैं, क्योंकि एक दूसरे के [[पूरक सेट|पूरक समुच्चय]] है। हालाँकि, पैरामिट्रीकृत जटिलता और सन्निकटन के लिए, वे भिन्न होते हैं, क्योंकि उन प्रकार के एल्गोरिदमों के लिए उपयोग किया जाने वाला विश्लेषण समाधान आमाप पर आश्रित है, न कि केवल इनपुट ग्राफ़ के आमाप पर, और न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ के आमाप एक दूसरे से भिन्न होते हैं।{{r|missik}}
-किसी दिए गए ग्राफ़ का फीडबैक चाप समुच्चय <math>G</math> दिष्ट रेखा ग्राफ़ के फीडबैक शीर्ष समुच्चय के समान है {{nowrap|of <math>G</math>.}} यहां, एक फीडबैक वर्टेक्स समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है, ग्राफ के शीर्षों के एक उपसमुच्चय के रूप में जिसका विलोपन सभी चक्रों को खत्म कर देगा। दिष्ट ग्राफ़ का रेखा ग्राफ़ <math>G</math> प्रत्येक किनारे के लिए एक शीर्ष है {{nowrap|of <math>G</math>,}} और प्रत्येक दो-किनारे पथ के लिए एक किनारा {{nowrap|in <math>G</math>.}} दूसरी दिशा में, किसी दिए गए ग्राफ़ का न्यूनतम फीडबैक शीर्ष समुच्चय <math>G</math> के प्रत्येक शीर्ष को विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या का समाधान प्राप्त किया जा सकता है <math>G</math> दो शीर्षों में, एक आने वाले किनारों के लिए और एक बाहर जाने वाले किनारों के लिए। ये परिवर्तन फीडबैक चाप समुच्चय और फीडबैक वर्टेक्स समुच्चय के लिए सटीक एल्गोरिदम को उनकी जटिलता सीमाओं के उचित अनुवाद के साथ एक-दूसरे में परिवर्तित करने की अनुमति देते हैं। हालाँकि, यह परिवर्तन अधिकतम अचक्रीयउपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।{{r|enss|Hecht}}
+किसी दिए गए ग्राफ़ <math>G</math> का फीडबैक चाप समुच्चय, {{nowrap| <math>G</math>}} के दिष्ट [[रेखा ग्राफ़]] के [[फीडबैक शीर्ष समुच्चय]] के समान है| यहां, एक फीडबैक शीर्ष समुच्चय को फीडबैक चाप समुच्चय के अनुरूप परिभाषित किया गया है। दिष्ट ग्राफ़ <math>G</math> के रेखा ग्राफ़ में {{nowrap| <math>G</math>}} के प्रत्येक किनारे के लिए एक शीर्ष होता है, और {{nowrap|<math>G</math>}} में प्रत्येक दो-किनारे वाले पथ के लिए एक किनारा होता है। दूसरी दिशा में, किसी दिए गए ग्राफ़ <math>G</math> का न्यूनतम फीडबैक शीर्ष समुच्चय <math>G</math> के प्रत्येक शीर्ष को दो शीर्षों में विभाजित करके प्राप्त ग्राफ़ पर न्यूनतम फीडबैक चाप समुच्चय समस्या के समाधान से प्राप्त किया जा सकता है| ये रूपांतरण फीडबैक चाप समुच्चय और फीडबैक शीर्ष समुच्चय के लिए सटीक एल्गोरिदमों को उनकी सम्मिश्रता परिबंधों के उचित स्थानांतरण के साथ एक-दूसरे में रूपांतरित करने की अनुमति देते हैं। हालाँकि, यह रूपांतरण अधिकतम अचक्रीय उपग्राफ समस्या के लिए सन्निकटन गुणवत्ता को संरक्षित नहीं करता है।{{r|enss|Hecht}}
-[[File:Scc-1.svg|thumb|upright=1.35|तीन [[दृढ़ता से जुड़े घटकों|दृढ़ता से संयोजित घटकों]] के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष <math>d</math> पर [[द्वियोजी]] [[घटकों]] में विभाजित किया जा सकता है, प्रत्येक दो शीर्षों का एक चक्र है। फीडबैक चाप समुच्चय समस्या को प्रत्येक मजबूती से जुड़े घटक में और मजबूती से जुड़े घटक के प्रत्येक द्वि-कनेक्टेड घटक में अलग से हल किया जा सकता है।]]फीडबैक चाप समुच्चय समस्या के सटीक और अनुमानित दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक मजबूती से जुड़े घटक को अलग से हल करना और इन दृढ़ता से जुड़े घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके द्वि-जुड़े घटकों को और भी दूर तक तोड़ना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटक में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में शामिल करने के लिए बेकार हैं।{{r|pa92}} जब इन घटकों में से एक को दो शीर्षों को हटाकर दो डिस्कनेक्ट किए गए उपग्राफ में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है, जिससे समस्या को इसके दृढ़ता से जुड़े घटकों के एसपीक्यूआर पेड़ से प्राप्त उप-समस्याओं में विभाजित किया जा सकता है।{{r|np00}}
+[[File:Scc-1.svg|thumb|upright=1.35|तीन [[दृढ़ता से जुड़े घटकों|दृढ़ता से संयोजित घटकों]] के साथ एक दिष्ट ग्राफ, जिनमें से सबसे दाहिनी ओर को आर्टिक्यूलेशन शीर्ष <math>d</math> पर [[द्वियोजी]] [[घटकों]] में विभाजित किया जा सकता है, प्रत्येक दो शीर्षों का एक चक्र है। फीडबैक चाप समुच्चय समस्या को प्रत्येक दृढ़ता से संयोजित घटक में और दृढ़ता से संयोजित घटक के प्रत्येक द्वियोजी घटक में अलग से हल किया जा सकता है।]]फीडबैक चाप समुच्चय समस्या के सटीक और सन्निकटन दोनों समाधानों में, दिए गए ग्राफ़ के प्रत्येक [[दृढ़ता से संयोजित घटक]] को अलग से हल करना और इन दृढ़ता से संयोजित घटकों को आर्टिक्यूलेशन शीर्षों पर विभाजित करके उनके [[द्वियोजी घटकों]] को और भी दूर तक विभक्तन करना पर्याप्त है। इन उपसमस्याओं में से किसी एक के भीतर समाधान का चुनाव दूसरों को प्रभावित नहीं करता है, और जो किनारे इनमें से किसी भी घटकों में दिखाई नहीं देते हैं वे फीडबैक चाप समुच्चय में सम्मिलित करने के लिए निष्क्रिय हैं।{{r|pa92}} जब इन घटकों में से एक को दो शीर्षों को हटाकर दो असंयोजित किए गए उपग्राफों में अलग किया जा सकता है, तो एक अधिक जटिल अपघटन लागू होता है|{{r|np00}}
-===सटीक===
-न्यूनतम फीडबैक चाप समुच्चय को खोजने का एक तरीका शीर्षों के क्रम की खोज करना है, ताकि क्रम में यथासंभव कुछ किनारों को बाद के शीर्षों से पहले के शीर्षों की ओर दिष्ट किया जा सके।{{r|younger}} एक के सभी क्रम[[परिवर्तन]] खोज रहे हैं {{nowrap|<math>n</math>-vertex}} ग्राफ लगेगा {{nowrap|time <math>O(n!)</math>,}} लेकिन हेल्ड-कार्प एल्गोरिदम पर आधारित एक [[गतिशील प्रोग्रामिंग]] विधि इष्टतम क्रमपरिवर्तन पा सकती है {{nowrap|time <math>O(n2^n)</math>,}} स्थान की घातीय मात्रा का भी उपयोग कर रहा है।{{r|lawler|bfkkt}} एक [[फूट डालो और जीतो एल्गोरिथ्म]] जो शीर्षों के सभी विभाजनों को दो समान उपसमुच्चयों में परीक्षण करता है और प्रत्येक उपसमुच्चय के भीतर पुनरावृत्ति करता है, समस्या को हल कर सकता है {{nowrap|time <math>O(4^n/\sqrt{n})</math>,}} [[बहुपद स्थान]] का उपयोग करना।{{r|bfkkt}}
-[[पैरामीटरयुक्त जटिलता]] में, एल्गोरिदम के लिए समय को न केवल इनपुट ग्राफ़ के आकार के संदर्भ में मापा जाता है, बल्कि ग्राफ़ के एक अलग पैरामीटर के संदर्भ में भी मापा जाता है। विशेष रूप से, न्यूनतम फीडबैक चाप समुच्चय समस्या के लिए, तथाकथित प्राकृतिक पैरामीटर न्यूनतम फीडबैक चाप समुच्चय का आकार है। के साथ ग्राफ़ पर <math>n</math> शिखर, प्राकृतिक के साथ {{nowrap|parameter <math>k</math>,}} फीडबैक चाप समुच्चय समस्या को हल किया जा सकता है {{nowrap|time <math>O(n^44^kk^3k!)</math>,}} इसे समतुल्य फीडबैक वर्टेक्स समुच्चय समस्या में परिवर्तित करके और एक पैरामीटरयुक्त फीडबैक वर्टेक्स समुच्चय एल्गोरिदम लागू करके। क्योंकि के प्रतिपादक <math>n</math> इस एल्गोरिथ्म में है {{nowrap|constant <math>4</math>,}} स्वतंत्र {{nowrap|of <math>k</math>,}} इस एल्गोरिदम को फिक्स्ड-पैरामीटर ट्रैक्टेबल कहा जाता है।{{r|cllor}}
-प्राकृतिक मापदण्ड के अतिरिक्त अन्य मापदण्डों का भी अध्ययन किया गया है। डायनेमिक प्रोग्रामिंग का उपयोग करके एक निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम न्यूनतम फीडबैक चाप समुच्चय पा सकता है {{nowrap|time <math>O(2^r m^4\log m)</math>,}} कहाँ <math>r</math> अंतर्निहित अप्रत्यक्ष ग्राफ़ का सर्किट रैंक है। सर्किट रैंक फीडबैक चाप समुच्चय का एक अप्रत्यक्ष एनालॉग है, किनारों की न्यूनतम संख्या जिसे ग्राफ़ से एक फैले हुए पेड़ तक कम करने के लिए हटाने की आवश्यकता होती है; न्यूनतम फीडबैक चाप समुच्चय की तुलना में इसकी गणना करना बहुत आसान है।{{r|Hecht}} के ग्राफ़ के लिए {{nowrap|[[treewidth]] <math>t</math>,}} ग्राफ़ के पेड़ के अपघटन पर गतिशील प्रोग्रामिंग ग्राफ़ आकार और घातांक में समय बहुपद में निर्धारित न्यूनतम फीडबैक चाप पा सकती है {{nowrap|in <math>O(t\log t)</math>.}}[[घातांकीय समय परिकल्पना]] के अंतर्गत, इससे बेहतर कोई निर्भरता नहीं <math>t</math> संभव है।{{r|bknpsw}}
-फीडबैक चाप समुच्चय के आकार को कम करने के बजाय, शोधकर्ताओं ने किसी भी शीर्ष से हटाए गए किनारों की अधिकतम संख्या को कम करने पर भी ध्यान दिया है। समस्या की इस भिन्नता को [[रैखिक समय]] में हल किया जा सकता है।{{r|ls89}} सभी न्यूनतम फीडबैक चाप समुच्चय को प्रति समुच्चय [[बहुपद विलंब]] के साथ एक एल्गोरिदम द्वारा सूचीबद्ध किया जा सकता है।{{r|ss02}}
-===अनुमानित===
-{{unsolved|mathematics|Does the feedback arc set problem have an [[approximation algorithm]] with a constant approximation ratio?}}
-फीडबैक चाप समुच्चय के लिए सबसे प्रसिद्ध बहुपद-समय सन्निकटन एल्गोरिथ्म में गैर-स्थिर सन्निकटन अनुपात है {{nowrap|<math>O(\log n\log\log n)</math>.}} इसका मतलब यह है कि फीडबैक चाप समुच्चय का आकार जो इसे मिलता है वह अधिकतम इस कारक से इष्टतम से बड़ा है।{{r|enss}} यह निर्धारित करना कि क्या फीडबैक चाप समुच्चय में एक स्थिर-अनुपात सन्निकटन एल्गोरिथ्म है, या क्या एक गैर-स्थिर अनुपात आवश्यक है, एक खुली समस्या बनी हुई है।{{r|compendium}}
-अधिकतम अचक्रीयउपग्राफ समस्या में एक आसान सन्निकटन एल्गोरिथ्म है जो एक सन्निकटन अनुपात प्राप्त करता है {{nowrap|of <math>\tfrac12</math>:}}
-*शीर्षों का मनमाना क्रम ठीक करें
-*किनारों को दो अचक्रीय उपसमूहों में विभाजित करें, एक में किनारे क्रम के अनुरूप दिष्ट होते हैं, और दूसरे में क्रम के विपरीत दिशा में दिष्ट किनारे होते हैं।
-*दो उपग्राफों में से बड़े को लौटाएँ।
-ऑर्डर चुनने के लिए एक [[लालची एल्गोरिदम]] का उपयोग करके इसे बेहतर बनाया जा सकता है। यह एल्गोरिदम एक शीर्ष को ढूंढता है और हटा देता है जिसके आने वाले और बाहर जाने वाले किनारों की संख्या यथासंभव दूर होती है, शेष ग्राफ़ को पुनरावर्ती रूप से ऑर्डर करती है, और फिर हटाए गए शीर्ष को परिणामी क्रम के एक छोर पर रखती है। के साथ ग्राफ़ के लिए <math>m</math> किनारों और <math>n</math> शीर्षों पर, यह एक चक्रीय उपग्राफ उत्पन्न करता है <math>m/2+n/6</math> किनारे, रैखिक समय में, एक सन्निकटन अनुपात देते हैं {{nowrap|of <math>\tfrac12+\Omega(n/m)</math>.{{r|els}}}} एक और, अधिक जटिल, बहुपद समय सन्निकटन एल्गोरिदम अधिकतम वाले ग्राफ़ पर लागू होता है {{nowrap|degree <math>\Delta</math>,}} और एक अचक्रीयउपग्राफ़ पाता है <math>m/2+\Omega(m/\sqrt{\Delta})</math> किनारों, का एक सन्निकटन अनुपात दे रहा है {{nowrap|form <math>\tfrac12+\Omega(1/\sqrt{\Delta})</math>.{{r|bs97|hr94}}}} कब <math>\Delta=3</math>, सन्निकटन अनुपात <math>8/9</math> हासिल किया जा सकता है।{{r|newman}}
+===यथार्थ (बिल्कुल ठीक)===
+न्यूनतम फीडबैक चाप समुच्चय को खोजने का एक तरीका शीर्षों के अनुक्रम की खोज करना है, ताकि अनुक्रम में यथासंभव कुछ किनारों को बाद के शीर्षों से पहले के शीर्षों की ओर दिष्ट किया जा सके।{{r|younger}} {{nowrap|<math>n</math>-शीर्ष}} ग्राफ के सभी [[क्रमचययों]] को खोजने में {{nowrap| <math>O(n!)</math>}} समय लगेगा, लेकिन [[हेल्ड-कार्प एल्गोरिदम]] पर आधारित एक [[गतिशील प्रोग्रामिंग|गतिक प्रोग्रामिंग]] विधि समष्टि की घातीय मात्रा का उपयोग करके समय {{nowrap|<math>O(n2^n)</math>}} में इष्टतम क्रमचय को प्राप्त कर सकती है।{{r|lawler|bfkkt}} एक [[फूट डालो और जीतो एल्गोरिथ्म|डिवाइड और कॉन्कर एल्गोरिथ्म]] जो शीर्षों के सभी विभाजनों को दो समान उपसमुच्चयों में परीक्षण करता है और प्रत्येक उपसमुच्चय के भीतर पुनरावृत्ति करता है, [[बहुपद समष्टि]] का उपयोग करके समय {{nowrap| <math>O(4^n/\sqrt{n})</math>}} में समस्या को हल कर सकता है।{{r|bfkkt}}
+[[पैरामीटरयुक्त जटिलता|पैरामिट्रीकृत सम्मिश्रता]] में, एल्गोरिदम के लिए समय को न केवल इनपुट ग्राफ़ के आकार के संदर्भ में मापा जाता है, बल्कि ग्राफ़ के एक अलग पैरामीटर के संदर्भ में भी मापा जाता है। विशेष रूप से, न्यूनतम फीडबैक चाप समुच्चय समस्या के लिए, तथाकथित ''सहज पैरामीटर'' न्यूनतम फीडबैक चाप समुच्चय का आमाप है। <math>n</math> शीर्षों वाले ग्राफों पर, सहज पैरामीटर {{nowrap| <math>k</math>}} के साथ, फीडबैक चाप समुच्चय समस्या को समय {{nowrap|<math>O(n^44^kk^3k!)</math>}} में हल किया जा सकता है, इसे समतुल्य फीडबैक शीर्ष समुच्चय समस्या में परिवर्तित करके और एक पैरामिट्रीकृत फीडबैक शीर्ष समुच्चय एल्गोरिदम में लागू किया जा सकता है। चूँकि इस एल्गोरिथ्म में <math>n</math> का घातांक नियतांक ''4'' है, जो {{nowrap|<math>k</math>}} से स्वतंत्र है, इस एल्गोरिथम को निश्चित-पैरामीटर ट्रैक्टेबल कहा जाता है।{{r|cllor}}
+सहज पैरामीटर के अतिरिक्त अन्य परमीटरों का भी अध्ययन किया गया है। गतिक प्रोग्रामिंग का उपयोग करके एक निश्चित-पैरामीटर ट्रैक्टेबल एल्गोरिदम समय {{nowrap| <math>O(2^r m^4\log m)</math>}} में न्यूनतम फीडबैक चाप समुच्चय प्राप्त कर सकता है, जहां <math>r</math> अंतर्निहित अदिष्ट ग्राफ़ का [[परिपथ कोटि|परिपथ रैंक]] ([[परिपथ कोटि|कोटि]]) है। परिपथ रैंक फीडबैक चाप समुच्चय का एक अदिष्ट अनुरूप है, किनारों की न्यूनतम संख्या जिसे ग्राफ़ से एक [[विस्तरित तरु]] तक कम करने के लिए हटाने की आवश्यकता होती है; न्यूनतम फीडबैक चाप समुच्चय की तुलना में इसकी गणना करना बहुत आसान है।{{r|Hecht}}[[ट्रीविड्थ]] {{nowrap| <math>t</math>}} के ग्राफ़ के लिए, ग्राफ़ के तरु अपघटन पर गतिक प्रोग्रामिंग, ग्राफ़ आमाप में समय बहुपद और {{nowrap|<math>O(t\log t)</math>}} में घातांक में निर्धारित न्यूनतम फीडबैक चाप समुच्चय प्राप्त कर सकते हैं। घातीय समय परिकल्पना के अंतर्गत, <math>t</math> पर कोई बेहतर आश्रितता संभव नहीं है।{{r|bknpsw}}
+फीडबैक चाप समुच्चय के आमाप को कम करने के बजाय, शोधकर्ताओं ने किसी भी शीर्ष से हटाए गए किनारों की अधिकतम संख्या को कम करने पर भी ध्यान दिया है। समस्या की इस भिन्नता को [[रैखिक समय]] में हल किया जा सकता है।{{r|ls89}} सभी अल्पिष्ठ फीडबैक चाप समुच्चयों को प्रति समुच्चय [[बहुपद विलंब]] के साथ एक एल्गोरिदम द्वारा सूचीबद्ध किया जा सकता है।{{r|ss02}}
+===सन्निकट===
+फीडबैक चाप समुच्चय के लिए बहुपद-काल सन्निकटन एल्गोरिथ्म में अस्थिर  [[सन्निकटन अनुपात]] {{nowrap|<math>O(\log n\log\log n)</math>}} है|  इसका अर्थ यह है कि फीडबैक चाप समुच्चय का आमाप जो इसे मिलता है वह अधिकतम गुणक इष्टतम से बड़ा होता है।{{r|enss}} यह निर्धारित करना कि क्या फीडबैक चाप समुच्चय में एक स्थिर-अनुपात सन्निकटन एल्गोरिथ्म है, या क्या एक अस्थिर अनुपात आवश्यक है, एक विवृत समस्या बनी हुई है।{{r|compendium}}
+अधिकतम अचक्रीय उपग्राफ समस्या में एक आसान सन्निकटन एल्गोरिथ्म है जो {{nowrap|<math>\tfrac12</math>}} का सन्निकटन अनुपात प्राप्त करता है:
+*शीर्षों का स्वेच्छ अनुक्रम निर्धारित करें
+*किनारों को दो अचक्रीय उपग्राफों में विभाजित करें, एक में अनुक्रम के अनुरूप दिष्ट किनारे होते हैं, और दूसरे में अनुक्रम की विपरीत दिशा में दिष्ट किनारे होते हैं।
+*दो उपग्राफों में से बड़े को प्रतिगम करते हैं।
+अनुक्रम चुनने के लिए एक [[लालची एल्गोरिदम|ग्रीडी एल्गोरिदम]] का उपयोग करके इसे बेहतर बनाया जा सकता है। यह एल्गोरिदम एक शीर्ष को खोजता है और हटा देता है जिसके आगामी और निर्गामी किनारों की संख्या यथासंभव दूर होती है| <math>m</math> किनारों और <math>n</math> शीर्षों वाले ग्राफों के लिए, यह रैखिक समय में <math>m/2+n/6</math> किनारों के साथ एक अचक्रीय उपग्राफ उत्पन्न करता है, जो {{nowrap| <math>\tfrac12+\Omega(n/m)</math>{{r|els}}}} का सन्निकटन अनुपात देता है। एक और, अधिक जटिल, बहुपद काल सन्निकटन एल्गोरिदम अधिकतम डिग्री {{nowrap| <math>\Delta</math>}} वाले ग्राफ़ पर लागू होता है, और <math>m/2+\Omega(m/\sqrt{\Delta})</math> किनारों के साथ एक अचक्रीय उपग्राफ खोजता है, जो {{nowrap|<math>\tfrac12+\Omega(1/\sqrt{\Delta})</math>{{r|bs97|hr94}}}} का सन्निकटन अनुपात देता है। जब <math>\Delta=3</math>, तब सन्निकटन अनुपात <math>8/9</math> प्राप्त किया जा सकता है।{{r|newman}}
 ===प्रतिबंधित इनपुट===
-दिष्ट समतलीय ग्राफ़ में, फीडबैक चाप समुच्चय समस्या परिणामी ग्राफ़ को मजबूती [[दृढ़ता से जुड़ा हुआ ग्राफ़]] बनाने के लिए किनारों के एक समुच्चय (एक डाइजॉइन) को अनुबंधित करने की समस्या का [[दोहरा ग्राफ]]़ है।{{r|gab95}} यह दोहरी समस्या बहुपद रूप से हल करने योग्य है,{{r|frank}} और इसलिए समतल न्यूनतम फीडबैक चाप समुच्चय समस्या भी है।{{r|ly78|frank}}इसमें समाधान किया जा सकता है {{nowrap|time <math>O(n^{5/2}\log n)</math>.{{r|gab93}}}} समस्या का एक भारित संस्करण हल किया जा सकता है {{nowrap|time <math>O(n^3)</math>,{{r|gab95}}}} या जब भार धनात्मक पूर्णांक होते हैं जो अधिकतम a होते हैं {{nowrap|number <math>N</math>,}} में {{nowrap|time <math>O(n^{5/2}\log nN)</math>.{{r|gab93}}}} इन समतल एल्गोरिदम को उन ग्राफ़ों तक बढ़ाया जा सकता है जिनमें [[उपयोगिता ग्राफ]]़ नहीं है <math>K_{3,3}</math> एक [[ ग्राफ लघु ]] के रूप में, इस तथ्य का उपयोग करते हुए कि इन ग्राफ़ के त्रिकोणीय घटक या तो समतल या परिबद्ध आकार के हैं।{{r|np00}} प्लेनर ग्राफ़ को दिष्ट ग्राफ़ के एक वर्ग के लिए एक अलग तरीके से सामान्यीकृत किया गया है जिसे कमजोर अचक्रीयडिग्राफ कहा जाता है, जिसे एक निश्चित [[पॉलीहेड्रल कॉम्बिनेटरिक्स]] के अभिन्न पॉलीटोप द्वारा परिभाषित किया गया है। प्रत्येक तलीय दिष्ट ग्राफ इस अर्थ में कमजोर रूप से चक्रीय है, और फीडबैक चाप समुच्चय समस्या को सभी कमजोर चक्रीय डिग्राफ के लिए बहुपद समय में हल किया जा सकता है।{{r|gjr85}}
+दिष्ट [[समतलीय ग्राफ़]] में, फीडबैक चाप समुच्चय समस्या परिणामी ग्राफ़ को [[दृढ़ता से जुड़ा हुआ ग्राफ़|दृढ़ता से]] [[संयोजित]] करने के लिए किनारों के एक समुच्चय को अनुबंधित करने की समस्या से द्वैती होती है।{{r|gab95}} यह द्वैती समस्या बहुपद रूप से हल करने योग्य है,{{r|frank}} और इसलिए समतल न्यूनतम फीडबैक चाप समुच्चय समस्या भी है।{{r|ly78|frank}}इसमें {{nowrap|समय <math>O(n^{5/2}\log n)</math>{{r|gab93}}}} में हल किया जा सकता है। समस्या का एक भारित संस्करण {{nowrap|समय <math>O(n^3)</math>{{r|gab95}}}}में हल किया जा सकता है, या जब भार धनात्मक पूर्णांक होते हैं जो  {{nowrap|समय <math>O(n^{5/2}\log nN)</math>{{r|gab93}}}}में अधिकतम संख्या ''N'' होते हैं। समतलीय ग्राफ़ को दिष्ट ग्राफ़ के एक वर्ग के लिए एक अलग तरीके से सामान्यीकृत किया गया है जिसे अल्प ''अचक्रीय द्विग्राफ'' कहा जाता है, जो उनके [[फीडबैक चाप]] [[बहुतल|समुच्चयों से संबद्ध एक निश्चित बहुतल]] के [[समाकलन]] द्वारा परिभाषित किया गया है।
-नियंत्रण-प्रवाह ग्राफ#रिड्यूसिबिलिटी दिष्ट ग्राफ़ का एक अन्य वर्ग है जिस पर फीडबैक चाप समुच्चय समस्या को बहुपद समय में हल किया जा सकता है। ये ग्राफ़ कई प्रोग्रामिंग भाषाओं के लिए संरचित कार्यक्रमों में नियंत्रण के प्रवाह का वर्णन करते हैं। हालाँकि संरचित कार्यक्रम अक्सर समतल दिष्ट प्रवाह ग्राफ़ उत्पन्न करते हैं, रिड्यूसिबिलिटी की परिभाषा के लिए ग्राफ़ का समतल होना आवश्यक नहीं है।{{r|ramachandran}}
+प्रत्येक समतलीय दिष्ट ग्राफ इस अर्थ में अल्प रूप से चक्रीय है, और फीडबैक चाप समुच्चय समस्या को सभी अल्प चक्रीय द्विग्राफ के लिए बहुपद काल में हल किया जा सकता है।{{r|gjr85}}
-जब न्यूनतम फीडबैक चाप समुच्चय समस्या [[टूर्नामेंट (ग्राफ सिद्धांत)]] तक सीमित होती है, तो इसमें एक [[बहुपद-समय सन्निकटन योजना]] होती है, जो समस्या के भारित संस्करण को सामान्यीकृत करती है।{{r|MathieuSchudy}} टूर्नामेंटों पर भारित फीडबैक चाप समुच्चय के लिए एक सबएक्सपोनेंशियल पैरामीटरयुक्त एल्गोरिदम भी जाना जाता है।{{r|KarpinskiSchudy}} घने ग्राफ़ के लिए अधिकतम चक्रीय उपग्राफ़ समस्या में एक बहुपद-समय सन्निकटन योजना भी होती है। इसका मुख्य विचार समस्या के [[रैखिक प्रोग्रामिंग विश्राम]] के लिए यादृच्छिक राउंडिंग लागू करना है, और [[विस्तारक ग्राफ]]़ पर चलने का उपयोग करके परिणामी एल्गोरिदम को डीरैंडमाइज़ करना है।{{r|compendium|afk02}}
+[[समानेय-प्रवाह ग्राफ]] दिष्ट ग्राफ़ का एक अन्य वर्ग है जिस पर फीडबैक चाप समुच्चय समस्या को बहुपद काल में हल किया जा सकता है। ये ग्राफ़ कई प्रोग्रामिंग भाषाओं के लिए संरचित प्रोग्रामों में नियंत्रण के प्रवाह का वर्णन करते हैं। हालाँकि संरचित प्रोग्राम अधिकतर समतल दिष्ट प्रवाह ग्राफ़ उत्पन्न करते हैं, समानेयता की परिभाषा के लिए ग्राफ़ का समतल होना आवश्यक नहीं है।{{r|ramachandran}}
+जब न्यूनतम फीडबैक चाप समुच्चय समस्या [[टूर्नामेंट (ग्राफ सिद्धांत)|टूर्नामेंट]] तक सीमित होती है, तो इसमें एक [[बहुपद-समय सन्निकटन योजना|बहुपद-काल सन्निकटन स्कीम]] (अधियोजना) होती है, जो समस्या के भारित संस्करण को सामान्यीकृत करती है।{{r|MathieuSchudy}} टूर्नामेंटों पर भारित फीडबैक चाप समुच्चयों के लिए एक उपघातांकी पैरामिट्रीकृत एल्गोरिदम भी जाना जाता है।{{r|KarpinskiSchudy}} [[सघन ग्राफों]] के लिए अधिकतम अचक्रिय उपग्राफ़ समस्या में एक बहुपद-काल सन्निकटन स्कीम भी होती है। इसका मुख्य विचार यह है कि समस्या के [[रैखिक प्रोग्रामिंग विश्राम|रैखिक प्रोग्रामन विश्रांति]] के लिए [[यादृच्छिक निकटन]] लागू करना है, और [[विस्तारक ग्राफ|प्रसारक ग्राफों]] पर वॉक का उपयोग करके परिणामी एल्गोरिदम को अनियमित करना है।{{r|compendium|afk02}}
 ==कठोरता==
 ===एनपी-कठोरता===
-[[File:Feedback arc set NP-completeness.svg|thumb|upright=1.35| एनपी-पूर्णता में कमी, बड़े पीले ग्राफ के शीर्ष कवर से लेकर छोटे नीले ग्राफ में न्यूनतम फीडबैक चाप समुच्चय तक, प्रत्येक पीले शीर्ष को दो आसन्न नीले ग्राफ कोने में विस्तारित करती है, और प्रत्येक अप्रत्यक्ष पीला किनारा दो विपरीत दिशा वाले किनारों में। न्यूनतम शीर्ष कवर (ऊपरी बाएँ और निचले दाएँ पीले कोने) लाल न्यूनतम फीडबैक चाप समुच्चय से मेल खाता है।]]एनपी-पूर्णता के सिद्धांत को न्यूनतम फीडबैक चाप समुच्चय पर लागू करने के लिए, समस्या को एक अनुकूलन समस्या (सभी चक्रों को तोड़ने के लिए कुछ किनारों को कैसे हटाया जा सकता है) से समतुल्य [[निर्णय संस्करण]] में संशोधित करना आवश्यक है, हाँ के साथ या कोई उत्तर नहीं (क्या इसे हटाना संभव है <math>k</math> किनारों)। इस प्रकार, फीडबैक चाप समुच्चय समस्या का निर्णय संस्करण एक दिष्ट ग्राफ और ए दोनों को इनपुट के रूप में लेता है {{nowrap|number <math>k</math>.}} यह पूछता है कि क्या सभी चक्रों को अधिक से अधिक हटाकर तोड़ा जा सकता है <math>k</math> किनारों, या समकक्ष रूप से क्या कम से कम एक अचक्रीयउपग्राफ है <math>|E(G)|-k</math> किनारों. यह समस्या एनपी-पूर्ण है, जिसका अर्थ है कि न तो इसमें और न ही अनुकूलन समस्या में बहुपद समय एल्गोरिदम होने की उम्मीद है। यह रिचर्ड एम. कार्प के कार्प की 21 एनपी-पूर्ण समस्याओं के मूल समुच्चय में से एक था|21 एनपी-पूर्ण समस्याएं; इसकी एनपी-पूर्णता कार्प और [[यूजीन लॉलर]] द्वारा साबित की गई थी कि एक और कठिन समस्या, [[वर्टेक्स कवर समस्या]] के लिए इनपुट को फीडबैक चाप समुच्चय निर्णय समस्या के समकक्ष इनपुट में परिवर्तित (कम) किया जा सकता है।{{r|karp|gj79}}
+[[File:Feedback arc set NP-completeness.svg|thumb|upright=1.35| कार्प और लॉलर के [[एनपी-पूर्णता में समानयन]], बड़े पीले ग्राफ के शीर्ष कवर से लेकर छोटे नीले ग्राफ में न्यूनतम फीडबैक चाप समुच्चय तक तथा प्रत्येक पीले शीर्ष को दो आसन्न नीले ग्राफ शीर्ष में विस्तारित करते हैं, और प्रत्येक अदिष्‍ट पीले किनारे को दो विपरीत दिशा वाले किनारों में विस्तारित करते हैं। न्यूनतम शीर्ष कवर (ऊपरी बाएँ और निचले दाएँ पीले शीर्ष) लाल न्यूनतम फीडबैक चाप समुच्चय के संगत है।]][[एनपी-पूर्णता]] के सिद्धांत को न्यूनतम फीडबैक चाप समुच्चय पर लागू करने के लिए, समस्या को एक इष्टतमीकरण समस्या (सभी चक्रों को तोड़ने के लिए कुछ किनारों को कैसे हटाया जा सकता है) से समतुल्य [[निर्णय संस्करण]] में आपरिवर्तन करना आवश्यक है, हाँ के साथ या कोई उत्तर नहीं (क्या <math>k</math> किनारों को हटाना संभव है)। इस प्रकार, फीडबैक चाप समुच्चय समस्या का निर्णय संस्करण एक दिष्ट ग्राफ और एक संख्या ''k'' दोनों को इनपुट के रूप में लेता है। यह पूछता है कि क्या सभी चक्रों को अधिकतम <math>k</math> किनारों को हटाकर तोड़ा जा सकता है, या समतुल्य रूप से क्या कम से कम <math>|E(G)|-k</math> किनारों के साथ एक अचक्रीय उपग्राफ है| यह समस्या [[एनपी-पूर्ण]] है, जिसका अर्थ है कि न तो इसमें और न ही इष्टतमीकरण समस्या में बहुपद काल एल्गोरिदम होने की अपेक्षा है। यह [[रिचर्ड एम. कार्प]] की [[21 एनपी-पूर्ण समस्याओं]] के मूल समुच्चय में से एक था; इसकी एनपी-पूर्णता कार्प और [[यूजीन लॉलर]] द्वारा सिद्ध की गई थी कि एक और कठिन समस्या, [[वर्टेक्स कवर समस्या|शीर्ष कवर समस्या]] के लिए इनपुट को फीडबैक चाप समुच्चय निर्णय समस्या के समतुल्य इनपुट में रूपांतरित ("समानीत") किया जा सकता है।{{r|karp|gj79}}
-कुछ एनपी-पूर्ण समस्याएं तब आसान हो सकती हैं जब उनके इनपुट विशेष मामलों तक सीमित हों। लेकिन फीडबैक चाप समुच्चय समस्या के सबसे महत्वपूर्ण विशेष मामले, टूर्नामेंट के मामले में, समस्या एनपी-पूर्ण बनी हुई है।{{r|alon|cty}}
+कुछ एनपी-पूर्ण समस्याएं तब आसान हो सकती हैं जब उनके इनपुट विशेष स्थितियों तक सीमित होते हैं। लेकिन फीडबैक चाप समुच्चय समस्या की सबसे महत्वपूर्ण विशेष स्थिति, टूर्नामेंट की स्थिति में, समस्या एनपी-पूर्ण बनी हुई है।{{r|alon|cty}}
 ===अप्राप्यता===
 सम्मिश्रता वर्ग [[APX]] को इष्टमीकरण समस्याओं से युक्त के रूप में परिभाषित किया गया है जिसमें एक बहुपद काल सन्निकटन एल्गोरिथ्म होता है जो एक नियत [[सन्निकटन अनुपात]] प्राप्त करता है। हालाँकि फीडबैक चाप समुच्चय समस्या के लिए ऐसे सन्निकटन ज्ञात नहीं हैं, समस्या को [[APX-हार्ड]] के रूप में जाना जाता है, जिसका अर्थ है कि इसके लिए सटीक सन्निकटन का उपयोग APX में अन्य सभी समस्याओं के लिए समान सटीक सन्निकटन प्राप्त करने के लिए किया जा सकता है। इसके कठोरता प्रमाण के परिणामस्वरूप, जब तक कि [[P = NP]] न हो, इसका कोई बहुपद काल सन्निकटन अनुपात 1.3606 से बेहतर नहीं है। यह सन्निकटन की कठोरता के लिए वही सीमा है जो शीर्ष् कवर के लिए जानी जाती है, और प्रमाण शीर्ष् कवर से फीडबैक चाप समुच्चय तक कार्प-लॉलर [[समानयन]] का उपयोग करता है, जो सन्निकटन की गुणवत्ता को संरक्षित करता है।{{r|compendium|adp80|kann|ds05}} एक भिन्न समानयन से, अधिकतम अचक्रीय उपग्राफ समस्या भी एपीएक्स-हार्ड है, और एनपी-हार्ड को इष्टतम के 65/66 के गुणक के भीतर सन्निकटित किया जा सकता है।{{r|newman}}
-इन समस्याओं के सन्निकटन की कठोरता का अध्ययन अप्रमाणित [[अभिकलनी कठोरता अभिधारणाओं]] के अंतर्गत भी किया गया है जो अभिकलनात्मक जटिलता सिद्धांत में मानक हैं लेकिन P ≠ NP से अधिक दृढ़ हैं। यदि अद्वितीय गेम का अनुमानित कथन सत्य है, तो न्यूनतम फीडबैक चाप समुच्चय समस्या को किसी भी नियत गुणक के भीतर बहुपद काल में सन्निकटित करना कठिन है, और अधिकतम फीडबैक चाप समुच्चय समस्या को प्रत्येक <math>\varepsilon>0</math> के लिए {{nowrap|<math>\tfrac12+\varepsilon</math>}} के गुणक के भीतर सन्निकटित करना कठिन है। सन्निकटन एल्गोरिदम के लिए बहुपद काल के अलावा, यदि घातीय समय परिकल्पना सत्य है, तो प्रत्येक <math>\varepsilon>0</math> के लिए न्यूनतम फीडबैक चाप समुच्चय में गुणक <math>\tfrac76-\varepsilon</math> के भीतर एक सन्निकटन नहीं होता है जिसे उपघातीय समय सीमा {{nowrap|<math>O(2^{n^{1-\varepsilon}})</math>.{{r|bp18}}}}में गणना किया जा सकती है।
+इन समस्याओं के सन्निकटन की कठोरता का अध्ययन अप्रमाणित [[अभिकलनी कठोरता अभिधारणाओं]] के अंतर्गत भी किया गया है जो अभिकलनात्मक जटिलता सिद्धांत में मानक हैं लेकिन P ≠ NP से अधिक दृढ़ हैं। यदि अद्वितीय गेम का अनुमानित कथन सत्य है, तो न्यूनतम फीडबैक चाप समुच्चय समस्या को किसी भी नियत गुणक के भीतर बहुपद काल में सन्निकटित करना कठिन है, और अधिकतम फीडबैक चाप समुच्चय समस्या को प्रत्येक <math>\varepsilon>0</math> के लिए {{nowrap|<math>\tfrac12+\varepsilon</math>}} के गुणक के भीतर सन्निकटित करना कठिन है। सन्निकटन एल्गोरिदम के लिए बहुपद काल के अलावा, यदि घातीय समय परिकल्पना सत्य है, तो प्रत्येक <math>\varepsilon>0</math> के लिए न्यूनतम फीडबैक चाप समुच्चय में गुणक <math>\tfrac76-\varepsilon</math> के भीतर एक सन्निकटन नहीं होता है जिसे उपघातीय समय सीमा {{nowrap|<math>O(2^{n^{1-\varepsilon}})</math>.{{r|bp18}}}}में गणना किया जा सकती है।{{r|ghmrc}}}}
 ==सिद्धांत==
-समतल दिष्ट ग्राफों में, फीडबैक चाप समुच्चय समस्या [[न्यूनतम-अधिकतम प्रमेय]] का पालन करती है: फीडबैक चाप समुच्चय का न्यूनतम आमाप किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या के समान होता है जो ग्राफ़ में पाए जा सकते हैं।{{r|ly78|lovasz}} यह कुछ अन्य ग्राफों के लिए सत्य नहीं है; उदाहरण के लिए पहला चित्र असमतलीय  ग्राफ़ <math>K_{3,3}</math> का एक दिष्ट संस्करण दिखाता है जिसमें फीडबैक चाप समुच्चय का न्यूनतम आमाप दो है, जबकि किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या केवल एक है।
+समतल दिष्ट ग्राफों में, फीडबैक चाप समुच्चय समस्या [[न्यूनतम-अधिकतम प्रमेय]] का पालन करती है: फीडबैक चाप समुच्चय का न्यूनतम आमाप किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या के समान होता है जो ग्राफ़ में पाए जा सकते हैं।{{r|ly78|lovasz}} यह कुछ अन्य ग्राफों के लिए सत्य नहीं है; उदाहरण के लिए पहला चित्र असमतलीय ग्राफ़ <math>K_{3,3}</math> का एक दिष्ट संस्करण दिखाता है जिसमें फीडबैक चाप समुच्चय का न्यूनतम आमाप दो है, जबकि किनारे-असंयुक्त दिष्ट चक्रों की अधिकतम संख्या केवल एक है।
-प्रत्येक टूर्नामेंट ग्राफ़ में एक [[हैमिल्टनियन पथ]] होता है, और हैमिल्टनियन पथ न्यूनतम फीडबैक चाप समुच्चय के साथ एक-के-लिए-एक के अनुरूप होते हैं, जो संबंधित पथ से अलग होते हैं। फीडबैक चाप समुच्चय के लिए हैमिल्टनियन पथ इसके चाप को उत्क्रम कर और परिणामी अचक्रीय टूर्नामेंट का सांस्थितिक अनुक्रम खोजकर पाया जाता है। अनुक्रम के प्रत्येक क्रमागत युग्म फीडबैक चाप समुच्चय से असंयुक्त होने चाहिए, क्योंकि अन्यथा उस युग्म को उत्क्रम कर एक छोटा फीडबैक चाप समुच्चय मिल सकता है। इसलिए, यह अनुक्रम सभी शीर्षों को कवर करते हुए, मूल टूर्नामेंट के चापों के माध्यम से एक पथ देता है। इसके विपरीत, किसी भी हैमिल्टनियन पथ से, किनारों का समुच्चय जो पथ में बाद के शीर्षों को पहले वाले शीर्षों से जोड़ता है, एक फीडबैक चाप समुच्चय बनाता है। यह अल्पिष्ठ है, क्योंकि इसका प्रत्येक किनारा हैमिल्टनियन पथ किनारों वाले एक चक्र से संबंधित है जो ऐसे अन्य सभी चक्रों से अलग है।{{r|bn90}} एक टूर्नामेंट में, ऐसा हो सकता है कि न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ दोनों अर्ध किनारों के सटीक हों। अधिक सटीक रूप से, प्रत्येक टूर्नामेंट ग्राफ़ में आमाप{{nowrap|<math>\tbinom{n}{2}/2-\Omega(n^{3/2})</math>}} का फीडबैक चाप समुच्चय होता है, और कुछ टूर्नामेंटों के लिए आमाप{{nowrap|<math>\tbinom{n}{2}/2-O(n^{3/2})</math> की आवश्यकता होती है।{{r|spencer}}}} [[लगभग सभी]] टूर्नामेंटों के लिए, आमाप कम से कम {{nowrap|<math>\tbinom{n}{2}/2 - 1.73n^{3/2}</math> होता है।{{r|fdlv}}}} प्रत्येक [[दिष्ट चक्रीय ग्राफ]] <math>D</math> को एक बड़े टूर्नामेंट ग्राफ के उपग्राफ के रूप में अंत:स्थापित किया जा सकता है, इस प्रकार से कि <math>D</math> टूर्नामेंट का अनन्य न्यूनतम फीडबैक चाप समुच्चय है। इस टूर्नामेंट के आमाप को {{nowrap| <math>D</math>}} की "उत्क्रमी संख्या" के रूप में परिभाषित किया गया है, और समान संख्या में शीर्षों के साथ दिष्ट चक्रीय ग्राफों के मध्य सबसे बड़ा है जब <math>D</math> स्वयं एक (अचक्रीय) टूर्नामेंट है।
+प्रत्येक टूर्नामेंट ग्राफ़ में एक [[हैमिल्टनियन पथ]] होता है, और हैमिल्टनियन पथ न्यूनतम फीडबैक चाप समुच्चय के साथ एक-के-लिए-एक के अनुरूप होते हैं, जो संबंधित पथ से अलग होते हैं। फीडबैक चाप समुच्चय के लिए हैमिल्टनियन पथ इसके चाप को उत्क्रम कर और परिणामी अचक्रीय टूर्नामेंट का सांस्थितिक अनुक्रम खोजकर पाया जाता है। अनुक्रम के प्रत्येक क्रमागत युग्म फीडबैक चाप समुच्चय से असंयुक्त होने चाहिए, क्योंकि अन्यथा उस युग्म को उत्क्रम कर एक छोटा फीडबैक चाप समुच्चय मिल सकता है। इसलिए, यह अनुक्रम सभी शीर्षों को आवरण करते हुए, मूल टूर्नामेंट के चापों के माध्यम से एक पथ देता है। इसके विपरीत, किसी भी हैमिल्टनियन पथ से, किनारों का समुच्चय जो पथ में बाद के शीर्षों को पहले वाले शीर्षों से जोड़ता है, एक फीडबैक चाप समुच्चय बनाता है। यह अल्पिष्ठ है, क्योंकि इसका प्रत्येक किनारा हैमिल्टनियन पथ किनारों वाले एक चक्र से संबंधित है जो ऐसे अन्य सभी चक्रों से अलग है।{{r|bn90}} एक टूर्नामेंट में, ऐसा हो सकता है कि न्यूनतम फीडबैक चाप समुच्चय और अधिकतम अचक्रीय उपग्राफ दोनों अर्ध किनारों के सटीक हों। अधिक सटीक रूप से, प्रत्येक टूर्नामेंट ग्राफ़ में आमाप{{nowrap|<math>\tbinom{n}{2}/2-\Omega(n^{3/2})</math>}} का फीडबैक चाप समुच्चय होता है, और कुछ टूर्नामेंटों के लिए आमाप{{nowrap|<math>\tbinom{n}{2}/2-O(n^{3/2})</math> की आवश्यकता होती है।{{r|spencer}}}} [[लगभग सभी]] टूर्नामेंटों के लिए, आमाप कम से कम {{nowrap|<math>\tbinom{n}{2}/2 - 1.73n^{3/2}</math> होता है।{{r|fdlv}}}} प्रत्येक [[दिष्ट चक्रीय ग्राफ]] <math>D</math> को एक बड़े टूर्नामेंट ग्राफ के उपग्राफ के रूप में अंत:स्थापित किया जा सकता है, इस प्रकार से कि <math>D</math> टूर्नामेंट का अनन्य न्यूनतम फीडबैक चाप समुच्चय है। इस टूर्नामेंट के आमाप को{{nowrap| <math>D</math>}} की "उत्क्रमी संख्या" के रूप में परिभाषित किया गया है, और समान संख्या में शीर्षों के साथ दिष्ट अचक्रीय ग्राफों के मध्य यह सबसे बड़ा है जब <math>D</math> स्वयं एक (अचक्रीय) टूर्नामेंट है।
 {{r|bhirt|in04}}
-एक दिष्ट ग्राफ़ में एक [[यूलर टावर|यूलर टूर]] (परिक्रम) होता है जब भी यह [[दृढ़ता से जुड़ा]] होता है और प्रत्येक शीर्ष पर आगामी और निर्गामी किनारों की समान संख्या होती है। ऐसे ग्राफ़ के लिए, <math>m</math> किनारों और <math>n</math> शीर्षों के साथ, न्यूनतम फीडबैक चाप समुच्चय का आमाप सदैव कम से कम  {{nowrap|<math>(m^2+mn)/2n^2</math>}} होता है| ऐसे अपरिमित यूलेरियन दिष्ट ग्राफ़ हैं जिनके लिए यह परिबद्ध सीमित है।{{r|hmssy}} यदि किसी दिष्ट ग्राफ में <math>n</math> शीर्ष हैं तथा प्रत्येक शीर्ष पर अधिकतम तीन किनारे हैं, तो इसमें अधिकतम <math>n/3</math> किनारों का एक फीडबैक चाप समुच्चय होता है और कुछ ग्राफों के लिए इतने की आवश्यकता होती है। यदि किसी दिष्ट ग्राफ़ में <math>m</math> किनारे हैं तथा प्रत्येक शीर्ष पर अधिकतम चार किनारे हैं, तो इसमें अधिकतम <math>m/3</math> किनारों का एक फीडबैक चाप समुच्चय होता है, और कुछ ग्राफों के लिए इतने की आवश्यकता होती है।{{r|hba}}
+एक दिष्ट ग्राफ़ में एक [[यूलर टावर|यूलर टूर]] (परिक्रम) होता है जब भी यह [[दृढ़ता से जुड़ा|दृढ़ता से संयुग्मित]]  होता है और प्रत्येक शीर्ष पर आगामी और निर्गामी किनारों की समान संख्या होती है। ऐसे ग्राफ़ के लिए, <math>m</math> किनारों और <math>n</math> शीर्षों के साथ, न्यूनतम फीडबैक चाप समुच्चय का आमाप सदैव कम से कम  {{nowrap|<math>(m^2+mn)/2n^2</math>}} होता है| ऐसे अपरिमित यूलेरियन दिष्ट ग्राफ़ हैं जिनके लिए यह परिबद्ध सीमित है।{{r|hmssy}} यदि किसी दिष्ट ग्राफ में <math>n</math> शीर्ष हैं तथा प्रत्येक शीर्ष पर अधिकतम तीन किनारे हैं, तो इसमें अधिकतम <math>n/3</math> किनारों का एक फीडबैक चाप समुच्चय होता है और कुछ ग्राफों के लिए इतने की आवश्यकता होती है। यदि किसी दिष्ट ग्राफ़ में <math>m</math> किनारे हैं तथा प्रत्येक शीर्ष पर अधिकतम चार किनारे हैं, तो इसमें अधिकतम <math>m/3</math> किनारों का एक फीडबैक चाप समुच्चय होता है, और कुछ ग्राफों के लिए इतने की आवश्यकता होती है।{{r|hba}}
 ==संदर्भ==
@@ Line 942: / Line 965: @@
 }}
-{{DEFAULTSORT:Feedback Arc Set}}[[Category: निर्देशित रेखांकन]] [[Category: ग्राफ़ सिद्धांत वस्तुएँ]] [[Category: एनपी-पूर्ण समस्याएँ]] [[Category: ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]]
+{{DEFAULTSORT:Feedback Arc Set}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 11/07/2023|Feedback Arc Set]]
-[[Category:Created On 11/07/2023]]
+[[Category:Good articles|Feedback Arc Set]]
+[[Category:Lua-based templates|Feedback Arc Set]]
+[[Category:Machine Translated Page|Feedback Arc Set]]
+[[Category:Pages with reference errors|Feedback Arc Set]]
+[[Category:Pages with script errors|Feedback Arc Set]]
+[[Category:Short description with empty Wikidata description|Feedback Arc Set]]
+[[Category:Template documentation pages|Short description/doc]]
+[[Category:Templates Vigyan Ready|Feedback Arc Set]]
+[[Category:Templates that add a tracking category|Feedback Arc Set]]
+[[Category:Templates that generate short descriptions|Feedback Arc Set]]
+[[Category:Templates using TemplateData|Feedback Arc Set]]
+[[Category:Webarchive template wayback links]]
+[[Category:एनपी-पूर्ण समस्याएँ|Feedback Arc Set]]
+[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं|Feedback Arc Set]]
+[[Category:ग्राफ़ सिद्धांत वस्तुएँ|Feedback Arc Set]]
+[[Category:निर्देशित रेखांकन|Feedback Arc Set]]

Anonymous

Search

फीडबैक आर्क सेट: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:29, 18 July 2023

Contents

अनुप्रयोग

एल्गोरिदम

समतुल्यताएं

यथार्थ (बिल्कुल ठीक)

सन्निकट

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

कठोरता

एनपी-कठोरता

अप्राप्यता

सिद्धांत

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फीडबैक आर्क सेट: Difference between revisions

Latest revision as of 10:29, 18 July 2023

अनुप्रयोग

एल्गोरिदम

समतुल्यताएं

यथार्थ (बिल्कुल ठीक)

सन्निकट

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

कठोरता

एनपी-कठोरता

अप्राप्यता

सिद्धांत

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories