Graph sandwich problem
ग्राफ सिद्धांत और कंप्यूटर विज्ञान में, ग्राफ सैंडविच समस्या एक ऐसे ग्राफ को खोजने की समस्या है जो ग्राफ के एक विशेष परिवार से संबंधित है और दो अन्य ग्राफों के बीच "सैंडविच" है, जिनमें से एक सबग्राफ होना चाहिए और दूसरा वांछित ग्राफ का सुपरग्राफ होना चाहिए। ग्राफ सैंडविच समस्याएं परीक्षण की समस्या को सामान्यीकृत करती हैं कि क्या दिया गया ग्राफ ग्राफ के एक परिवार से संबंधित है, और उनके अनुप्रयोगों के कारण और मान्यता समस्याओं के प्राकृतिक सामान्यीकरण के रूप में ध्यान आकर्षित किया है। समस्या कथन अधिक सटीक रूप से, एक शीर्ष समुच्चय V, एक अनिवार्य किनारा समुच्चय E1, और एक बड़े किनारे समुच्चय E2 को देखते हुए, एक ग्राफ G = (V, E) को जोड़ी G1 = (V, E1), G2 = (V, E2) के लिए एक सैंडविच ग्राफ कहा जाता है यदि E1 = E2 है। प्रॉपर्टी Π के लिए ग्राफ सैंडविच समस्या को निम्नानुसार परिभाषित किया गया हैः प्रॉपर्टी के लिए ग्राफ सैंडविच समस्या Π: उदाहरण के लिएः वर्टेक्स सेट V और एज सेट E1-E2-V × V. प्रश्नः क्या कोई ग्राफ G = (V, E) ऐसा है कि E1-E2-E2 और G प्रॉपर्टी Π को संतुष्ट करता है? ग्राफ के एक वर्ग के लिए पहचान की समस्या (जो एक गुण Π को संतुष्ट करते हैं) विशेष ग्राफ सैंडविच समस्या के बराबर है जहां E1 = E2, यानी वैकल्पिक किनारा सेट खाली है। कम्प्यूटेशनल जटिलता ग्राफ सैंडविच समस्या एन. पी.-पूर्ण होती है जब Π एक कॉर्डल ग्राफ, तुलनात्मक ग्राफ, क्रमपरिवर्तन ग्राफ, कॉर्डल द्विदलीय ग्राफ, या श्रृंखला ग्राफ होने का गुण होता है। इसे विभाजित ग्राफ, सीमा ग्राफ और ग्राफ के लिए बहुपद समय में हल किया जा सकता है जिसमें प्रत्येक पांच शीर्षों में अधिकतम एक चार-अक्षतंतु प्रेरित पथ होता है। चार-वर्टेक्स ग्राफ एच. में से प्रत्येक के लिए एच-मुक्त ग्राफ सैंडविच समस्याओं के लिए जटिलता की स्थिति को भी तय किया गया है। ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं