2025-11-16T21:46:12.827225

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs

Grigoriev, Kobayashi, Tamaki et al.

We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithms due to Bouchitt{Ã©} and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices.

academic

त्रिसंयोजित समतलीय ग्राफ़ में सभी संभावित अधिकतम क्लिक उत्पन्न करने वाला बहुपद विलंब एल्गोरिदम

मूल जानकारी

पेपर ID: 2506.12635
शीर्षक: त्रिसंयोजित समतलीय ग्राफ़ में सभी संभावित अधिकतम क्लिक उत्पन्न करने वाला बहुपद विलंब एल्गोरिदम
लेखक: Alexander Grigoriev, Yasuaki Kobayashi, Hisao Tamaki, Tom C. van der Zanden
वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम)
प्रकाशन समय/सम्मेलन: IPEC 2025 (20वां अंतर्राष्ट्रीय पैरामीटरीकृत और सटीक संगणना संगोष्ठी)
पेपर लिंक: https://arxiv.org/abs/2506.12635

सारांश

यह पेपर त्रिसंयोजित समतलीय ग्राफ़ के संभावित अधिकतम क्लिक (Potential Maximal Cliques, PMC) समस्या के लिए एक नई विशेषता विधि विकसित करता है, और इस विशेषता के आधार पर दिए गए त्रिसंयोजित समतलीय ग्राफ़ के सभी संभावित अधिकतम क्लिक उत्पन्न करने के लिए एक बहुपद विलंब एल्गोरिदम प्रस्तावित करता है। Bouchitté और Todinca के गतिशील प्रोग्रामिंग एल्गोरिदम के साथ संयोजन में, यह एल्गोरिदम सामान्य समतलीय ग्राफ़ के लिए एक वृक्ष-चौड़ाई गणना एल्गोरिदम प्रदान करता है, जिसका चलन समय संभावित अधिकतम क्लिक की संख्या के संबंध में रैखिक है और शीर्षों की संख्या के संबंध में बहुपद है।

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

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

वृक्ष-चौड़ाई गणना की मूल समस्या: संभावित अधिकतम क्लिक (PMC) की गणना Bouchitté-Todinca वृक्ष-चौड़ाई एल्गोरिदम का पहला चरण है, जो दूसरे चरण में समय जटिलता |Π(G)|n^O(1) में ग्राफ़ G की वृक्ष-चौड़ाई की गणना करता है।
खुली समस्या: क्या Π(G) को समय |Π(G)|n^O(1) में गणना की जा सकती है, यह पैरामीटरीकृत और सटीक संगणना के क्षेत्र में एक महत्वपूर्ण खुली समस्या है। पहले इस समस्या को ज्ञात ग्राफ़ वर्गों को छोड़कर किसी भी प्राकृतिक ग्राफ़ वर्ग के लिए हल नहीं किया गया था।
समतलीयता की भूमिका: शाखा-चौड़ाई के लिए, समतलीयता की सहायता स्पष्ट है (Ratcatcher एल्गोरिदम), लेकिन वृक्ष-चौड़ाई के लिए, समतलीय ग्राफ़ की वृक्ष-चौड़ाई गणना NP-कठिन है या बहुपद समय में हल करने योग्य है, यह एक दीर्घकालीन खुली समस्या है।

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

Bouchitté और Todinca ने साबित किया कि Π(G) को न्यूनतम विभाजकों की संख्या के संबंध में बहुपद समय में गणना की जा सकती है
Fomin और Villanger ने O(1.7549^n) की ऊपरी सीमा और संबंधित एल्गोरिदम दिया
हालांकि सैद्धांतिक सीमाएं मौजूद हैं, व्यावहारिक अनुप्रयोगों में |Π(G)|n^O(1) समय के एल्गोरिदम अधिक व्यावहारिक हैं

मुख्य योगदान

नई PMC विशेषता: "steering" ग्राफ़ के आधार पर त्रिसंयोजित समतलीय ग्राफ़ PMC की एक सरल विशेषता विधि प्रस्तावित करता है
बहुपद विलंब एल्गोरिदम: त्रिसंयोजित समतलीय ग्राफ़ के लिए सभी PMC उत्पन्न करने वाला पहला बहुपद विलंब एल्गोरिदम डिजाइन करता है
latching ग्राफ़ का परिचय: latching ग्राफ़ की अवधारणा प्रस्तावित करता है जो त्रिसंयोजित समतलीय ग्राफ़ के साथ काम करने के लिए एक नया उपकरण है, जो पारंपरिक radial ग्राफ़ और noose विधि को प्रतिस्थापित करता है
वृक्ष-चौड़ाई एल्गोरिदम में सुधार: सामान्य समतलीय ग्राफ़ के लिए |Π(G)|n^O(1) चलन समय के साथ वृक्ष-चौड़ाई गणना एल्गोरिदम प्रदान करता है
समतलीयता का पहला स्पष्ट उपयोग: यह सटीक वृक्ष-चौड़ाई गणना के लिए गैर-तुच्छ तरीके से समतलीयता का स्पष्ट रूप से उपयोग करने वाला पहला एल्गोरिदम है

विधि विवरण

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

इनपुट: त्रिसंयोजित समतलीय ग्राफ़ G आउटपुट: G के सभी संभावित अधिकतम क्लिक Π(G) बाधा: एल्गोरिदम को बहुपद विलंब उत्पादन को संतुष्ट करना चाहिए, अर्थात दो क्रमागत आउटपुट के बीच का समय n^O(1) है

मूल अवधारणाएं

Latching ग्राफ़

द्विसंयोजित समतलीय ग्राफ़ G के लिए, इसका latching ग्राफ़ L_G G के प्रत्येक फलक में उस फलक की सीमा वलय के सभी जीवाओं को जोड़कर प्राप्त बहु-ग्राफ़ है।

मुख्य गुण:

त्रिसंयोजित समतलीय ग्राफ़ के लिए, latching ग्राफ़ एक सरल ग्राफ़ है (प्रस्ताव 6)
L_GX समतलीय ग्राफ़ है यदि और केवल यदि कोई फलक f मौजूद नहीं है जैसे कि |V(f)∩X|≥4 (प्रस्ताव 7)

Steering ग्राफ़ विशेषता

परिभाषा 13: ग्राफ़ H एक steering ग्राफ़ है, यदि शीर्ष समुच्चय का एक द्विविभाजन (S,P) मौजूद है जैसे कि:

HS एक वलय है
N_H(P) न तो खाली है और न ही HS का slot है
यदि |P|≥2, तो अतिरिक्त शर्तें संतुष्ट होती हैं (पथ संरचना, कनेक्शन सीमाएं आदि)

मुख्य प्रमेय (प्रमेय 21): त्रिसंयोजित समतलीय ग्राफ़ G का शीर्ष समुच्चय X एक PMC है यदि और केवल यदि L_GX एक steering ग्राफ़ है।

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

उत्पादन एल्गोरिदम संरचना

वर्गीकृत उत्पादन:
- सभी C∈C_G(X) को संतुष्ट करने वाले PMC X उत्पन्न करता है जहां |N_G(C)|=3 (ये K_4 के अनुरूप हैं)
- ऐसे PMC X उत्पन्न करता है जहां C∈C_G(X) मौजूद है जैसे कि |N_G(C)|≥4
न्यूनतम विभाजक के आधार पर उत्पादन:
- प्रत्येक न्यूनतम विभाजक S के लिए, संबंधित PMC उत्पन्न करता है
- steering ग्राफ़ बनाने के लिए arch की अवधारणा का उपयोग करता है
दोहराव से बचना: दोहराव उत्पादन समस्या को संभालने के लिए Bergougnoux आदि की तकनीक का उपयोग करता है (प्रमेय 27)

मुख्य एल्गोरिदम घटक

Arch अवधारणा (परिभाषा 18): न्यूनतम विभाजक S के लिए, arch P, V(G)\S का एक उपसमुच्चय है, जैसे कि:

L_GP एक पथ है
N_(P)∩S न तो खाली है और न ही L_GS का slot है

उत्पादन प्रक्रिया:

सभी न्यूनतम विभाजकों को उत्पन्न करता है (chordless वलय उत्पादन का उपयोग करके)
प्रत्येक विभाजक के लिए, संबंधित arch खोजता है
PMC बनाने के लिए chordless पथ उत्पादन एल्गोरिदम का उपयोग करता है
बहुपद विलंब सुनिश्चित करने के लिए दोहराव दमन तकनीक लागू करता है

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

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

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

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

समय जटिलता: |Π(G)|n^O(1)
विलंब जटिलता: n^O(1) (बहुपद विलंब)
स्पेस जटिलता: बहुपद स्पेस

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

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

सही्ता: steering ग्राफ़ विशेषता की आवश्यकता और पर्याप्तता को साबित करता है
पूर्णता: एल्गोरिदम सभी PMC उत्पन्न करता है और कोई दोहराव नहीं है
दक्षता: बहुपद विलंब आवश्यकता को संतुष्ट करता है

सामान्य समतलीय ग्राफ़ में विस्तार

प्रमेय 34: समतलीय ग्राफ़ G के लिए, समय |Π(G)|n^O(1) में tw(G) की गणना की जा सकती है।

प्रमाण द्विशीर्ष विभाजकों के विघटन के आधार पर प्रेरण का उपयोग करता है, लगभग क्लिक विभाजकों को संभालने के लिए Bodlaender-Koster प्रमेय का उपयोग करता है।

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

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

विशिष्ट ग्राफ़ वर्ग (त्रिसंयोजित समतलीय ग्राफ़) पर PMC की |Π(G)|n^O(1) समय गणना समस्या को पहली बार हल करता है
सटीक वृक्ष-चौड़ाई एल्गोरिदम के लिए समतलीयता का स्पष्ट उपयोग करने वाला पहला एल्गोरिदम प्रदान करता है
latching ग्राफ़ को त्रिसंयोजित समतलीय ग्राफ़ के साथ काम करने के लिए एक प्रभावी उपकरण के रूप में प्रस्तुत करता है

सीमाएं

ग्राफ़ वर्ग प्रतिबंध: विधि विशेष रूप से त्रिसंयोजित समतलीय ग्राफ़ के लिए है, सामान्य समतलीय ग्राफ़ में विस्तार के लिए अतिरिक्त तकनीकें आवश्यक हैं
latching ग्राफ़ सीमाएं: गैर-त्रिसंयोजित ग्राफ़ के लिए, latching ग्राफ़ सरल ग्राफ़ नहीं हो सकता है, जो विधि की प्रयोज्यता को सीमित करता है
सिद्धांत बनाम व्यवहार: हालांकि सैद्धांतिक रूप से सुंदर है, व्यावहारिक प्रदर्शन सत्यापन की प्रतीक्षा में है

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

सामान्य समतलीय ग्राफ़ में विस्तार: द्विशीर्ष न्यूनतम विभाजकों को पार करने वाले PMC को संभालने की विधि खोजना
अन्य सतहें: पर्यावरण और अन्य सतहों पर ग्राफ़ में विस्तार (लेखक ध्यान देते हैं कि latching ग्राफ़ विधि लागू नहीं है)
ऊपरी सीमा में सुधार: त्रिसंयोजित समतलीय ग्राफ़ के |Π(G)| के लिए कड़ी सीमाओं का अनुसंधान
व्यावहारिक एल्गोरिदम: व्यावहारिक कार्यान्वयन विकसित करना और प्रदर्शन मूल्यांकन करना

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

शक्तियां

सैद्धांतिक नवाचार: steering ग्राफ़ विशेषता सरल और सुंदर है, पारंपरिक noose और radial ग्राफ़ की जटिलता से बचती है
तकनीकी योगदान: latching ग्राफ़ अवधारणा त्रिसंयोजित समतलीय ग्राफ़ विश्लेषण के लिए एक नया उपकरण प्रदान करती है
समस्या समाधान: पहली बार प्राकृतिक ग्राफ़ वर्ग पर महत्वपूर्ण खुली समस्या को हल करता है
एल्गोरिदम डिजाइन: बहुपद विलंब उत्पादन तकनीक का अनुप्रयोग चतुर है, दोहराव आउटपुट समस्या को प्रभावी ढंग से संभालता है

कमियां

प्रयोज्यता सीमा: केवल त्रिसंयोजित समतलीय ग्राफ़ तक सीमित है, सामान्य समतलीय ग्राफ़ को अभी भी जटिल प्रेरक प्रक्रिया की आवश्यकता है
व्यावहारिकता अज्ञात: वास्तविक कार्यान्वयन और प्रदर्शन परीक्षण की कमी है
स्थिरांक कारक: बहुपद विलंब में स्थिरांक बड़े हो सकते हैं, व्यावहारिक दक्षता को प्रभावित करते हैं

प्रभाव

सैद्धांतिक महत्व: दीर्घकालीन खुली समस्या के लिए आंशिक समाधान प्रदान करता है, पैरामीटरीकृत एल्गोरिदम सिद्धांत को आगे बढ़ाता है
पद्धति योगदान: latching ग्राफ़ विधि अन्य समतलीय ग्राफ़ एल्गोरिदम को प्रेरित कर सकती है
व्यावहारिक संभावना: समतलीय ग्राफ़ वृक्ष-चौड़ाई गणना के लिए नई सैद्धांतिक नींव प्रदान करता है

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

विद्युत परिपथ डिजाइन में समतलीय ग्राफ़ विश्लेषण
भौगोलिक सूचना प्रणालियों में समतलीय नेटवर्क अनुकूलन
कम्प्यूटेशनल ज्यामिति में वृक्ष विघटन की आवश्यकता वाली समस्याएं
ग्राफ़ सिद्धांत अनुसंधान में सैद्धांतिक विश्लेषण उपकरण

संदर्भ

पेपर 22 महत्वपूर्ण संदर्भों का हवाला देता है, मुख्य रूप से:

Bouchitté & Todinca के PMC और वृक्ष-चौड़ाई मूल कार्य
समतलीय ग्राफ़ एल्गोरिदम के शास्त्रीय परिणाम (जैसे Seymour-Thomas का Ratcatcher एल्गोरिदम)
संयोजक गणना की बहुपद विलंब तकनीकें
ग्राफ़ की त्रिसंयोजितता और समतलीय एम्बेडिंग का मूल सिद्धांत

यह पेपर सैद्धांतिक कंप्यूटर विज्ञान के क्षेत्र में महत्वपूर्ण योगदान देता है। हालांकि इसकी प्रयोज्यता सीमित है, लेकिन इसकी विधि नवाचार और समस्या समाधान में महत्वपूर्ण शैक्षणिक मूल्य है, जो समतलीय ग्राफ़ एल्गोरिदम और पैरामीटरीकृत जटिलता सिद्धांत के विकास के लिए नई सोच और उपकरण प्रदान करता है।