वर्टेक्स कवर

उदाहरण ग्राफ़ जिसमें वर्टेक्स कवर होता है जिसमें 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 में सुधार नहीं किया जा सकता, यदि n, O(K) है।

चूँकि, प्लानर ग्राफ़ के लिए और अधिक सामान्यतः कुछ निश्चित ग्राफ़ को अवयस्क के रूप में छोड़कर ग्राफ़ के लिए, आकार 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