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

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

परिभाषा

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

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

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

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

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

वहाँ एक फ़ंक्शन मौजूद है $f(n)\sim 2\log _{2}n$ इस तरह कि स्पर्शोन्मुख रूप से लगभग निश्चित रूप से, एक में सबसे बड़े गुट का आकार n-वर्टेक्स रैंडम ग्राफ या तो है $f(n)$ या $f(n)+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, प्लांटेड क्लिक समस्या को बहुपद समय में (उच्च संभावना के साथ) हल किया जा सकता है।

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

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

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

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

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

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

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

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

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

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

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