2025-11-25T13:28:17.606015

On Stable Cutsets in General and Minimum Degree Constrained Graphs

Vroon, Bodlaender
A stable cutset is a set of vertices $S$ of a connected graph, that is pairwise non-adjacent and when deleting $S$, the graph becomes disconnected. Determining the existence of a stable cutset in a graph is known to be NP-complete. In this paper, we introduce a new exact algorithm for Stable Cutset. By branching on graph configurations and using the $O^*(1.3645)$ algorithm for the (3,2)-Constraint Satisfaction Problem presented by Beigel and Eppstein, we achieve an improved running time of $O^*(1.2972^n)$. In addition, we investigate the Stable Cutset problem for graphs with a bound on the minimum degree $δ$. First, we show that if the minimum degree of a graph $G$ is at least $\frac{2}{3}(n-1)$, then $G$ does not contain a stable cutset. Furthermore, we provide a polynomial-time algorithm for graphs where $δ\geq \tfrac{1}{2}n$, and a similar kernelisation algorithm for graphs where $δ= \tfrac{1}{2}n - k$. Finally, we prove that Stable Cutset remains NP-complete for graphs with minimum degree $c$, where $c > 1$. We design an exact algorithm for this problem that runs in $O^*(λ^n)$ time, where $λ$ is the positive root of $x^{δ+ 2} - x^{δ+ 1} + 6$. This algorithm can also be applied to the \textsc{3-Colouring} problem with the same minimum degree constraint, leading to an improved exact algorithm as well.
academic

सामान्य और न्यूनतम डिग्री सीमित ग्राफ़ में स्थिर कटसेट पर

मूल जानकारी

  • पेपर ID: 2510.09432
  • शीर्षक: सामान्य और न्यूनतम डिग्री सीमित ग्राफ़ में स्थिर कटसेट पर
  • लेखक: Mats Vroon (Utrecht University), Hans L. Bodlaender (Utrecht University)
  • वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम), cs.CC (कम्प्यूटेशनल जटिलता), cs.DM (असतत गणित)
  • प्रकाशन समय: 25 अक्टूबर 10 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.09432

सारांश

स्थिर कटसेट (Stable Cutset) एक जुड़े हुए ग्राफ़ में एक शीर्ष समुच्चय S है, जहां कोई भी दो शीर्ष आसन्न नहीं हैं, और S को हटाने के बाद ग्राफ़ असंयुक्त हो जाता है। किसी ग्राफ़ में स्थिर कटसेट के अस्तित्व को निर्धारित करना NP-पूर्ण समस्या है। यह पेपर स्थिर कटसेट के लिए एक नया सटीक एल्गोरिदम प्रस्तुत करता है, जो ग्राफ़ कॉन्फ़िगरेशन पर शाखा करके और Beigel और Eppstein द्वारा प्रस्तावित O*(1.3645) समय जटिलता के (3,2)-बाध्य संतुष्टि समस्या एल्गोरिदम का उपयोग करके O*(1.2972^n) की सुधारी गई चलने का समय प्राप्त करता है।

इसके अलावा, पेपर न्यूनतम डिग्री δ सीमित ग्राफ़ पर स्थिर कटसेट समस्या का अध्ययन करता है। पहले यह साबित किया जाता है कि यदि ग्राफ़ G की न्यूनतम डिग्री कम से कम 2/3(n-1) है, तो G में कोई स्थिर कटसेट नहीं है। आगे δ≥n/2 के लिए बहुपद समय एल्गोरिदम, और δ=n/2-k के लिए समान कर्नलाइजेशन एल्गोरिदम प्रदान किए गए हैं। अंत में यह साबित किया गया है कि जब न्यूनतम डिग्री c>1 हो तो स्थिर कटसेट समस्या अभी भी NP-पूर्ण है, और O*(λ^n) समय का एक सटीक एल्गोरिदम डिज़ाइन किया गया है, जहां λ x^(δ+2)-x^(δ+1)-6 का सकारात्मक मूल है। यह एल्गोरिदम समान न्यूनतम डिग्री बाधा के साथ 3-रंगीकरण समस्या पर भी लागू किया जा सकता है।

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

समस्या परिभाषा और महत्व

स्थिर कटसेट समस्या ग्राफ़ सिद्धांत में एक मौलिक समस्या है। दिए गए जुड़े हुए ग्राफ़ G=(V,E) को देखते हुए, स्थिर कटसेट शीर्ष उपसमुच्चय S⊆V है, जो निम्नलिखित को संतुष्ट करता है:

  1. S में कोई भी दो शीर्ष आसन्न नहीं हैं (स्थिरता)
  2. S को हटाने के बाद ग्राफ़ असंयुक्त हो जाता है (कटसेट गुण)

यह समस्या पूर्ण ग्राफ़ सिद्धांत में महत्वपूर्ण अनुप्रयोग है। Tucker ने साबित किया कि ग्राफ़ G k-रंगीकरणीय है यदि और केवल यदि सभी Gi∪S k-रंगीकरणीय हैं, जहां Gi G\S के जुड़े घटक हैं, S कोई भी छिद्र शीर्ष नहीं रखने वाला स्थिर कटसेट है।

मौजूदा तरीकों की सीमाएं

  1. जटिलता: Chvátal ने पहली बार साबित किया कि स्थिर कटसेट समस्या NP-पूर्ण है
  2. एल्गोरिदम दक्षता: मौजूदा सर्वश्रेष्ठ सटीक एल्गोरिदम Rauch आदि द्वारा प्रस्तावित है, जिसकी समय जटिलता O*(3^(n/3)) है
  3. विशेष ग्राफ़ वर्गों का अध्ययन अपर्याप्त: न्यूनतम डिग्री सीमित ग्राफ़ पर अनुसंधान अपेक्षाकृत कम है

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

  1. सामान्य ग्राफ़ पर स्थिर कटसेट समस्या के सटीक एल्गोरिदम में सुधार
  2. न्यूनतम डिग्री बाधा की समस्या जटिलता पर प्रभाव का गहन अध्ययन
  3. स्थिर कटसेट और अन्य समस्याओं (जैसे 3-रंगीकरण) के बीच संबंध स्थापित करना

मुख्य योगदान

  1. सुधारा गया सटीक एल्गोरिदम: O*(1.2972^n) समय जटिलता का एक नया एल्गोरिदम प्रस्तुत किया, जो पिछले O*(3^(n/3)) परिणाम में महत्वपूर्ण सुधार है
  2. न्यूनतम डिग्री सैद्धांतिक सीमाएं: साबित किया कि न्यूनतम डिग्री 2/3(n-1) से अधिक के ग्राफ़ में कोई स्थिर कटसेट नहीं है
  3. बहुपद समय एल्गोरिदम: δ≥n/2 वाले ग्राफ़ के लिए बहुपद समय एल्गोरिदम प्रदान किया
  4. कर्नलाइजेशन एल्गोरिदम: δ=n/2-k वाले ग्राफ़ के लिए O(k) कर्नल आकार वाला कर्नलाइजेशन एल्गोरिदम प्रदान किया
  5. NP-पूर्णता परिणाम: साबित किया कि न्यूनतम डिग्री c>1 होने पर समस्या अभी भी NP-पूर्ण है
  6. न्यूनतम डिग्री बाधित सटीक एल्गोरिदम: O*(λ^n) समय एल्गोरिदम प्रस्तुत किया, जहां λ एक विशिष्ट बहुपद का सकारात्मक मूल है
  7. 3-रंगीकरण समस्या का अनुप्रयोग: एल्गोरिदम को 3-रंगीकरण समस्या तक विस्तारित किया, सुधारे गए परिणाम प्राप्त किए

विधि विवरण

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

इनपुट: जुड़ा हुआ ग्राफ़ G=(V,E) आउटपुट: यह निर्धारित करना कि क्या G में स्थिर कटसेट है बाधाएं: स्थिर कटसेट S को स्थिरता और कटसेट गुण को संतुष्ट करना चाहिए

एनोटेटेड ग्राफ़ मॉडल

पेपर स्थिर कटसेट समस्या को एनोटेटेड ग्राफ़ समस्या के रूप में मॉडल करता है, जहां प्रत्येक शीर्ष को तीन संभावित लेबल में से एक दिया जाता है:

  • A: पहला जुड़ा घटक
  • B: दूसरा जुड़ा घटक
  • S: स्थिर कटसेट

एनोटेशन फ़ंक्शन p: V → P(L) प्रत्येक शीर्ष के संभावित लेबल समुच्चय को रिकॉर्ड करता है।

मुख्य एल्गोरिदम आर्किटेक्चर

1. (3,2)-CSP में रूपांतरण

पेपर दिखाता है कि स्थिर कटसेट उदाहरण को (3,2)-बाध्य संतुष्टि समस्या में कैसे रूपांतरित किया जाए:

  • प्रत्येक शीर्ष एक चर के अनुरूप है
  • चर डोमेन शीर्ष के संभावित लेबल समुच्चय है
  • किनारे की बाधाएं आसन्न शीर्षों के कुछ लेबल संयोजनों को प्रतिबंधित करती हैं

2. शाखा रणनीति

एल्गोरिदम दो मुख्य शाखा रणनीतियों का उपयोग करता है:

शाखा नियम 1: जब शीर्ष v त्रिभुज T में हो और |N(v)∩(W\T)|≥2 हो

  • शाखा 1: p(v)={A}, N(v)∩W पर लेम्मा 1 लागू करें
  • शाखा 2: p(v)={B}, N(v)∩W पर लेम्मा 1 लागू करें
  • शाखा 3: p(v)={S}, N(v)∩W पर लेम्मा 1 लागू करें

शाखा नियम 2: जब शाखा नियम 1 लागू न हो

  • शाखा 1: T में सभी शीर्षों के लिए p(v)={A,S} सेट करें
  • शाखा 2: T में सभी शीर्षों के लिए p(v)={B,S} सेट करें

3. बुद्धिमान शीर्ष समुच्चय निर्माण

सबसे धीमी शीर्ष समुच्चय कॉन्फ़िगरेशन से बचने के लिए, पेपर "तेज़" शीर्ष समुच्चय बनाने के लिए बहुपद समय एल्गोरिदम प्रस्तावित करता है:

  • अधिकतम त्रिभुज परिवार का लालची निर्माण
  • जटिल केस विश्लेषण के माध्यम से धीमी कॉन्फ़िगरेशन से बचना
  • अपरिवर्तनीय बनाए रखना: प्रत्येक शीर्ष किसी त्रिभुज से संबंधित है

तकनीकी नवाचार बिंदु

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

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

सैद्धांतिक विश्लेषण विधि

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

  1. शाखा कारक विश्लेषण: विभिन्न शाखा नियमों के सबसे खराब स्थिति शाखा कारक की गणना
  2. माप और विजय: न्यूनतम डिग्री बाधित एल्गोरिदम के लिए बुद्धिमान माप विश्लेषण का उपयोग
  3. केस विश्लेषण: बुद्धिमान शीर्ष समुच्चय निर्माण के लिए व्यापक केस विश्लेषण

जटिलता विश्लेषण

  • सामान्य ग्राफ़ एल्गोरिदम: सबसे खराब शीर्ष लागत 1.2972 का विश्लेषण
  • न्यूनतम डिग्री बाधित एल्गोरिदम: माप κ=w₂n₂+w₃n₃ का उपयोग करके विश्लेषण

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

मुख्य सैद्धांतिक परिणाम

1. सामान्य ग्राफ़ एल्गोरिदम

  • प्रमेय 13: O*(1.2972^n) समय का स्थिर कटसेट एल्गोरिदम मौजूद है
  • पिछले सर्वश्रेष्ठ परिणाम O*(3^(n/3))≈O*(1.4422^n) की तुलना में महत्वपूर्ण सुधार

2. न्यूनतम डिग्री सीमाएं

  • प्रमेय 14: न्यूनतम डिग्री δ>2/3(n-1) वाले ग्राफ़ में कोई स्थिर कटसेट नहीं है
  • यह सीमा कसी हुई है

3. बहुपद समय एल्गोरिदम

  • प्रमेय 20: δ≥n/2 होने पर बहुपद समय एल्गोरिदम मौजूद है
  • प्रमेय 23: δ=n/2-k होने पर O(k) कर्नल आकार वाला कर्नलाइजेशन एल्गोरिदम मौजूद है

4. NP-पूर्णता

  • प्रमेय 24: न्यूनतम डिग्री c>1 होने पर समस्या अभी भी NP-पूर्ण है

5. न्यूनतम डिग्री बाधित सटीक एल्गोरिदम

  • प्रमेय 26: δ≥3 होने पर O*(λ^n) एल्गोरिदम मौजूद है, जहां λ x^(δ+2)-x^(δ+1)-6 का सकारात्मक मूल है
  • δ≥11 होने पर सामान्य ग्राफ़ एल्गोरिदम से बेहतर

6. 3-रंगीकरण अनुप्रयोग

  • प्रमेय 27: समान जटिलता न्यूनतम डिग्री बाधित 3-रंगीकरण समस्या पर लागू होती है

विशिष्ट संख्यात्मक परिणाम

विभिन्न न्यूनतम डिग्री δ के लिए एल्गोरिदम जटिलता:

  • δ=3: λ≈1.7069
  • δ=15: λ≈1.2271
  • δ=25: λ≈1.1519
  • δ=50: λ≈1.0866
  • δ=100: λ≈1.0488

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

स्थिर कटसेट अनुसंधान

  1. जटिलता: Chvátal (1984) ने पहली बार NP-पूर्णता साबित की
  2. विशेष ग्राफ़ वर्ग: Brandstädt आदि ने K₄-मुक्त ग्राफ़ का अध्ययन किया, Le आदि ने claw-मुक्त ग्राफ़ का अध्ययन किया
  3. पैरामीटरीकृत जटिलता: Marx आदि ने समाधान आकार के अनुसार पैरामीटरीकृत FPT परिणाम साबित किए

संबंधित समस्याएं

  1. मिलान कटसेट: Kratsch और Le ने O*(1.4143^n) एल्गोरिदम प्रस्तावित किया, बाद में O*(1.3280^n) तक सुधारा गया
  2. 3-रंगीकरण: वर्तमान सबसे तेज़ एल्गोरिदम O*(1.3217^n) है

न्यूनतम डिग्री बाधित अनुसंधान

  • मिलान कटसेट समस्या पर पहले से न्यूनतम डिग्री बाधित अनुसंधान है
  • 3-रंगीकरण समस्या पर प्रभुत्व समुच्चय आधारित न्यूनतम डिग्री एल्गोरिदम है
  • यह पेपर स्थिर कटसेट के न्यूनतम डिग्री बाधा का पहली बार व्यवस्थित अध्ययन करता है

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

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

  1. सामान्य ग्राफ़ पर स्थिर कटसेट समस्या के सटीक एल्गोरिदम जटिलता में महत्वपूर्ण सुधार
  2. न्यूनतम डिग्री और स्थिर कटसेट अस्तित्व के बीच सैद्धांतिक संबंध स्थापित किया
  3. बहुपद समय से घातीय समय तक पूर्ण एल्गोरिदम स्पेक्ट्रम प्रदान किया
  4. 3-रंगीकरण समस्या के साथ प्रभावी संबंध स्थापित किया

सीमाएं

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

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

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

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

लाभ

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

कमियां

  1. प्रायोगिक अभाव: विशुद्ध सैद्धांतिक विश्लेषण, वास्तविक प्रदर्शन सत्यापन नहीं
  2. स्थिरांक कारक: वास्तविक एल्गोरिदम में काफी बड़े छिपे हुए स्थिरांक हो सकते हैं
  3. अनुप्रयोग परिदृश्य: वास्तविक अनुप्रयोग परिदृश्यों पर चर्चा पर्याप्त नहीं है
  4. अनुमानी विधियां: संभावित अनुमानी त्वरण तकनीकों की खोज नहीं की गई है

प्रभाव

  1. शैक्षणिक मूल्य: सटीक एल्गोरिदम और ग्राफ़ सिद्धांत क्षेत्र में महत्वपूर्ण सैद्धांतिक योगदान
  2. पद्धति विज्ञान: न्यूनतम डिग्री बाधित समस्याओं के अनुसंधान के लिए नई पद्धति प्रदान करता है
  3. पुनरुत्पादनीयता: एल्गोरिदम विवरण विस्तृत हैं, सैद्धांतिक परिणाम सत्यापन योग्य हैं
  4. विस्तारशीलता: तकनीकी विधियां अन्य ग्राफ़ समस्याओं तक सामान्यीकृत की जा सकती हैं

प्रयोज्य परिदृश्य

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

संदर्भ

पेपर 24 महत्वपूर्ण संदर्भों का हवाला देता है, जिनमें शामिल हैं:

  • Beigel & Eppstein (2005): (3,2)-CSP एल्गोरिदम
  • Chvátal (1984): स्थिर कटसेट NP-पूर्णता
  • Marx et al. (2013): पैरामीटरीकृत जटिलता परिणाम
  • Chen et al. (2021): न्यूनतम डिग्री बाधित मिलान कटसेट एल्गोरिदम
  • Meijer (2023): वर्तमान सबसे तेज़ 3-रंगीकरण एल्गोरिदम

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