वर्टेक्स कवर

उदाहरण ग्राफ़ जिसमें वर्टेक्स कवर होता है जिसमें 2 कोने (नीचे) होते हैं, लेकिन कम के साथ कोई नहीं।

किनारा (ग्राफ सिद्धांत), ग्राफ़ (असतत गणित) का वर्टेक्स कवर (कभी-कभी नोड कवर) वर्टेक्स का समूह होता है जिसमें ग्राफ़ के प्रत्येक किनारा (ग्राफ़ थ्योरी) का कम से कम समापन बिंदु सम्मलित होता है।

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

न्यूनतम वर्टेक्स कवर समस्या को आधा-पूर्णांक | आधा-अभिन्न, रैखिक कार्यक्रम के रूप में तैयार किया जा सकता है जिसका दोहरा रैखिक कार्यक्रम अधिकतम मिलान समस्या है।

वर्टेक्स कवर की समस्याओं को हाइपरग्राफ के लिए सामान्यीकृत किया गया है, देखें हाइपरग्राफ में वर्टेक्स कवर।

परिभाषा

वर्टेक्स कवर के उदाहरण

न्यूनतम वर्टेक्स कवर के उदाहरण

औपचारिक रूप से, वर्टेक्स कवर $V'$ अप्रत्यक्ष ग्राफ का $G=(V,E)$ का उपसमुच्चय है $V$ ऐसा है कि $uv\in E\Rightarrow u\in V'\lor v\in V'$, अर्थात यह शीर्षों का समूह है $V'$ जहां प्रत्येक किनारे के शीर्ष कवर में कम से कम समापन बिंदु होता है $V'$. इस तरह के समूह के किनारों को कवर करने के लिए कहा जाता है $G$. ऊपरी आंकड़ा वर्टेक्स कवर के दो उदाहरण दिखाता है, कुछ वर्टेक्स कवर के साथ $V'$ लाल रंग में चिह्नित।

न्यूनतम वर्टेक्स कवर सबसे छोटे संभव आकार का वर्टेक्स कवर है। वर्टेक्स कवर नंबर $\tau$ न्यूनतम वर्टेक्स कवर का आकार है, अर्थात $\tau =|V'|$. निचला आंकड़ा पिछले ग्राफ़ में न्यूनतम वर्टेक्स कवर के उदाहरण दिखाता है।

उदाहरण

• सभी शीर्षों का समुच्चय शीर्ष आवरण है।
• किसी भी अधिकतम मिलान के समापन बिंदु वर्टेक्स कवर बनाते हैं।
• पूरा द्विपक्षीय ग्राफ $K_{m,n}$ आकार का न्यूनतम वर्टेक्स कवर है $\tau (K_{m,n})=\min\{\,m,n\,\}$.

गुण

• वर्टिकल का समूह वर्टेक्स कवर है अगर और केवल अगर इसका पूरक (समूह थ्योरी) स्वतंत्र समूह (ग्राफ थ्योरी) है।
• नतीजतन, ग्राफ के शीर्षों की संख्या इसके न्यूनतम शीर्ष आवरण संख्या और अधिकतम स्वतंत्र समूह के आकार के बराबर होती है (तिबोर सकता है 1959)।

अभिकलनात्मक समस्या

न्यूनतम वर्टेक्स कवर समस्या किसी दिए गए ग्राफ़ में सबसे छोटा वर्टेक्स कवर खोजने की अनुकूलन समस्या है।

उदाहरण: ग्राफ $G$

आउटपुट: सबसे छोटी संख्या $k$ ऐसा है कि $G$ आकार का वर्टेक्स कवर है $k$.

यदि समस्या को निर्णय समस्या के रूप में कहा जाता है, तो इसे वर्टेक्स कवर समस्या कहा जाता है:

उदाहरण: ग्राफ $G$ और सकारात्मक पूर्णांक $k$.

प्रश्न: करता है $G$ अधिकतम आकार का वर्टेक्स कवर है $k$?

वर्टेक्स कवर समस्या एनपी-पूर्ण समस्या है: यह कार्प की 21 एनपी-पूर्ण समस्याओं में से थी। यह अक्सर अभिकलनात्मक जटिलता सिद्धांत में एनपी-कठोरता प्रमाण के लिए प्रारंभिक बिंदु के रूप में उपयोग किया जाता है।

आईएलपी सूत्रीकरण

मान लें कि प्रत्येक शीर्ष की संबद्ध लागत है $c(v)\geq 0$. (भारित) न्यूनतम वर्टेक्स कवर समस्या को निम्नलिखित पूर्णांक रेखीय कार्यक्रम (ILP) के रूप में तैयार किया जा सकता है।

minimize	$\textstyle \sum _{v\in V}c(v)x_{v}$			(minimize the total cost)
subject to	$x_{u}+x_{v}\geq 1$	for all $\{u,v\}\in E$		(cover every edge of the graph),
	$x_{v}\in \{0,1\}$	for all $v\in V$.		(every vertex is either in the vertex cover or not)

यह ILP समस्याओं को कवर करने के लिए ILPs के अधिक सामान्य वर्ग से संबंधित है। इस ILP का लीनियर प्रोग्रामिंग रिलैक्सेशन# सन्निकटन और इंटीग्रेलिटी गैप है $2$, इसलिए इसकी रैखिक प्रोग्रामिंग छूट (प्रत्येक चर को 0 से 1 के अंतराल में होने की अनुमति देता है, न कि केवल 0 या 1 होने के लिए चर की आवश्यकता होती है) कारक देता है-$2$ न्यूनतम वर्टेक्स कवर समस्या के लिए सन्निकटन एल्गोरिथम। इसके अतिरिक्त, उस आईएलपी की रैखिक प्रोग्रामिंग छूट आधा-अभिन्न है, यानी, इष्टतम समाधान मौजूद है जिसके लिए प्रत्येक प्रविष्टि $x_{v}$ या तो 0, 1/2, या 1 है। इस भिन्नात्मक समाधान से 2-अनुमानित वर्टेक्स कवर प्राप्त किया जा सकता है, जिसके वेरिएबल्स नॉनज़रो हैं।

सटीक मूल्यांकन

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

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

फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी

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

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

अनुमानित मूल्यांकन

किनारे के दोनों समापन बिंदुओं को बार-बार वर्टेक्स कवर में ले जाकर, फिर उन्हें ग्राफ़ से हटाकर कारक -2 सन्निकटन एल्गोरिथम पा सकता है। अन्यथा रखो, हम लालची एल्गोरिथ्म के साथ अधिकतम मिलान एम पाते हैं और वर्टेक्स कवर सी का निर्माण करते हैं जिसमें एम में किनारों के सभी समापन बिंदु होते हैं। निम्नलिखित आकृति में, अधिकतम मिलान एम को लाल रंग से चिह्नित किया गया है, और वर्टेक्स कवर सी है नीले रंग से चिह्नित।

इस तरह से निर्मित समूह सी वर्टेक्स कवर है: मान लीजिए कि किनारा ई सी द्वारा कवर नहीं किया गया है; तो M ∪ {e} मिलान है और e ∉ M, जो इस धारणा के विपरीत है कि M अधिकतम है। इसके अतिरिक्त, यदि e = {u, v} ∈ M, तो किसी भी वर्टेक्स कवर - इष्टतम वर्टेक्स कवर सहित - में u या v (या दोनों) होना चाहिए; अन्यथा किनारा ई ढका नहीं है। यही है, इष्टतम कवर में एम में प्रत्येक किनारे का कम से कम समापन बिंदु होता है; कुल मिलाकर, समूह सी इष्टतम वर्टेक्स कवर के रूप में अधिकतम 2 गुना बड़ा है।

यह सरल एल्गोरिथम स्वतंत्र रूप से फैनिका गैवरिल और माइकलिस यानाकाकिस द्वारा खोजा गया था। अधिक सम्मलित तकनीकों से पता चलता है कि थोड़ा बेहतर सन्निकटन कारक के साथ सन्निकटन एल्गोरिदम हैं। उदाहरण के लिए, सन्निकटन एल्गोरिथम सन्निकटन कारक के साथ ${\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}$ ज्ञात है। समस्या को सन्निकटन कारक के साथ अनुमानित किया जा सकता है $2/(1+\delta )$ में $\delta$ - घने रेखांकन।

अनुपयुक्तता

उपरोक्त की तुलना में कोई बेहतर स्थिर-कारक सन्निकटन एल्गोरिथम ज्ञात नहीं है। न्यूनतम वर्टेक्स कवर समस्या APX|APX-पूर्ण है, अर्थात, इसे मनमाने ढंग से अच्छी तरह से अनुमानित नहीं किया जा सकता है जब तक कि P = NP समस्या|P = NP। पीसीपी प्रमेय की तकनीकों का उपयोग करते हुए, इरिट दिनूर और शमूएल सफरा ने 2005 में साबित किया कि किसी भी पर्याप्त बड़ी शीर्ष डिग्री के लिए 1.3606 के कारक के भीतर न्यूनतम वर्टेक्स कवर का अनुमान नहीं लगाया जा सकता है जब तक कि P = NP नहीं। बाद में, कारक में सुधार किया गया ${\sqrt {2}}-\epsilon$ किसी के लिए $\epsilon >0$. इसके अतिरिक्त, यदि अद्वितीय खेलों का अनुमान सही है, तो न्यूनतम वर्टेक्स कवर को 2 से बेहतर किसी भी स्थिर कारक के भीतर अनुमानित नहीं किया जा सकता है। यद्यपि न्यूनतम-आकार के वर्टेक्स कवर को खोजना अधिकतम-आकार के स्वतंत्र समूह को खोजने के बराबर है, जैसा कि ऊपर वर्णित है, दो समस्याएं सन्निकटन-संरक्षण के तरीके के बराबर नहीं हैं: स्वतंत्र समूह समस्या का कोई स्थिर-कारक सन्निकटन नहीं है जब तक कि 'पी' = 'एनपी'।

स्यूडोकोड

APPROXIMATION-VERTEX-COVER(G)
C = ∅
E'= G.E

while E' ≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v

return C

अनुप्रयोग

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

संदर्भ

• Chen, Jianer; Kanj, Iyad A.; Xia, Ge (2006). "Improved Parameterized Upper Bounds for Vertex Cover". Mathematical Foundations of Computer Science 2006: 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings (PDF). Lecture Notes in Computer Science. Vol. 4162. Springer-Verlag. pp. 238–249. doi:10.1007/11821069_21. ISBN 978-3-540-37791-7.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Cambridge, Mass.: MIT Press and McGraw-Hill. pp. 1024–1027. ISBN 0-262-03293-7.
• Demaine, Erik; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2005). "Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs". Journal of the ACM. 52 (6): 866–893. doi:10.1145/1101821.1101823. S2CID 6238832. Retrieved 2010-03-05.
• Dinur, Irit; Safra, Samuel (2005). "On the hardness of approximating minimum vertex cover". Annals of Mathematics. 162 (1): 439–485. CiteSeerX 10.1.1.125.334. doi:10.4007/annals.2005.162.439.
• Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. ISBN 978-3-540-29952-3. Retrieved 2010-03-05.
• Garey, Michael R.; Johnson, David S. (1977). "The rectilinear Steiner tree problem is NP-complete". SIAM Journal on Applied Mathematics. 32 (4): 826–834. doi:10.1137/0132071.
• Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT1, pg.190.
• Garey, Michael R.; Johnson, David S.; Stockmeyer, Larry (1974). "Some simplified NP-complete problems". Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. pp. 47–63. doi:10.1145/800119.803884.
• Gallai, Tibor (1959). "Über extreme Punkt- und Kantenmengen". Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 2: 133–138.
• Karakostas, George (November 2009). "A better approximation ratio for the vertex cover problem" (PDF). ACM Transactions on Algorithms. 5 (4): 41:1–41:8. CiteSeerX 10.1.1.649.7407. doi:10.1145/1597036.1597045. S2CID 2525818. ECCC TR04-084.
• Karpinski, Marek; Zelikovsky, Alexander (1998). "Approximating dense cases of covering problems". Proceedings of the DIMACS Workshop on Network Design: Connectivity and Facilities Location. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 40. American Mathematical Society. pp. 169–178.
• Khot, Subhash; Regev, Oded (2008). "Vertex cover might be hard to approximate to within 2−ε". Journal of Computer and System Sciences. 74 (3): 335–349. doi:10.1016/j.jcss.2007.06.019.
• O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race detection". ACM SIGPLAN Notices. 38 (10): 167–178. doi:10.1145/966049.781528.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998). Combinatorial Optimization: Algorithms and Complexity. Dover.
• Vazirani, Vijay V. (2003). Approximation Algorithms. Springer-Verlag. ISBN 978-3-662-04565-7.

बाहरी संबंध

• Weisstein, Eric W. "Vertex Cover". MathWorld.
• Weisstein, Eric W. "Minimum Vertex Cover". MathWorld.
• Weisstein, Eric W. "Vertex Cover Number". MathWorld.
• River Crossings (and Alcuin Numbers) – Numberphile