परिकल्पना-आर्क ग्राफ़ और हेल्ली गुण

इस पेपर में, हम परिकल्पना-आर्क ग्राफ़ के हेल्ली गुणों से संबंधित कुछ समस्याओं का अध्ययन करते हैं, जिन्हें एक निश्चित वृत्त के आर्क के इंटरसेक्शन ग्राफ़ के रूप में परिभाषित किया जाता है। इस प्रकार, परिकल्पना-आर्क ग्राफ़ सबसे सरल इंटरसेक्शन ग्राफ़ श्रेणियों में से हैं जिनके मॉडल हेल्ली गुण को संतुष्ट नहीं कर सकते हैं। विशेष रूप से, एक परिकल्पना-आर्क ग्राफ़ के कुछ क्लिक्स किसी कुछ लेकिन सभी आर्क इंटरसेक्शन मॉडल में हेल्ली हो सकते हैं। हमारा पहला परिणाम लिन और स्वार्कफ़िटर द्वारा एक प्रमेय का वैकल्पिक प्रमाण है, जो asserts करता है कि प्रत्येक परिकल्पना-आर्क ग्राफ़ G के लिए या तो G का प्रत्येक मानकीकृत मॉडल हेल्ली गुण को संतुष्ट करता है या G का कोई मानकीकृत मॉडल इस गुण को संतुष्ट नहीं करता है। इसके बाद, हम परिकल्पना-आर्क ग्राफ़ G के एकल क्लिक के हेल्ली गुणों का अध्ययन करते हैं। हम G के क्लिक्स को तीन प्रकारों में विभाजित करते हैं: G का एक क्लिक C हमेशा-हेल्ली/हमेशा-गैर-हेल्ली/अस्पष्ट होता है यदि C G के हर/कोई/(कुछ लेकिन नहीं सभी) मानकीकृत मॉडल में हेल्ली है। हम प्रत्येक प्रकार के क्लिक्स के लिए एक संयोजकीय वर्णन प्रदान करते हैं, और इसके आधार पर, हम एक बहुपद समय एल्गोरिदम तैयार करते हैं जो एक दिए गए क्लिक के प्रकार का निर्धारण करता है। अंत में, हम हेल्ली क्लिक्स समस्या का अध्ययन करते हैं, जिसमें हमें n-शिखर परिकल्पना-आर्क ग्राफ़ G और इसके कुछ क्लिक्स C₁, , Cₖ दिए जाते हैं और हम पूछते हैं कि क्या G का एक आर्क इंटरसेक्शन मॉडल है जिसमें सभी क्लिक्स C₁, , Cₖ हेल्ली गुण को संतुष्ट करते हैं। हम दिखाते हैं: (1) हेल्ली क्लिक्स समस्या 2^O (kk) n^O (1) समय एल्गोरिदम को स्वीकार करती है (यानी, यह इनपुट में दिए गए क्लिक्स की संख्या द्वारा पारामेट्राइज़ किए जाने पर FPT है), (2) एक्सपोनेंशियल टाइम हाइपोथेसिस (ETH) मानते हुए, हेल्ली क्लिक्स समस्या समय 2^o (k) n^O (1) में हल नहीं की जा सकती है, (3) हेल्ली क्लिक्स समस्या का आकार O (k⁶) का एक बहुपद कर्नेल है। हमारे सभी परिणाम एक डेटा संरचना, जिसे PQM-ट्री कहा जाता है, का उपयोग करते हैं, जो एक परिकल्पना-आर्क ग्राफ़ G के सभी मानकीकृत मॉडलों को बनाए रखता है।