2025-11-25T10:28:17.626083

Smoothed analysis for graph isomorphism

Anastos, Kwan, Moore

There is no known polynomial-time algorithm for graph isomorphism testing, but elementary combinatorial "refinement" algorithms seem to be very efficient in practice. Some philosophical justification is provided by a classical theorem of Babai, ErdÅs and Selkow: an extremely simple polynomial-time combinatorial algorithm (variously known as "naÃ¯ve refinement", "naÃ¯ve vertex classification", "colour refinement" or the "1-dimensional Weisfeiler-Leman algorithm") yields a so-called canonical labelling scheme for "almost all graphs". More precisely, for a typical outcome of a random graph $G(n,1/2)$, this simple combinatorial algorithm assigns labels to vertices in a way that easily permits isomorphism-testing against any other graph. We improve the Babai-ErdÅs-Selkow theorem in two directions. First, we consider randomly perturbed graphs, in accordance with the smoothed analysis philosophy of Spielman and Teng: for any graph $G$, naÃ¯ve refinement becomes effective after a tiny random perturbation to $G$ (specifically, the addition and removal of $O(n\log n)$ random edges). Actually, with a twist on naÃ¯ve refinement, we show that $O(n)$ random additions and removals suffice. These results significantly improve on previous work of Gaudio-RÃ¡cz-Sridhar, and are in certain senses best-possible. Second, we complete a long line of research on canonical labelling of random graphs: for any $p$ (possibly depending on $n$), we prove that a random graph $G(n,p)$ can typically be canonically labelled in polynomial time. This is most interesting in the extremely sparse regime where $p$ has order of magnitude $c/n$; denser regimes were previously handled by BollobÃ¡s, Czajka-Pandurangan, and Linial-Mosheiff. Our proof also provides a description of the automorphism group of a typical outcome of $G(n,p_n)$ (slightly correcting a prediction of Linial-Mosheiff).

academic

ग्राफ समरूपता के लिए सुचारु विश्लेषण

मूल जानकारी

पेपर ID: 2410.06095
शीर्षक: ग्राफ समरूपता के लिए सुचारु विश्लेषण
लेखक: Michael Anastos, Matthew Kwan, Benjamin Moore
वर्गीकरण: math.CO cs.CC cs.DS
प्रकाशन समय: अक्टूबर 2024
पेपर लिंक: https://arxiv.org/abs/2410.06095v3

सारांश

ग्राफ समरूपता परीक्षण समस्या के लिए कोई ज्ञात बहुपद समय एल्गोरिदम नहीं है, लेकिन मौलिक संयोजनात्मक "परिशोधन" एल्गोरिदम व्यावहारिक रूप से अत्यंत कुशल हैं। Babai, Erdős और Selkow की शास्त्रीय प्रमेय इसके लिए दार्शनिक व्याख्या प्रदान करती है: एक अत्यंत सरल बहुपद समय संयोजनात्मक एल्गोरिदम (जिसे "भोली परिशोधन", "भोली शीर्ष वर्गीकरण", "रंग परिशोधन" या "1-आयामी Weisfeiler-Leman एल्गोरिदम" कहा जाता है) "लगभग सभी ग्राफ" के लिए विहित लेबलिंग योजना प्रदान करता है।

यह पेपर Babai-Erdős-Selkow प्रमेय को दो दिशाओं में सुधारता है: पहला, Spielman और Teng के सुचारु विश्लेषण विचार के अनुसार यादृच्छिक रूप से विक्षुब्ध ग्राफ पर विचार करना; दूसरा, यादृच्छिक ग्राफ विहित लेबलिंग पर दीर्घकालीन अनुसंधान को पूरा करना।

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

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

ग्राफ समरूपता समस्या का महत्व: ग्राफ समरूपता परीक्षण कम्प्यूटेशनल जटिलता सिद्धांत में एक मूल समस्या है, जो P और NP-complete के बीच विशेष स्थिति में है
व्यावहारिकता और सिद्धांत का अंतर: यद्यपि सबसे खराब स्थिति में घातीय समय की आवश्यकता होती है, रंग परिशोधन एल्गोरिदम व्यावहारिक रूप से उत्कृष्ट प्रदर्शन करता है
Babai-Erdős-Selkow प्रमेय की सीमाएं: यह शास्त्रीय प्रमेय केवल यादृच्छिक ग्राफ G(n,1/2) पर लागू होता है, संरचित ग्राफ पर खराब प्रदर्शन करता है

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

सुचारु विश्लेषण का अनुप्रयोग: Spielman-Teng के सुचारु विश्लेषण ढांचे को ग्राफ समरूपता समस्या पर लागू करना
प्रयोज्यता का विस्तार: साबित करना कि मामूली यादृच्छिक विक्षोभ रंग परिशोधन एल्गोरिदम को किसी भी ग्राफ के लिए प्रभावी बनाता है
सिद्धांत प्रणाली को पूर्ण करना: सभी घनत्वों के यादृच्छिक ग्राफ के लिए संपूर्ण विहित लेबलिंग सिद्धांत प्रदान करना

मुख्य योगदान

सुचारु विश्लेषण परिणाम: साबित किया कि किसी भी ग्राफ G₀ पर O(n log n) यादृच्छिक किनारों के विक्षोभ के बाद, रंग परिशोधन एल्गोरिदम लगभग हमेशा सफल होता है
सुधारी गई विक्षोभ सीमा: संशोधित एल्गोरिदम के माध्यम से, आवश्यक विक्षोभ को O(n) यादृच्छिक किनारों तक कम करना
विरल यादृच्छिक ग्राफ का संपूर्ण सिद्धांत: किसी भी घनत्व p के यादृच्छिक ग्राफ G(n,p) के लिए बहुपद समय विहित लेबलिंग योजना प्रदान करना
स्वसमरूपता समूह की विशेषता: विशिष्ट यादृच्छिक ग्राफ की स्वसमरूपता समूह संरचना का वर्णन, Linial-Mosheiff की भविष्यवाणी को सुधारना

विधि विवरण

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

दो n-शीर्ष ग्राफ G₁ और G₂ दिए गए हैं, ग्राफ समरूपता समस्या शीर्ष समुच्चय के बीच एक द्विभाजन के अस्तित्व को निर्धारित करने की मांग करती है जो दोनों ग्राफ के आसन्नता संबंध को संरक्षित करता है। विहित लेबलिंग प्रत्येक ग्राफ को एक मानक रूप निर्दिष्ट करने की एक विधि है, जिससे समरूप ग्राफ का समान लेबलिंग हो।

मुख्य एल्गोरिदम: रंग परिशोधन

मूल ढांचा

रंग परिशोधन एल्गोरिदम एक पुनरावृत्तिमूलक प्रक्रिया है:

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

गणितीय विवरण

ग्राफ G और रंग c : V(G) → Ω के लिए, परिशोधन संचालन को परिभाषित किया जाता है:

R_G c(v) = (c(v), (d_ω(v))_{ω∈Ω})

जहां d_ω(v) शीर्ष v के रंग ω वाले पड़ोसियों की संख्या है।

दृश्य और सार्वभौमिक आवरण

एल्गोरिदम की प्रभावशीलता "दृश्य" अवधारणा के माध्यम से विश्लेषण की जाती है:

दृश्य T_G(v) शीर्ष v से शुरू होने वाले सभी संभावित पथों को एन्कोड करता है
दो शीर्षों का रंग समान होता है यदि और केवल यदि उनके दृश्य समरूप हों

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

1. विस्तार और प्रतिसांद्रण तकनीकें

विस्तार गुण: यादृच्छिक ग्राफ के मजबूत विस्तार गुण का उपयोग करके, साबित करना कि छोटे शीर्ष समुच्चय तेजी से बढ़ते हैं
प्रतिसांद्रण असमानता: Erdős-Littlewood-Offord प्रकार की असमानताओं को लागू करके यादृच्छिक उतार-चढ़ाव को नियंत्रित करना

2. मुख्य संरचना विश्लेषण

k-कोर: ग्राफ का k-कोर अधिकतम न्यूनतम डिग्री कम से कम k वाला उप-ग्राफ है
2-कोर की विशेष गुण: 2-कोर में डिग्री कम से कम 3 वाले शीर्षों को आमतौर पर रंग परिशोधन द्वारा अलग किया जा सकता है

3. छिड़काव तकनीक (Sprinkling)

यादृच्छिक विक्षोभ को कई स्वतंत्र विरल विक्षोभों में विघटित करना:

प्रत्येक दौर विक्षोभ नए शीर्षों को अद्वितीय रंग प्रदान करता है
एकरसता का उपयोग करके ग्राफ के गुणों को क्रमिक रूप से सुधारना

4. विषमता ग्राफ (Disparity Graph)

रंग परिशोधन के प्रभाव को विश्लेषण करने के लिए विषमता ग्राफ D(G,c) को परिभाषित करना:

ग्राफ संरचना और रंग वर्गों के बीच असमानता को पकड़ना
छोटे जुड़े घटक प्रभावी विहित लेबलिंग के अनुरूप हैं

मुख्य प्रमेय

प्रमेय 1.2 (सुचारु विश्लेषण - मूल संस्करण)

स्थिरांक ε > 0 और p ≥ (1+ε)log n/n के लिए, किसी भी ग्राफ G₀ और यादृच्छिक ग्राफ G_rand ~ G(n,p) के लिए, लगभग हमेशा रंग परिशोधन एल्गोरिदम G₀△G_rand के सभी शीर्षों को अलग कर सकता है।

प्रमेय 1.3 (सुधारा गया सुचारु विश्लेषण)

ग्राफ वर्ग H और बहुपद समय विहित लेबलिंग एल्गोरिदम मौजूद हैं, जिससे कि p ≥ 100/n के लिए, किसी भी ग्राफ G₀ और G_rand ~ G(n,p) के लिए, लगभग हमेशा G₀△G_rand ∈ H।

प्रमेय 1.4 (विरल यादृच्छिक ग्राफ)

किसी भी अनुक्रम (p_n) के लिए, यादृच्छिक ग्राफ G_n ~ G(n,p_n) लगभग हमेशा बहुपद समय में विहित लेबल किया जा सकता है।

प्रमाण तकनीकें

महत्वपूर्ण लेम्मा 4.1

यह मुख्य तकनीकी परिणाम है, जो साबित करता है कि उपयुक्त यादृच्छिक विक्षोभ वाले ग्राफ में, जब S^{≤i}({u,v}) पर्याप्त बड़ा हो, तो शीर्ष u और v लगभग हमेशा रंग परिशोधन द्वारा अलग किए जाते हैं।

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

अन्वेषण प्रक्रिया: यादृच्छिक किनारों को क्रमिक रूप से प्रकट करना, दृश्य अंतर समुच्चय के विकास का अध्ययन करना
विस्तार लेम्मा: साबित करना कि छोटे अंतर समुच्चय घातीय रूप से बढ़ते हैं
प्रतिसांद्रण विश्लेषण: स्वतंत्र यादृच्छिक चर की प्रतिसांद्रण गुण का उपयोग करना

2-आयामी Weisfeiler-Leman एल्गोरिदम

अधिक सूक्ष्म विश्लेषण के लिए, 2-आयामी संस्करण का परिचय:

शीर्ष जोड़ी पर रंग लागू करना, न कि एकल शीर्ष पर
दूरी की जानकारी का पता लगा सकता है
अधिक मजबूत विभेदन क्षमता प्रदान करता है

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

सिद्धांत विश्लेषण मुख्य है

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

संभाव्य मॉडल: Erdős-Rényi यादृच्छिक ग्राफ मॉडल G(n,p) का उपयोग करना
स्पर्शोन्मुख विश्लेषण: n → ∞ समय के व्यवहार का अध्ययन करना
उच्च संभाव्यता घटनाएं: आवश्यक गुणों को 1-o(1) संभाव्यता के साथ साबित करना

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

रंग परिशोधन: O((n+m)log n) समय
2-आयामी एल्गोरिदम: O(n³log n) समय
समग्र एल्गोरिदम: बहुपद समय

मुख्य परिणाम

सुचारु विश्लेषण परिणाम

विक्षोभ सीमा: साबित किया कि p ≥ (1+ε)log n/n रंग परिशोधन को सफल बनाने के लिए सीमा है
इष्टतमता: यह सीमा किसी अर्थ में इष्टतम है
सुधारा गया एल्गोरिदम: 2-आयामी Weisfeiler-Leman एल्गोरिदम के माध्यम से सीमा को p ≥ 100/n तक कम करना

विरल यादृच्छिक ग्राफ परिणाम

संपूर्ण विशेषता: सभी घनत्व p के लिए विहित लेबलिंग योजना प्रदान करना
चरण परिवर्तन घटना: p ≈ 1/n के पास महत्वपूर्ण चरण परिवर्तन की खोज करना
स्वसमरूपता समूह: विरल यादृच्छिक ग्राफ की स्वसमरूपता समूह संरचना का संपूर्ण विवरण

तकनीकी योगदान

नई विश्लेषण उपकरण: यादृच्छिक विक्षुब्ध ग्राफ को विश्लेषण करने के लिए नई तकनीकें विकसित करना
एकीकृत ढांचा: विभिन्न घनत्व अंतरालों के परिणामों को एक ढांचे के तहत एकीकृत करना
सटीक स्थिरांक: कई परिणामों में सटीक स्थिरांक सीमाएं प्रदान करना

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

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

सैद्धांतिक व्याख्या: रंग परिशोधन एल्गोरिदम के व्यावहारिक प्रभाव के लिए सैद्धांतिक व्याख्या प्रदान करना
विक्षोभ की शक्ति: साबित करना कि मामूली यादृच्छिक विक्षोभ का विशाल प्रभाव होता है
संपूर्ण चित्र: यादृच्छिक ग्राफ समरूपता समस्या के लिए संपूर्ण सैद्धांतिक चित्र प्रदान करना

सीमाएं

विक्षोभ आवश्यकता: अभी भी एक निश्चित मात्रा में यादृच्छिक विक्षोभ की आवश्यकता है
स्थिरांक अनुकूलन: कुछ स्थिरांक इष्टतम नहीं हो सकते हैं
व्यावहारिक अनुप्रयोग: सैद्धांतिक परिणामों से व्यावहारिक एल्गोरिदम में रूपांतरण के लिए आगे के कार्य की आवश्यकता है

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

विक्षोभ मॉडल: अन्य प्रकार के यादृच्छिक विक्षोभ पर विचार करना
एल्गोरिदम सुधार: अधिक कुशल व्यावहारिक एल्गोरिदम विकसित करना
सामान्यीकृत अनुप्रयोग: तकनीकों को अन्य ग्राफ एल्गोरिदम समस्याओं पर लागू करना

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

शक्तियां

सैद्धांतिक गहराई: एक महत्वपूर्ण व्यावहारिक घटना की गहरी सैद्धांतिक अंतर्दृष्टि प्रदान करता है
तकनीकी नवाचार: कई नई विश्लेषण तकनीकें विकसित करता है, विशेष रूप से दृश्य विश्लेषण और छिड़काव विधि
पूर्णता: एक शास्त्रीय समस्या के लिए अपेक्षाकृत संपूर्ण सैद्धांतिक चित्र प्रदान करता है
सटीकता: कई परिणामों में सटीक सीमाएं और स्थिरांक प्रदान करता है

तकनीकी योगदान

पद्धति विज्ञान: असतत संरचना समस्याओं पर सुचारु विश्लेषण का सफल अनुप्रयोग
विश्लेषण उपकरण: विषमता ग्राफ, दृश्य, 2-आयामी Weisfeiler-Leman आदि अवधारणाओं का व्यवस्थित उपयोग
संभाव्य तकनीकें: विस्तार गुण और प्रतिसांद्रण असमानताओं का चतुर संयोजन

कमियां

जटिलता: प्रमाण तकनीकें काफी जटिल हैं, पठनीयता में सुधार की गुंजाइश है
व्यावहारिकता: सैद्धांतिक परिणामों से व्यावहारिक एल्गोरिदम में रूपांतरण पर्याप्त प्रत्यक्ष नहीं है
स्थिरांक अनुकूलन: कुछ तकनीकी स्थिरांकों में सुधार की गुंजाइश हो सकती है

प्रभाव मूल्यांकन

शैक्षणिक प्रभाव: ग्राफ समरूपता और यादृच्छिक ग्राफ सिद्धांत में महत्वपूर्ण योगदान
पद्धति प्रभाव: असतत गणित में सुचारु विश्लेषण के अनुप्रयोग का प्रदर्शन
व्यावहारिक संभावना: बेहतर ग्राफ समरूपता एल्गोरिदम विकास के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है

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

सैद्धांतिक अनुसंधान: ग्राफ समरूपता जटिलता, यादृच्छिक ग्राफ सिद्धांत अनुसंधान
एल्गोरिदम डिजाइन: नए ग्राफ समरूपता एल्गोरिदम डिजाइन को प्रेरित करता है
संबंधित समस्याएं: तकनीकें अन्य ग्राफ एल्गोरिदम समस्याओं पर लागू हो सकती हैं

तकनीकी विवरण पूरक

महत्वपूर्ण असमानताएं

पेपर में कई महत्वपूर्ण संभाव्य असमानताओं का उपयोग किया गया है:

सांद्रण विश्लेषण के लिए Chernoff सीमा
Erdős-Littlewood-Offord प्रकार की प्रतिसांद्रण असमानताएं
मोडल संभाव्यता का सटीक अनुमान

ग्राफ सिद्धांत संरचना

k-कोर के गुण और गणना
नग्न पथ और कोर संरचना
जुड़े घटकों का विकास प्रक्रिया

एल्गोरिदम जटिलता

विभिन्न एल्गोरिदम घटकों की समय जटिलता का विस्तृत विश्लेषण, समग्र बहुपद समय गुण को साबित करता है।

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