k-ट्री में एम्बेडिंग खोजने की जटिलता

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