2025-11-10T03:13:00.108521

The Complexity of Contracting Bipartite Graphs into Small Cycles

Krithika, Sharma, Tale
For a positive integer $\ell \geq 3$, the $C_\ell$-Contractibility problem takes as input an undirected simple graph $G$ and determines whether $G$ can be transformed into a graph isomorphic to $C_\ell$ (the induced cycle on $\ell$ vertices) using only edge contractions. Brouwer and Veldman [JGT 1987] showed that $C_4$-Contractibility is NP-complete in general graphs. It is easy to verify that $C_3$-Contractibility is polynomial-time solvable. Dabrowski and Paulusma [IPL 2017] showed that $C_{\ell}$-Contractibility is \NP-complete\ on bipartite graphs for $\ell = 6$ and posed as open problems the status of the problem when $\ell$ is 4 or 5. In this paper, we show that both $C_5$-Contractibility and $C_4$-Contractibility are NP-complete on bipartite graphs.
academic

द्विपक्षीय ग्राफ़ को छोटे चक्रों में संकुचित करने की जटिलता

मूल जानकारी

  • पेपर ID: 2206.07358
  • शीर्षक: द्विपक्षीय ग्राफ़ को छोटे चक्रों में संकुचित करने की जटिलता
  • लेखक: R. Krithika, Roohani Sharma, Prafullkumar Tale
  • वर्गीकरण: cs.CC (कम्प्यूटेशनल जटिलता सिद्धांत)
  • प्रकाशन समय/सम्मेलन: 48वां अंतर्राष्ट्रीय कार्यशाला ग्राफ़-सैद्धांतिक अवधारणाएं कंप्यूटर विज्ञान में (WG2022)
  • पेपर लिंक: https://arxiv.org/abs/2206.07358

सारांश

धनात्मक पूर्णांक ℓ≥3\ell \geq 3 के लिए, CℓC_\ell-संकुचनीयता समस्या एक अनिर्देशित सरल ग्राफ़ GG को इनपुट के रूप में लेती है और यह निर्धारित करती है कि क्या किनारे संकुचन संचालन के माध्यम से GG को CℓC_\ell (ℓ\ell शीर्षों वाले प्रेरित चक्र) के समरूप ग्राफ़ में परिवर्तित किया जा सकता है। Brouwer और Veldman ने 1987 में साबित किया कि C4C_4-संकुचनीयता सामान्य ग्राफ़ पर NP-पूर्ण है। C3C_3-संकुचनीयता बहुपद समय में हल की जा सकती है। Dabrowski और Paulusma ने 2017 में साबित किया कि जब ℓ=6\ell = 6 हो, तो CℓC_\ell-संकुचनीयता द्विपक्षीय ग्राफ़ पर NP-पूर्ण है, और जब ℓ=4\ell = 4 या 55 हो तो समस्या की जटिलता के बारे में एक खुला प्रश्न प्रस्तुत किया। यह पेपर साबित करता है कि C5C_5-संकुचनीयता और C4C_4-संकुचनीयता दोनों द्विपक्षीय ग्राफ़ पर NP-पूर्ण हैं।

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

समस्या की पृष्ठभूमि

  1. ग्राफ़ संकुचन संचालन: किनारे संकुचन ग्राफ़ सिद्धांत में एक मौलिक संचालन है, जो एक किनारे के दोनों अंतबिंदुओं को हटाकर और नए शीर्ष को मूल अंतबिंदु के सभी पड़ोसियों से जोड़कर ग्राफ़ को सरल बनाता है। यह संचालन क्लस्टरिंग, संपीड़न, विरलीकरण और कंप्यूटर ग्राफ़िक्स में महत्वपूर्ण अनुप्रयोग है।
  2. चक्र संकुचन समस्या: CℓC_\ell-संकुचनीयता समस्या यह निर्धारित करने की मांग करती है कि क्या दिया गया ग्राफ़ किनारे संकुचन संचालन के माध्यम से ℓ\ell-चक्र में परिवर्तित किया जा सकता है। यह समस्या ग्राफ़ के "चक्रीयता" (cyclicity) पैरामीटर से निकटता से संबंधित है, जिसे ग्राफ़ द्वारा संकुचित किए जा सकने वाले सबसे बड़े चक्र की लंबाई के रूप में परिभाषित किया जाता है।
  3. जटिलता अनुसंधान की वर्तमान स्थिति:
    • C3C_3-संकुचनीयता: बहुपद समय में हल योग्य
    • C4C_4-संकुचनीयता: सामान्य ग्राफ़ पर NP-पूर्ण
    • CℓC_\ell-संकुचनीयता (ℓ≥5\ell \geq 5): सामान्य ग्राफ़ पर NP-पूर्ण
    • C6C_6-संकुचनीयता: द्विपक्षीय ग्राफ़ पर NP-पूर्ण

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

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

मुख्य योगदान

  1. मुख्य सैद्धांतिक परिणाम: साबित किया कि C5C_5-संकुचनीयता और C4C_4-संकुचनीयता दोनों द्विपक्षीय ग्राफ़ पर NP-पूर्ण हैं
  2. रचनात्मक प्रमाण: Positive NAE-SAT समस्या से बहुपद समय कमी के माध्यम से रचनात्मक प्रमाण दिया गया
  3. तकनीकी नवाचार:
    • C5C_5 समस्या के लिए, दो-चरणीय निर्माण विधि डिजाइन की गई: पहले गैर-द्विपक्षीय ग्राफ़ HH का निर्माण, फिर किनारे विभाजन के माध्यम से द्विपक्षीय ग्राफ़ GG प्राप्त करना
    • C4C_4 समस्या के लिए, द्विपक्षीय ग्राफ़ का सीधा निर्माण और इसकी समतुल्यता का प्रमाण
  4. विस्तारित परिणाम: साबित किया कि C4C_4-संकुचनीयता व्यास 2 के K4K_4-मुक्त ग्राफ़ पर भी NP-पूर्ण है

विधि विवरण

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

इनपुट: द्विपक्षीय ग्राफ़ G=(V,E)G = (V, E)आउटपुट: यह निर्धारित करना कि क्या किनारे संकुचन का एक क्रम मौजूद है जो GG को CℓC_\ell (ℓ∈{4,5}\ell \in \{4,5\}) में परिवर्तित करता है बाधा: केवल किनारे संकुचन संचालन का उपयोग किया जा सकता है, शीर्ष हटाए या किनारे जोड़े नहीं जा सकते

प्रमाण रणनीति

C5C_5-संकुचनीयता का प्रमाण

पहला चरण: गैर-द्विपक्षीय ग्राफ़ HH का निर्माण Positive NAE-SAT उदाहरण ψ\psi दिया गया (NN चर, MM खंड):

  1. आधार चक्र: 5 शीर्ष Vα={α0,α1,α2,α3,α4}V_\alpha = \{\alpha_0, \alpha_1, \alpha_2, \alpha_3, \alpha_4\} जोड़ें जो 5-चक्र बनाते हैं
  2. चर उपकरण: प्रत्येक चर XiX_i के लिए, 5-चक्र Ci=(x0i,x1i,x2i,x3i,x4i)C_i = (x_0^i, x_1^i, x_2^i, x_3^i, x_4^i) जोड़ें और इसे आधार चक्र से जोड़ें
  3. खंड उपकरण: प्रत्येक खंड CjC_j के लिए, शीर्ष cj,bjc_j, b_j जोड़ें और उपयुक्त रूप से किनारे जोड़ें
  4. एन्कोडिंग संबंध: किनारे x1icjx_1^i c_j और x2ibjx_2^i b_j के माध्यम से चर-खंड संबंध को एन्कोड करें

दूसरा चरण: द्विपक्षीय ग्राफ़ GG का निर्माणHH में विशिष्ट किनारे सेट को विभाजित करके द्विपक्षीय ग्राफ़ GG प्राप्त करें:

  • किनारे α0α4\alpha_0\alpha_4 को विभाजित करें
  • प्रत्येक ii के लिए, किनारे x0ix4i,x0iα1,x1iα2,x2iα3,x3iα4x_0^i x_4^i, x_0^i \alpha_1, x_1^i \alpha_2, x_2^i \alpha_3, x_3^i \alpha_4 को विभाजित करें
  • कुछ चर-खंड कनेक्शन किनारों को विभाजित करें

C4C_4-संकुचनीयता का प्रमाण

द्विपक्षीय ग्राफ़ GG का सीधा निर्माण:

  1. आधार संरचना: शीर्ष t,f∈Vt, f \in V और t′,f′∈V′t', f' \in V' जोड़ें, किनारे tt′,ff′tt', ff' जोड़ें
  2. चर उपकरण: प्रत्येक चर XiX_i के लिए, शीर्ष सेट जोड़ें और उपयुक्त कनेक्शन स्थापित करें
  3. खंड उपकरण: प्रत्येक खंड CjC_j के लिए, संबंधित शीर्ष और किनारे जोड़ें
  4. बाध्य संरचना: सहायक शीर्ष सेट DD और D′D' जोड़कर यह सुनिश्चित करें कि विशिष्ट शीर्ष जोड़े साक्षी संरचना में सही स्थिति में हों

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

  1. दो-चरणीय निर्माण विधि: C5C_5 समस्या के लिए, पहले गैर-द्विपक्षीय ग्राफ़ पर समतुल्यता स्थापित करें, फिर द्विपक्षीय ग्राफ़ में परिवर्तित करें, जिससे द्विपक्षीय ग्राफ़ पर सीधे निर्माण की जटिलता से बचा जा सके
  2. साक्षी संरचना विश्लेषण: "अच्छी साक्षी संरचना" (nice witness structure) की अवधारणा प्रस्तुत करें, C4C_4-साक्षी संरचना के गुणों का व्यवस्थित विश्लेषण करें
  3. कमी की सही्यता का प्रमाण:
    • निर्मित ग्राफ़ की द्विपक्षीयता का प्रमाण
    • मूल समस्या और निर्मित ग्राफ़ की समतुल्यता का प्रमाण
    • SAT समस्या के समाधान के साथ द्विपक्षीय संबंध स्थापित करें

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

यह पेपर शुद्ध सैद्धांतिक अनुसंधान है, जिसमें प्रायोगिक सत्यापन शामिल नहीं है। सभी परिणाम गणितीय प्रमाण के माध्यम से प्राप्त किए गए हैं।

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

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

प्रमेय 1: C5C_5-संकुचनीयता द्विपक्षीय ग्राफ़ पर NP-पूर्ण है प्रमेय 2: C4C_4-संकुचनीयता द्विपक्षीय ग्राफ़ पर NP-पूर्ण है प्रमेय 3: C4C_4-संकुचनीयता व्यास 2 के K4K_4-मुक्त ग्राफ़ पर NP-पूर्ण है

प्रमाण के मुख्य बिंदु

  1. NP समावेशन: दी गई साक्षी संरचना के साथ बहुपद समय में सत्यापन किया जा सकता है
  2. NP-कठोरता: ज्ञात NP-पूर्ण समस्या Positive NAE-SAT से बहुपद समय कमी के माध्यम से
  3. निर्माण जटिलता: सभी निर्माण बहुपद समय में पूरे किए जाते हैं

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

ऐतिहासिक विकास

  1. Brouwer & Veldman (1987): सामान्य ग्राफ़ पर C4C_4-संकुचनीयता की NP-पूर्णता साबित की
  2. Hammack (1999, 2002): समतल ग्राफ़ पर चक्र संकुचन समस्या का अध्ययन
  3. Dabrowski & Paulusma (2017): द्विपक्षीय ग्राफ़ पर C6C_6-संकुचनीयता की NP-पूर्णता साबित की

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

  1. पथ संकुचन समस्या: PℓP_\ell-संकुचनीयता कुछ ग्राफ़ वर्गों पर बहुपद समय में हल योग्य है
  2. सामान्य HH-संकुचन समस्या: विभिन्न ग्राफ़ वर्गों पर जटिलता विश्लेषण
  3. पैरामीटरकृत जटिलता: पैरामीटरकृत दृष्टिकोण से संकुचन समस्या का अध्ययन

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

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

  1. Dabrowski और Paulusma द्वारा प्रस्तुत खुली समस्या को पूरी तरह हल किया
  2. द्विपक्षीय ग्राफ़ पर छोटे चक्र संकुचन समस्या की संपूर्ण जटिलता तस्वीर स्थापित की
  3. ग्राफ़ संरचना प्रतिबंध की कम्प्यूटेशनल जटिलता पर प्रभाव प्रदर्शित किया

सीमाएं

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

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

  1. अन्य ग्राफ़ वर्ग: अन्य प्रतिबंधित ग्राफ़ वर्गों पर जटिलता का अध्ययन
  2. पैरामीटरकृत एल्गोरिथम: निश्चित पैरामीटर ट्रैक्टेबल एल्गोरिथम विकसित करें
  3. सन्निकटन एल्गोरिथम: गारंटीकृत सन्निकटन अनुपात के साथ एल्गोरिथम डिजाइन करें
  4. सबसे लंबा चक्र समस्या: ग्राफ़ की चक्रीयता पैरामीटर की गणना की जटिलता का अध्ययन

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

शक्तियां

  1. सैद्धांतिक पूर्णता: महत्वपूर्ण खुली समस्या को पूरी तरह हल किया, बहुत अधिक सैद्धांतिक मूल्य है
  2. तकनीकी नवाचार: दो-चरणीय निर्माण विधि और nice witness structure अवधारणा पद्धति संबंधी महत्व रखती है
  3. प्रमाण की कठोरता: सभी प्रमेय पूर्ण गणितीय प्रमाण के साथ हैं, तर्क स्पष्ट है
  4. लेखन गुणवत्ता: पेपर संरचना तार्किक है, अभिव्यक्ति स्पष्ट है, आरेख सहायक है

कमियां

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

प्रभाव

  1. शैक्षणिक योगदान: कम्प्यूटेशनल जटिलता सिद्धांत में महत्वपूर्ण रिक्त स्थान भरता है
  2. पद्धति मूल्य: प्रदान की गई तकनीकी विधि समान समस्याओं के अनुसंधान में उपयोग की जा सकती है
  3. अनुवर्ती अनुसंधान: संबंधित क्षेत्र के आगे के अनुसंधान के लिए आधार स्थापित करता है

लागू दृश्य

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

संदर्भ

पेपर 29 संबंधित संदर्भों का हवाला देता है, जिसमें शामिल हैं:

  • ग्राफ़ संकुचन समस्या का प्रारंभिक कार्य
  • कम्प्यूटेशनल जटिलता सिद्धांत की नींव
  • संबंधित NP-पूर्णता परिणाम
  • ग्राफ़ सिद्धांत की मूल बातें

मुख्य संदर्भों में Brouwer & Veldman (1987), Dabrowski & Paulusma (2017), Garey & Johnson (1979) जैसे शास्त्रीय कार्य शामिल हैं।