2025-11-13T16:28:10.775883

A CSP approach to Graph Sandwich Problems

Bodirsky, Guzmán-Pro
The \emph{Sandwich Problem} (SP) for a graph class $\calC$ is the following computational problem. The input is a pair of graphs $(V,E_1)$ and $(V,E_2)$ where $E_1\subseteq E_2$, and the task is to decide whether there is an edge set $E$ where $E_1\subseteq E \subseteq E_2$ such that the graph $(V,E)$ belongs to $\calC$. In this paper we show that many SPs correspond to the constraint satisfaction problem (CSP) of an infinite $2$-edge-coloured graph $H$. We then notice that several known complexity results for SPs also follow from general complexity classifications of infinite-domain CSPs, suggesting a fruitful application of the theory of CSPs to complexity classifications of SPs. We strengthen this evidence by using basic tools from constraint satisfaction theory to propose new complexity results of the SP for several graph classes including line graphs of multigraphs, line graphs of bipartite multigraphs, $K_k$-free perfect graphs, and classes described by forbidding finitely many induced subgraphs, such as $\{I_4,P_4\}$-free graphs, settling an open problem of Alvarado, Dantas, and Rautenbach (2019). We also construct a graph sandwich problem which is in coNP, but neither in P nor coNP-complete (unless P = coNP).
academic

ग्राफ सैंडविच समस्याओं के लिए एक CSP दृष्टिकोण

मूल जानकारी

  • पेपर ID: 2510.09128
  • शीर्षक: ग्राफ सैंडविच समस्याओं के लिए एक CSP दृष्टिकोण
  • लेखक: Manuel Bodirsky, Santiago Guzmán-Pro (TU Dresden)
  • वर्गीकरण: cs.DM (असतत गणित), cs.CC (कम्प्यूटेशनल जटिलता), math.CO (संयोजन गणित)
  • प्रकाशन तिथि: 13 अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.09128

सारांश

ग्राफ सैंडविच समस्या (Graph Sandwich Problem, SP) ग्राफ सिद्धांत में एक महत्वपूर्ण कम्प्यूटेशनल समस्या है। ग्राफ वर्ग C\mathcal{C} के लिए, इसकी सैंडविच समस्या को इस प्रकार परिभाषित किया जाता है: दो ग्राफ (V,E1)(V,E_1) और (V,E2)(V,E_2) दिए गए हैं जहाँ E1⊆E2E_1 \subseteq E_2, यह निर्धारित करें कि क्या किनारों का एक समुच्चय EE मौजूद है जैसे कि E1⊆E⊆E2E_1 \subseteq E \subseteq E_2 और ग्राफ (V,E)(V,E) वर्ग C\mathcal{C} से संबंधित है। यह पेपर सिद्ध करता है कि कई सैंडविच समस्याएं अनंत 2-किनारे-रंगीन ग्राफ HH की बाधा संतुष्टि समस्याओं (CSP) के समतुल्य हैं, और CSP सिद्धांत का उपयोग करके कई ग्राफ वर्गों की सैंडविच समस्याओं के लिए नए जटिलता परिणाम प्रदान करता है, जिनमें बहु-ग्राफ के लाइन ग्राफ, द्विपक्षीय बहु-ग्राफ के लाइन ग्राफ, KkK_k-मुक्त पूर्ण ग्राफ आदि शामिल हैं, जो Alvarado et al. (2019) द्वारा प्रस्तुत की गई खुली समस्या को हल करता है।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या की महत्ता

  1. सैद्धांतिक महत्व: ग्राफ सैंडविच समस्या ग्राफ सिद्धांत में एक शास्त्रीय समस्या है, जिसे Golumbic et al. द्वारा 1995 में प्रस्तुत किया गया था, यह ग्राफ पहचान समस्याओं का एक प्राकृतिक सामान्यीकरण है
  2. कम्प्यूटेशनल जटिलता: सैंडविच समस्याएं कम से कम संबंधित ग्राफ पहचान समस्याओं जितनी कठिन हैं, इनकी जटिलता वर्गीकरण एल्गोरिथ्मिक ग्राफ सिद्धांत का एक महत्वपूर्ण विषय है
  3. खुली समस्याएं: पूर्ण ग्राफ की सैंडविच समस्या की जटिलता अभी भी निर्धारित नहीं है, इसे इस क्षेत्र की सबसे महत्वपूर्ण खुली समस्याओं में से एक माना जाता है

मौजूदा विधियों की सीमाएं

  1. एकीकृत ढांचे का अभाव: मौजूदा अनुसंधान मुख्य रूप से विशिष्ट ग्राफ वर्गों के लिए विशेष तकनीकों का उपयोग करता है, सामान्य विश्लेषण विधि का अभाव है
  2. जटिल प्रमाण: पारंपरिक कठोरता प्रमाण आमतौर पर जटिल पुनरुत्पादन निर्माण की आवश्यकता होती है
  3. सीमित सैद्धांतिक उपकरण: सैंडविच समस्याओं की जटिलता का विश्लेषण करने के लिए व्यवस्थित सैद्धांतिक उपकरणों की कमी है

अनुसंधान प्रेरणा

यह पेपर ग्राफ सैंडविच समस्याओं और बाधा संतुष्टि समस्याओं के बीच संबंध स्थापित करने का लक्ष्य रखता है, सैंडविच समस्याओं के लिए एक एकीकृत विश्लेषण ढांचा प्रदान करने के लिए CSP सिद्धांत के परिपक्व उपकरणों का उपयोग करता है।

मूल योगदान

  1. सैद्धांतिक ढांचे की स्थापना: सिद्ध करता है कि विशिष्ट शर्तों को पूरा करने वाले ग्राफ वर्गों की सैंडविच समस्याएं 2-किनारे-रंगीन ग्राफ के CSP के समतुल्य हैं
  2. नई जटिलता परिणाम: कई ग्राफ वर्गों के लिए नई जटिलता वर्गीकरण प्रदान करता है, जिनमें शामिल हैं:
    • लाइन ग्राफ के बहु-ग्राफ और द्विपक्षीय बहु-ग्राफ संस्करण
    • KkK_k-मुक्त पूर्ण ग्राफ
    • {I4,P4}\{I_4,P_4\}-मुक्त ग्राफ आदि
  3. खुली समस्या का समाधान: Alvarado et al. (2019) द्वारा प्रस्तुत {I4,P4}\{I_4,P_4\}-मुक्त ग्राफ की सैंडविच समस्या के बारे में खुली समस्या को हल करता है
  4. गैर-द्विभाजन परिणाम: coNP-intermediate ग्राफ सैंडविच समस्याओं का निर्माण करता है, जटिलता वर्गीकरण की गैर-तुच्छता को सिद्ध करता है

विधि विवरण

कार्य परिभाषा

ग्राफ सैंडविच समस्या (SP): ग्राफ वर्ग C\mathcal{C} और इनपुट (V,E1,E2)(V,E_1,E_2) दिए गए हैं जहाँ E1⊆E2E_1 \subseteq E_2, यह निर्धारित करें कि क्या EE मौजूद है जैसे कि E1⊆E⊆E2E_1 \subseteq E \subseteq E_2 और (V,E)∈C(V,E) \in \mathcal{C}।

समतुल्य व्यक्तिव्य: इनपुट त्रिगुण (V,E,N)(V,E,N) है, जहाँ EE अनिवार्य किनारे हैं, NN निषिद्ध किनारे हैं, यह निर्धारित करें कि क्या ग्राफ (V,E′)∈C(V,E') \in \mathcal{C} मौजूद है जैसे कि E⊆E′E \subseteq E' और E′∩N=∅E' \cap N = \emptyset।

मूल सैद्धांतिक ढांचा

2-किनारे-रंगीन ग्राफ और CSP

  • 2-किनारे-रंगीन ग्राफ: त्रिगुण (V,B,R)(V,B,R), जहाँ BB नीले किनारों का समुच्चय है, RR लाल किनारों का समुच्चय है, और B∩R=∅B \cap R = \emptyset
  • समरूपता: आसन्नता संबंध और रंग को संरक्षित करने वाली शीर्ष मानचित्रण
  • CSP(H)(H): सभी परिमित 2-किनारे-रंगीन ग्राफ जो HH में समरूप मानचित्रण कर सकते हैं, का वर्ग

मुख्य अभिलक्षण प्रमेय

प्रस्ताव 3: ग्राफ वर्ग C\mathcal{C} के लिए, निम्नलिखित समतुल्य हैं:

  1. C\mathcal{C} वंशानुगत है, संयुक्त एम्बेडिंग गुण रखता है और विभाजन विस्तार के तहत बंद है
  2. 2-किनारे-रंगीन ग्राफ (V,R,B)(V,R,B) मौजूद है जैसे कि CSP(V,R,B)=SP(C)(V,R,B) = \text{SP}(\mathcal{C})
  3. ग्राफ HH मौजूद है जैसे कि SP(C)=CSP(H∗)=injCSP(H∗)(\mathcal{C}) = \text{CSP}(H^*) = \text{injCSP}(H^*)

जहाँ H∗H^* पूर्ण 2-किनारे-रंगीन ग्राफ को दर्शाता है, नीले किनारे E(H)E(H) हैं, लाल किनारे N(H)N(H) हैं।

तकनीकी नवाचार

1. आदिम सकारात्मक निर्माण (Primitive Positive Constructions)

CSP के बीच पुनरुत्पादन संबंध स्थापित करने के लिए pp-निर्माण का उपयोग करता है, यह ग्राफ सिद्धांत में gadget पुनरुत्पादन के अनुरूप है।

2. सार्वभौमिक ग्राफ सिद्धांत

वंशानुगत ग्राफ वर्ग C\mathcal{C} के लिए, यदि सार्वभौमिक ग्राफ HH मौजूद है (अर्थात् Age(H)=C(H) = \mathcal{C}), तो SP(C)=CSP(H∗)(\mathcal{C}) = \text{CSP}(H^*)।

3. विभाजन विस्तार बंद होना

  • विस्तार: twins जोड़ना (समान पड़ोस वाले शीर्ष)
  • सह-विस्तार: co-twins जोड़ना (एक दूसरे को छोड़कर समान पड़ोस)
  • विभाजन विस्तार: शीर्ष विभाजन (I,C)(I,C) के अनुसार विस्तार या सह-विस्तार

प्रायोगिक सेटअप

सैद्धांतिक सत्यापन

यह पेपर मुख्य रूप से सैद्धांतिक कार्य है, निम्नलिखित तरीकों से विधि की प्रभावशीलता को सत्यापित करता है:

  1. ज्ञात परिणामों का पुनरुत्पादन: CSP विधि का उपयोग करके पहले से ज्ञात सैंडविच समस्या जटिलता परिणामों को फिर से सिद्ध करता है
  2. नए परिणामों की व्युत्पत्ति: CSP सिद्धांत उपकरणों का उपयोग करके नई जटिलता वर्गीकरण प्राप्त करता है
  3. कम्प्यूटेशनल सत्यापन: कुछ परिमित संरचनाओं की बहुरूपता कंप्यूटर प्रोग्राम द्वारा सत्यापित की जाती है

विश्लेषण उपकरण

  • Datalog प्रोग्राम: कुछ बहुपद समय में हल करने योग्य CSP को हल करता है
  • MMSNP पुनरुत्पादन: अनंत डोमेन CSP को परिमित डोमेन में पुनरुत्पादित करता है
  • बीजगणितीय विधि: बहुरूपता का उपयोग करके CSP जटिलता का विश्लेषण करता है

प्रायोगिक परिणाम

मुख्य जटिलता परिणाम

1. लाइन ग्राफ संबंधित

  • प्रमेय: बहु-ग्राफ के लाइन ग्राफ की सैंडविच समस्या NP-complete है
  • प्रमेय: द्विपक्षीय बहु-ग्राफ के लाइन ग्राफ की सैंडविच समस्या NP-complete है

2. निषिद्ध उप-ग्राफ वर्ग

  • परिणाम 18: k≥4k \geq 4 के लिए, {P4,Kk}\{P_4,K_k\}-मुक्त ग्राफ, {P4,Ik}\{P_4,I_k\}-मुक्त ग्राफ और KkK_k-मुक्त पूर्ण ग्राफ की सैंडविच समस्याएं सभी NP-complete हैं
  • प्रमेय 17: मान लीजिए FF गैर-पूर्ण बिंदु-निर्धारण ग्राफ का समुच्चय है और FF-मुक्त ग्राफ सभी पूर्ण हैं, तो k≥4k \geq 4 के लिए, (F∪{Kk})(F \cup \{K_k\})-मुक्त ग्राफ की सैंडविच समस्या NP-hard है

3. पथ निषेध

  • प्रमेय 20: n,k≥4n,k \geq 4 के लिए, {Pn,Kk}\{P_n,K_k\}-मुक्त ग्राफ की सैंडविच समस्या NP-complete है

एल्गोरिथ्मिक जटिलता वर्गीकरण

बहुपद समय में हल करने योग्य स्थितियां

  • विभाजित ग्राफ: 2-SAT पुनरुत्पादन के माध्यम से
  • थ्रेशोल्ड ग्राफ: पूर्ण सममित बहुरूपता का उपयोग करके
  • पूर्ण बहु-भाग ग्राफ: Datalog प्रोग्राम द्वारा हल

NP-complete स्थितियां

  • तुलनीय ग्राफ: यादृच्छिक आंशिक क्रम के CSP पुनरुत्पादन के माध्यम से
  • क्रमचय ग्राफ: betweenness समस्या पुनरुत्पादन के माध्यम से
  • सामान्यीकृत विभाजित ग्राफ: (p,q)(p,q)-विभाजित ग्राफ जब p+q>2p+q > 2

गैर-द्विभाजन परिणाम

प्रमेय 21: यदि P ≠\neq coNP, तो ग्राफ वर्ग C\mathcal{C} मौजूद है जैसे कि SP(C)(\mathcal{C}) coNP-intermediate है।

निर्माण Ladner प्रमेय के अनुकूलन पर आधारित है, जो सिद्ध करता है कि ग्राफ सैंडविच समस्याओं की जटिलता P बनाम NP द्विभाजन से परे है।

संबंधित कार्य

ग्राफ सैंडविच समस्या अनुसंधान

  • Golumbic et al. (1995): ग्राफ सैंडविच समस्याओं का पहला व्यवस्थित अध्ययन
  • बाद का कार्य: विशिष्ट ग्राफ वर्गों की जटिलता वर्गीकरण
  • खुली समस्या: पूर्ण ग्राफ सैंडविच समस्या जटिलता अनिर्धारित

बाधा संतुष्टि सिद्धांत

  • Schaefer प्रमेय: बूलियन डोमेन CSP का द्विभाजन
  • Hell-Nešetřil प्रमेय: ग्राफ समरूपता समस्या वर्गीकरण
  • परिमित डोमेन द्विभाजन: Bulatov और Zhuk के सफलता के परिणाम
  • अनंत डोमेन CSP: समय-संबंधी CSP आदि विशेष मामलों की वर्गीकरण

तकनीकी संबंध

यह पेपर पहली बार ग्राफ सैंडविच समस्याओं और अनंत डोमेन CSP के बीच व्यवस्थित संबंध स्थापित करता है, दोनों क्षेत्रों के अंतर्संबंध के लिए नया दृष्टिकोण प्रदान करता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. सैद्धांतिक एकीकरण: ग्राफ सैंडविच समस्याओं को CSP सिद्धांत का उपयोग करके व्यवस्थित रूप से विश्लेषण किया जा सकता है
  2. विधि प्रभावशीलता: CSP उपकरण जटिलता प्रमाणों को सरल करते हैं और नए परिणाम खोजते हैं
  3. जटिलता समृद्धि: सैंडविच समस्याएं P से coNP-intermediate तक की पूर्ण जटिलता स्पेक्ट्रम प्रदर्शित करती हैं

सीमाएं

  1. लागू क्षेत्र: केवल विशिष्ट शर्तों (वंशानुगत, JEP, विभाजन विस्तार बंद) को पूरा करने वाले ग्राफ वर्गों पर लागू होता है
  2. पूर्ण ग्राफ समस्या: सबसे महत्वपूर्ण खुली समस्या (पूर्ण ग्राफ सैंडविच समस्या) अभी भी अनसुलझी है
  3. निर्माणात्मकता: कुछ अस्तित्व परिणामों में प्रभावी निर्माण एल्गोरिथ्म की कमी है

भविष्य की दिशाएं

  1. ω-वर्गीकरण संरचनाएं: ω-वर्गीकरण ग्राफ वर्गों की सैंडविच समस्याओं का अध्ययन करता है
  2. पूर्ण ग्राफ समस्या: पूर्ण ग्राफ सैंडविच समस्या के समाधान की खोज करता है
  3. निर्णयशीलता: दिए गए निषिद्ध उप-ग्राफ समुच्चय के लिए जटिलता की निर्णयशीलता का अध्ययन करता है
  4. NP-intermediate: NP-intermediate ग्राफ सैंडविच समस्याओं की खोज करता है

गहन मूल्यांकन

लाभ

  1. सैद्धांतिक नवाचार: पहली बार ग्राफ सैंडविच समस्याओं और CSP सिद्धांत के बीच व्यवस्थित संबंध स्थापित करता है, एकीकृत विश्लेषण ढांचा प्रदान करता है
  2. विधि सुंदरता: pp-निर्माण जैसे CSP उपकरणों का उपयोग करके जटिलता प्रमाणों को बहुत सरल करता है
  3. परिणाम समृद्धि: कई खुली समस्याओं को हल करता है, बड़ी संख्या में नई जटिलता परिणाम प्रदान करता है
  4. तकनीकी गहराई: ग्राफ सिद्धांत, मॉडल सिद्धांत, कम्प्यूटेशनल जटिलता आदि कई क्षेत्रों के गहन सिद्धांत को जोड़ता है

कमियां

  1. लागू प्रतिबंध: ढांचा केवल विशिष्ट प्रकार के ग्राफ वर्गों पर लागू होता है, पूरी तरह से सार्वभौमिक नहीं है
  2. व्यावहारिकता: मुख्य रूप से सैद्धांतिक योगदान, वास्तविक एल्गोरिथ्मिक सुधार सीमित है
  3. पूर्ण ग्राफ: मुख्य खुली समस्या अभी भी अनसुलझी है

प्रभाव

  1. शैक्षणिक मूल्य: ग्राफ सैंडविच समस्या अनुसंधान के लिए नए सैद्धांतिक उपकरण और दृष्टिकोण प्रदान करता है
  2. अंतर्संबंध महत्व: ग्राफ सिद्धांत और CSP सिद्धांत के अंतर्संबंध को बढ़ावा देता है
  3. पद्धति योगदान: ग्राफ सिद्धांत जटिलता विश्लेषण में pp-निर्माण के अनुप्रयोग का प्रदर्शन महत्व रखता है

लागू परिदृश्य

यह विधि विशेष रूप से उपयुक्त है:

  1. अच्छे संरचनात्मक गुणों वाले वंशानुगत ग्राफ वर्गों के लिए
  2. सार्वभौमिक ग्राफ वाले ग्राफ वर्गों के लिए
  3. ग्राफ सिद्धांत समस्याओं की व्यवस्थित जटिलता विश्लेषण की आवश्यकता वाली समस्याओं के लिए

संदर्भ

पेपर 61 संबंधित संदर्भों का हवाला देता है, मुख्य रूप से शामिल हैं:

  • ग्राफ सैंडविच समस्याओं की नींव कार्य 38
  • CSP सिद्धांत के मूल परिणाम 20,59,60
  • अनंत डोमेन CSP की वर्गीकरण परिणाम 10,11,46
  • ग्राफ सिद्धांत में संरचनात्मक परिणाम 22,23,37,47

सारांश: यह पेपर ग्राफ सैंडविच समस्याओं और बाधा संतुष्टि समस्याओं के बीच गहन संबंध स्थापित करके, इस शास्त्रीय ग्राफ सिद्धांत समस्या के लिए एक पूरी तरह से नया सैद्धांतिक विश्लेषण ढांचा प्रदान करता है। हालांकि सभी सैंडविच समस्याओं को पूरी तरह से हल करने में अभी भी सीमाएं हैं, लेकिन इसके सैद्धांतिक योगदान और पद्धति नवाचार संबंधित अनुसंधान के लिए नए मार्ग खोलते हैं।