प्लांटेड क्लिक

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

परिभाषा

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

प्लांटेड क्लिक समस्या को ग्राफ़ पर यादृच्छिक वितरण पर निर्णय समस्या के रूप में औपचारिक रूप दिया जा सकता है, जिसे दो संख्याओं, n (शीर्षों की संख्या), और k (क्लिक का आकार) द्वारा पैरामीटर किया जाता है। इन मापदंडों का उपयोग निम्नलिखित यादृच्छिक प्रक्रिया द्वारा ग्राफ़ उत्पन्न करने के लिए किया जा सकता है:

1. शीर्षों के प्रत्येक जोड़े के लिए स्वतंत्र रूप से चयन करके n शीर्षों पर एक एर्दो-रेनी यादृच्छिक ग्राफ़ बनाएं कि क्या प्रत्येक जोड़े के लिए प्रायिकता 1/2 के साथ उस जोड़े को जोड़ने वाला एक किनारा सम्मिलित किया जाए।
2. प्रायिकता 1/2 के साथ तय करें कि ग्राफ़ में एक क्लिक जोड़ना है या नहीं; यदि नहीं, तो चरण 1 में बनाया गया ग्राफ़ लौटाएँ।
3. यदि n शीर्ष है तो यादृच्छिक रूप से k का एक उपसमुच्चय चुनें और चयनित शीर्षों के प्रत्येक जोड़े के बीच एक किनारा (यदि कोई पहले से उपस्थित नहीं है) जोड़ें।

समस्या तब एल्गोरिदमिक रूप से यह निर्धारित करने की है कि क्या इस प्रक्रिया से उत्पन्न ग्राफ़ में से एक में कम से कम k शीर्षों का एक समूह है।

ऊपरी और निचली सीमाएं

वहाँ एक फ़ंक्शन $f(n)\sim 2\log _{2}n$ उपस्थित है जैसे कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, n-वर्टेक्स यादृच्छिक ग्राफ में सबसे बड़े क्लिक का आकार या तो $f(n)$ या $f(n)+1$+1 है, और कुछ स्थिरांक $c$ उपस्थित है जैसे कि आकार के क्लिक्स की अपेक्षित संख्या $\geq f(n)-c$ अनंत में परिवर्तित हो जाता है। परिणामस्वरूप, किसी को अपेक्षा करनी चाहिए कि $\sim 2\log _{2}n$ आकार के एक समूह के रोपण का उच्च संभावना के साथ पता नहीं लगाया जा सकता है।

केंद्रीय सीमा प्रमेय के अनुसार, यादृच्छिक ग्राफ की शीर्ष डिग्री को माध्य ${\frac {n}{2}}$ और मानक विचलन ${\frac {\sqrt {n}}{2}}$ के साथ एक मानक सामान्य वितरण के करीब वितरित किया जाता हैं। परिणामस्वरूप, जब $k$ ${\sqrt {n}}$ के क्रम पर होता है यह वितरण के आकार में एक पता लगाने योग्य परिवर्तन उत्पन्न करता हैं। अर्थात्, यदि आप शीर्ष डिग्री वितरण की योजना बनाते हैं, तो यह एक विकृत घंटी वक्र जैसा दिखेगा। इसलिए, पैरामीटर के लिए मानों की सबसे दिलचस्प श्रेणी k इन दो मानों के बीच है,

:$2\log _{2}n\ll k\ll {\sqrt {n}}.$

एल्गोरिदम

बड़े क्लिक

पैरामीटर k के पर्याप्त बड़े मानों के लिए, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) समाधान किया जा सकता है।

कुचेरा (1995) का मानना है कि, जब $k=\Omega ({\sqrt {n\log n}})$ होता है तो लगभग निश्चित रूप से लगाए गए समूह के सभी शीर्षों की डिग्री समूह के बाहर के सभी शीर्षों की तुलना में अधिक होती है, जिससे समूह को ढूंढना बहुत आसान हो जाता है। वह प्लांटेड क्लिक उदाहरण उत्पन्न करने के लिए यादृच्छिक प्रक्रिया में संशोधन का वर्णन करता है, जो कि k के बड़े मानों के लिए भी शीर्ष डिग्री को अधिक समान बनाता है, किन्तु दिखाता है कि इस संशोधन के अतिरिक्त लगाए गए क्लिक को अभी भी जल्दी से पाया जा सकता है।

एलोन, क्रिवेलेविच & सुदाकोव (1998) ने सिद्ध किया कि $k>10{\sqrt {n}}$ एक रोपित क्लिक को निम्नलिखित विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:

1. आसन्न मैट्रिक्स के आइजन्वेक्टर की गणना उसके दूसरे उच्चतम आइगेनवैल्यूज़ के अनुरूप करें।
2. उन k शीर्षों का चयन करें जिनके निर्देशांक इसआइजनवेक्टर में सबसे बड़े निरपेक्ष मान हैं।
3. शीर्षों का वह सेट लौटाएं जो चयनित शीर्षों के कम से कम 3/4 से सटे हों।

वे बताते हैं कि इस विधि को कैसे संशोधित किया जाए जिससे यह कभी भी काम करती रहे k कम से कम शीर्षों की संख्या के वर्गमूल के कुछ गुणज के समानुपाती होता है। अर्धनिश्चित प्रोग्रामिंग का उपयोग करके बड़े लगाए गए क्लिक्स भी पाए जा सकते हैं।

यादृच्छिक रूप से नमूनाकरण शीर्षों पर आधारित एक संयोजन विधि k पर समान सीमा प्राप्त कर सकती है और रैखिक समय में चलता है।

अर्धबहुपद समय

अर्ध-बहुपद समय में, k की पसंद की परवाह किए बिना, प्लांटेड क्लिक समस्या को हल करना भी संभव है।

क्योंकि यादृच्छिक ग्राफ़ में सबसे बड़े समूह का आकार सामान्यतः 2 log₂ n के निकट होता है, आकार का एक रोपा हुआ समूह k (यदि यह उपस्थित है) निम्न विधि द्वारा उच्च संभावना के साथ पाया जा सकता है:

1. $\min(k,3\log _{2}n)$ शीर्षों के सभी सेट S के माध्यम से लूप करें।
2. S की प्रत्येक पसंद के लिए, परीक्षण करें कि क्या S एक गुट है। यदि यह है, और $|S|=k$, तो S लौटाएँ। अन्यथा, उन शीर्षों का समुच्चय T ज्ञात करें जो S में सभी शीर्षों के निकट हैं। यदि $|T|\geq k$, तो T लौटाएँ।

इस एल्गोरिदम का चलने का समय अर्धबहुपद है, क्योंकि लूप ओवर करने के लिए S के अर्धबहुपद रूप से कई विकल्प हैं। इस पद्धति से सेट S को आज़माने की गारंटी है जो कि लगाए गए समूह का एक उपसमूह है; उच्च संभावना के साथ सेट T में केवल लगाए गए गुट के अन्य सदस्य सम्मिलित होंगे।

कठोरता धारणा के रूप में

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

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