💻 computer science

Breaking Symmetries from a Set-Covering Perspective

यह शोध पत्र ग्राफ में समरूपता भंग (symmetry breaking) को एक सेट-कवरिंग समस्या के रूप में औपचारिक रूप देता है, जो संबंधित कम्प्यूटेशनल चुनौतियों को संबोधित करने के लिए सेट-कवरिंग तकनीकों पर दशकों के शोध का लाभ उठाते हुए इष्टतम और उन्नत आंशिक समरूपता भंगों की व्युत्पत्ति को सक्षम बनाता है।

मूल लेखक: Michael Codish, Mikoláš Janota

प्रकाशित 2026-03-31

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Michael Codish, Mikoláš Janota

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

यहाँ "Breaking Symmetries from a Set-Covering Perspective" शोध पत्र का सरल भाषा और रचनात्मक उपमाओं के साथ अनुवाद दिया गया है।

मुख्य विचार: "सिमिट्री" (Symmetry) की समस्या

कल्पना कीजिए कि आप एक जासूस हैं जो हाथ से बने अद्वितीय जिग्सॉ पज़ल्स (jigsaw puzzles) के एक सेट से जुड़ी गुत्थी सुलझाने की कोशिश कर रहे हैं। हालाँकि, एक पेच है: आप किसी भी पज़ल को घुमा सकते हैं या पलट सकते हैं, और वह फिर भी वही पज़ल ही रहेगा।

यदि आप हर पज़ल के हर संभव संस्करण को सूचीबद्ध करने की कोशिश करेंगे, तो आप लाखों डुप्लिकेट्स (एक जैसे दिखने वाले) के ढेर में फंस जाएंगे। उदाहरण के लिए, 90 डिग्री घुमाया गया पज़ल टुकड़ों का तकनीकी रूप से एक अलग विन्यास (arrangement) है, लेकिन वह वही पज़ल है। इसे सिमिट्री (Symmetry) कहा जाता है।

कंप्यूटर विज्ञान में, जटिल समस्याओं (जैसे कि सबसे अच्छा नेटवर्क लेआउट खोजना या सर्किट डिजाइन करना) को हल करते나 समय, कंप्यूटर अटक जाते हैं क्योंकि वे इन लाखों "घुमाए गए" डुप्लिकेट्स की जाँच करने में समय बर्बाद करते हैं। उन्हें यह कहने का एक तरीका चाहिए: "रुकिए! हमें इस पज़ल के केवल एक संस्करण की जाँच करने की आवश्यकता है। बाकी सभी को अनदेखा करें।" इसे ब्रेकिंग सिमिट्री (Breaking Symmetry) कहा जाता है।

पुराना तरीका: "ब्रूट फोर्स" (Brute Force) दृष्टिकोण

पारंपरिक रूप से, कंप्यूटर को डुप्लिकेट्स की जाँच करने से रोकने के लिए, प्रोग्रामर नियमों की एक विशाल सूची जोड़ते हैं।

"इस संस्करण की जाँच न करें।"
"उस संस्करण की जाँच न करें।"
"उस संस्करण की जाँच न करें जहाँ लाल टुकड़ा बाईं ओर है।"

समस्या यह है कि जटिल पज़ल्स के लिए, यह नियमों की सूची अत्यधिक विशाल हो जाती है। यह दुनिया के हर व्यक्ति को कमरे में प्रवेश करने से रोकने के लिए हर एक व्यक्ति के लिए नियम लिखने जैसा है, बजाय इसके कि बस एक "बंद" (Closed) का साइन लगा दिया जाए। नियमों की किताब के विशाल आकार के कारण कंप्यूटर अभिभूत (overwhelmed) हो जाता है।

नया विचार: "सेट-कवर" (Set-Cover) परिप्रेक्ष्य

इस शोध पत्र के लेखक, माइकल कोडिश और मिकोलाश जानोटा ने समस्या को अलग तरह से देखने का निर्णय लिया। हर पज़ल के लिए नियम लिखने के बजाय, उन्होंने पूछा: "हमें हर एक डुप्लिकेट को पकड़ने के लिए 'इंस्पेक्टर्स' (निरीक्षकों) की कितनी छोटी टीम की आवश्यकता है?"

यहाँ उनका रूपक (analogy) कैसे काम करता है:

ग्राफ का ब्रह्मांड (The Universe of Graphs): हर पज़ल के हर संभव संस्करण (हर ग्राफ) वाले एक विशाल पुस्तकालय की कल्पना करें।
इंस्पेक्टर्स (परम्यूटेशन्स - Permutations): एक "इंस्पेक्टर" एक विशिष्ट नियम (एक गणितीय शफल) है जो कहता है, "यदि आप एक पज़ल देखते हैं जो ऐसा दिखता है, तो यह उसका एक डुप्लिकेट है।"
- यदि एक इंस्पेक्टर एक पज़ल पाता है और कहता है, "अरे, यह तो एक छोटे, सरल पज़ल का घुमाया हुआ संस्करण है," तो हम कहते हैं कि इंस्पेक्टर उस पज़ल को कवर (cover) करता है।
लक्ष्य (Set Cover): हम इंस्पेक्टर्स की सबसे छोटी संभव टीम चाहते हैं ताकि पुस्तकालय में मौजूद हर एक डुप्लिकेट पज़ल कम से कम एक इंस्पेक्टर द्वारा पकड़ा जा सके।
- यदि हमें 3 इंस्पेक्टर्स की एक ऐसी टीम मिलती है जो सभी डुप्लिकेट्स को पकड़ लेती है, तो हमें अन्य 10,000 इंस्पेक्टर्स की आवश्यकता नहीं है। हम उन्हें निकाल सकते हैं!

गुप्त हथियार: उन्होंने इस विशाल समस्या को कैसे नियंत्रित किया

चुनौती यह है कि पुस्तकालय बहुत बड़ा है (अरबों पज़ल्स) और संभावित इंस्पेक्टर्स लाखों में हैं। आप उन्हें एक-एक करके चेक नहीं कर सकते। लेखकों ने इस समस्या को प्रबंधनीय आकार में छोटा करने के लिए तीन चतुर तरकीबें इस्तेमाल कीं:

1. "लेजी इंस्पेक्टर" (Lazy Inspector) की तरकीब (Dominance)

कल्पना कीजिए कि आपके पास दो इंस्पेक्टर हैं:

इंस्पेक्टर A 100 विशिष्ट डुप्लिकेट्स को पकड़ता है।
इंस्पेक्टर B उन्हीं 100 डुप्लिकेट्स को पकड़ता है साथ ही 50 और अधिक को भी।
तरकीब: इंस्पेक्टर A को क्यों रखें? इंस्पेक्टर B वह सब कुछ करता है जो A करता है, और उससे भी अधिक। हम इंस्पेक्टर A को तुरंत हटा सकते हैं। इसे परम्यूटेशन डोमिनेंस (Permutation Dominance) कहा जाता है। यह एक जूनियर कर्मचारी को निकालने जैसा है क्योंकि सीनियर कर्मचारी पहले से ही उसके पूरे जॉब डिस्क्रिप्शन को कवर कर रहा है।

2. "ईज़ी टारगेट" (Easy Target) की तरकीब (Graph Dominance)

कल्पना कीजिए कि आपके पास एक बहुत कठिन पज़ल (ग्राफ X) है जिसे पकड़ना मुश्किल है, और एक बहुत आसान पज़ल (ग्राफ Y) है जिसे पकड़ना आसान है।

यदि वे इंस्पेक्टर जो कठिन पज़ल (X) को पकड़ते हैं, वे स्वचालित रूप से आसान पज़ल (Y) को भी पकड़ लेते हैं, तो हमें अब Y की चिंता करने की आवश्यकता नहीं है। हमें केवल कठिन वाले पज़ल्स पर ध्यान केंद्रित करने की आवश्यकता है।
यह ग्राफ डोमिनेंस (Graph Dominance) है। यह कंप्यूटर को "आसान" डुप्लिकेट्स को अनदेखा करने और अपनी ऊर्जा "ट्रिकी" (कठिन) वाले पज़ल्स पर लगाने की अनुमति देता है।

3. "वन-ऑफ-अ-काइंड" (One-of-a-Kind) की तरकीब (Backbones)

कभी-कभी, एक बहुत ही अजीब, विशिष्ट पज़ल होता है जिसे केवल एक अकेला इंस्पेक्टर ही पकड़ सकता है। कोई दूसरा उसे नहीं पहचान सकता।

वह इंस्पेक्टर एक बैकबोन (Backbone) है। वे अनिवार्य हैं। आपको उन्हें नियुक्त करना ही होगा, अन्यथा वह एक अजीब पज़ल छूट जाएगा।
एक बार जब आप बैकबोन को नियुक्त कर लेते हैं, तो आप शेष सूची से उन सभी पज़ल्स को हटा सकते हैं जिन्हें वे पकड़ते हैं, क्योंकि अब वे व्यवस्थित हो चुके हैं। यह अक्सर शेष बचे हुए इंस्पेक्टर्स के बीच नए बैकबोन्स को प्रकट करता है।

परिणाम: असंभव को संभव बनाना

इन तरकीबों का उपयोग करके, लेखक आकार 10 तक के ग्राफों (जो इस क्षेत्र में बहुत बड़ा माना जाता है) के लिए "सेट कवर" समस्या को हल करने में सक्षम रहे।

पहले: उन्हें 10! (3.6 मिलियन) संभावित नियमों और अरबों पज़ल्स वाली समस्या से जूझना पड़ता था।
बाद में: "बैकबोन" और "डोमिनेंस" की तरकीबों का उपयोग करके, उन्होंने समस्या को केवल 199 नियमों की एक छोटी सूची में बदल दिया जो सभी डुप्लिकेट्स को पूरी तरह से कवर करती है।

यह क्यों महत्वपूर्ण है

यह शोध पत्र एक मास्टर की (master key) खोजने जैसा है। हर दरवाजे को व्यक्तिगत रूप से लॉक करने के बजाय (जिसमें बहुत समय लगता है), उन्होंने एक ऐसा तरीका खोजा जिससे वे कुछ विशिष्ट चाबियों की पहचान कर सकें जो हर दरवाजे को स्वचालित रूप से लॉक कर देती हैं।

कंप्यूटर वैज्ञानिकों के लिए: यह जटिल समस्याओं को हल करने के लिए सबसे कुशल "नियम पुस्तिकाएं" बनाने का एक तरीका प्रदान करता है, जिससे गणना के समय की भारी बचत होती है।
बाकियों के लिए: यह दिखाता है कि कैसे एक उलझी हुई समस्या को एक अलग नजरिए से देखने पर (इसे "नियम" बनाने के बजाय एक "कवरिंग" समस्या के रूप में देखना) एक असंभव कार्य को हल करने योग्य कार्य में बदला जा सकता है।

संक्षेप में: उन्होंने डुप्लिकेट पज़ल्स के एक अराजक पहाड़ को आवश्यक इंस्पेक्टर्स की एक सुव्यवस्थित, छोटी सूची में बदल दिया, जिससे यह सुनिश्चित हुआ कि कंप्यूटर कभी भी एक ही चीज़ की दोबारा जाँच करने में समय बर्बाद न करे।

यहाँ माइकल कोडिश और मिकोलाश जानोटा के शोध पत्र "Breaking Symmetries from a Set-Covering Perspective" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

ग्राफ खोज समस्याओं (जैसे, विशिष्ट संरचनात्मक गुणों वाले ग्राफ खोजना) को ग्राफ आइसोमोर्फिज्म (graph isomorphism) के कारण एक विशाल खोज स्थान (search space) का सामना करना पड़ता है। समाधान का कोई भी क्रमपरिवर्तन (permutation) एक आइसोमोर्फिक (सममित) समाधान ही देता है, जिससे खोज का दोहराव वाला प्रयास होता है।

लक्ष्य: खोज को प्रत्येक आइसोमोर्फिज्म क्लास के लिए केवल एक "कैनोनिकल" (canonical) ग्राफ तक सीमित करना।
मानक दृष्टिकोण: समस्या के सूत्रीकरण में सिमेट्री ब्रेकिंग बाधाओं (जैसे, LexLeader) को जोड़ा जाता है। एक पूर्ण सिमेट्री ब्रेक (complete symmetry break) यह सुनिश्चित करता है कि प्रत्येक क्लास के लिए ठीक एक कैनोनिकल ग्राफ पर विचार किया जाए।
चुनौती: मानक LexLeader बाधा के लिए सुपर-एक्सपोनेंशियल (super-exponential) संख्या में बाधाओं की आवश्यकता होती है (प्रत्येक क्रमपरिवर्तन $S_n$ के लिए एक)। जबकि कॉम्पैक्ट बाधा सेट मौजूद हैं, पूर्ण सिमेट्री ब्रेकिंग के लिए बाधाओं के इष्टतम (optimal) (न्यूनतम आकार के) सेट को खोजना एक कठिन खुला प्रश्न बना हुआ है, विशेष रूप से $n > 6$ के क्रम वाले ग्राफों के लिए।

2. कार्यप्रणाली: सेट-कवरिंग परिप्रेक्ष्य (Methodology: The Set-Covering Perspective)

लेखक सिमेट्री ब्रेकिंग को एक सेट-कवरिंग समस्या (Set-Covering Problem) के रूप में एक नए औपचारिक रूप में प्रस्तुत करते हैं।

मुख्य परिभाषाएँ

कवरिंग (Covering): एक क्रमपरिवर्तन $\pi$ एक ग्राफ $G$ को "कवर" करता है यदि $\pi$ को $G$ पर लागू करने से एक लेक्सिकोग्राफिक रूप से छोटा ग्राफ प्राप्त होता है ( $\pi(G) < G$ )।
कैनोनाइजिंग सेट (Canonizing Set): एक क्रमपरिवर्तनों का सेट $\Pi$ एक पूर्ण सिमेट्री ब्रेक है यदि और केवल यदि $\Pi$ द्वारा कवर किए गए ग्राफों का संघ (union) सभी गैर-कैनोनिकल ग्राफों को शामिल करता है।
इष्टतम सिमेट्री ब्रेक (Optimal Symmetry Break): समस्या को क्रमपरिवर्तनों के सबसे छोटे उपसमुच्चय $\Pi \subseteq S_n$ $Π \subseteq S_{n}$ को खोजने के रूप में पुनर्गठित किया गया है जो गैर-कैनोनिकल ग्राफों के ब्रह्मांड (universe) को कवर करता है। यह एक क्लासिक सेट-कवर (Set-Cover) समस्या है जहाँ:
- ब्रह्मांड ( $U$ ): क्रम $n$ के सभी गैर-कैनोनिकल ग्राफ (आकार $\approx 2^{n(n-1)/2}$ )।
- उपसमुच्चय ( $S$ ): प्रत्येक गैर-तत्काल (non-identity) क्रमपरिवर्तन द्वारा कवर किए गए ग्राफों का सेट (आकार $n!$ )।

मुख्य तकनीकी नवाचार (Key Technical Innovations)

ब्रह्मांड और उपसमुत्त्सों के अकल्पनीय आकार से निपटने के लिए, लेखक तीन मुख्य तंत्र पेश करते हैं:

A. पैटर्न प्रतिनिधित्व (संक्षिप्त एन्कोडिंग)
ग्राफों को स्पष्ट रूप से सूचीबद्ध करने के बजाय, लेखक एक क्रमपरिवर्तन द्वारा कवर किए गए ग्राफों के सेट को दर्शाने के लिए पैटर्न (patterns) का उपयोग करते हैं।

एक क्रमपरिवर्तन $\pi$ एक विशिष्ट इंडेक्स $i$ पर ग्राफ को छोटा बनाता है यदि लेक्सिकोग्राफिक तुलना उस स्थिति पर विफल हो जाती है।
इस स्थिति को एडजेसेंसी मैट्रिक्स वेरिएबल्स पर समीकरण बाधाओं के एक सेट के रूप में एनकोड किया जाता है।
मोस्ट जनरल यूनिफायर (Most General Unifier - MGU) का उपयोग करके, इन बाधाओं को एक "पैटर्न" (वेरिएबल्स का एक आंशिक असाइनमेंट) में संक्षिप्त किया जाता है।
$\pi$ द्वारा कवर किए गए ग्राफों का सेट इन पैटर्नों से मेल खाने वाले ग्राफों का विलगित संघ (disjoint union) है। यह लेखकों को प्रतीकात्मक रूप से घातांकीय (exponential) ग्राफ सेटों के बारे में तर्क करने की अनुमति देता है।

B. प्रतीकात्मक अनुकूलन (Pre-Matrix Construction)
विशाल सेट-कवर मैट्रिक्स बनाने से पहले, लेखक SAT सॉल्वर का उपयोग करके प्रतीकात्मक रूप से तीन अनुकूलन लागू करते हैं:

क्रमपरिवर्तन प्रभुत्व (Permutation Dominance): यदि $\pi_1$ द्वारा कवर किए गए ग्राफों का सेट $\pi_2$ द्वारा कवर किए गए ग्राफों का उपसमुच्चय है, तो $\pi_1$ अनावश्यक है और उसे हटा दिया जाता है।
ग्राफ प्रभुत्व (Graph Dominance): यदि ग्राफ $G_1$ उन क्रमपरिवर्तनों के एक उपसमुच्चय द्वारा कवर किया जाता है जो $G_2$ को कवर करते हैं, तो $G_2$ अनावश्यक है (यदि $G_1$ कवर किया गया है, तो $G_2$ भी संभवतः समान या कम क्रमपरिवर्तनों द्वारा कवर होगा)।
बैकबोन की पहचान (Backbone Identification): एक क्रमपरिवर्तन एक बैकबोन (backbone) है यदि वह एक विशिष्ट ग्राफ को कवर करने वाला एकमात्र क्रमपरिवर्तन है। इन्हें किसी भी इष्टतम समाधान में शामिल किया जाना चाहिए।
- एल्गोरिदम: लेखक मौजूदा बैकबोन्स या कैनोनिकल ग्राफों द्वारा पहले से कवर किए जा चुके ग्राफों के बड़े रेंज को छोड़ने के लिए "लीप" (leap) ह्यूरिस्टिक्स का उपयोग करते हुए बैकबोन्स की पहचान करने के लिए ग्राफों (या क्रमपरिवर्तनों) पर पुनरावृत्ति करते हैं।

C. मैट्रिक्स निर्माण और समाधान
प्रतीकात्मक छंटाई के बाद, शेष समस्या को एक मैट्रिक्स (पंक्तियाँ = क्रमपरिवर्तन, कॉलम = ग्राफ) के रूप में तैयार किया जाता है।

$n \le 9$ के लिए, अनुकूलन समस्या को एक खाली मैट्रिक्स में बदल देते हैं (सभी ग्राफ पहचाने गए बैकबोन्स द्वारा कवर किए जाते हैं)।
$n=10$ के लिए, घटाया गया मैट्रिक्स RoundingSat सॉल्वर का उपयोग करके एक ऑप्टिमाइज़ेशन पीउडो-बूलियन (Optimization Pseudo-Boolean - OPB) समस्या के रूप में हल करने के लिए पर्याप्त छोटा है (199 पंक्तियाँ $\times$ 197 कॉलम)।

3. मुख्य योगदान (Key Contributions)

औपचारिकीकरण (Formalization): सिमेट्री ब्रेकिंग को एक सेट-कवरिंग समस्या के रूप में स्थापित किया, जो ग्राफ थ्योरी को कॉम्बिनेटरियल ऑप्टिमाइज़ेशन से जोड़ता है।
पैटर्न-आधारित प्रतीकात्मक तर्क (Pattern-Based Symbolic Reasoning): संक्षिप्त पैटर्न का उपयोग करके घातांकीय ग्राफ सेटों को दर्शाने की विधि विकसित की, जिससे स्पष्ट सूची बनाए बिना प्रभुत्व और बैकबोन जाँचों को संभालना संभव हुआ।
इष्टतम समाधान (Optimal Solutions): क्रम $n \le 10$ $n \leq 10$ के लिए ग्राफों के लिए इष्टतम (न्यूनतम संख्या में लेक्स-बाधाओं वाले) पूर्ण सिमेट्री ब्रेक की गणना की।
- पिछले कार्य (जैसे, Codish et al., 2016) ने कॉम्पैक्ट सेट पाए, लेकिन अनिवार्य रूप से न्यूनतम नहीं।
- नया दृष्टिकोण सिद्ध करता है कि 2016 के सेट $n \le 10$ के लिए इष्टतम के 10% के भीतर थे।
आंशिक सिमेट्री ब्रेक (Partial Symmetry Breaks): यह प्रदर्शित किया कि बैकबोन क्रमपरिवर्तनों का सेट अकेले एक अत्यधिक प्रभावी आंशिक सिमेट्री ब्रेक प्रदान करता है।
- $n=10$ के लिए, केवल 131 बैकबोन क्रमपरिवर्तनों का उपयोग करने से (मानक दृष्टिकोण में 45 ट्रांसपोज़िशन के मुकाबले) रेडंडेंसी अनुपात को काफी कम कर दिया जाता है, जो कम बाधाओं के साथ अधिक सटीक आंशिक ब्रेक प्रदान करता है।

4. परिणाम (Results)

लेखकों ने क्रम 10 तक के ग्राफों के लिए सफलतापूर्वक इष्टतम सिमेट्री ब्रेक की गणना की।

क्रम ( $n$ )	इष्टतम आकार (Lex-Constraints)	पिछला सर्वश्रेष्ठ (2016)	हल करने का समय
4	3	3	4.6s
5	6	7	0.67s
6	13	13	103s
7	35	37	~2 min
8	121	135	~15 min
9	765	842	~4.8 hours
10	7,181	7,853	~613 hours (कुल)

दक्षता (Efficiency): $n < 10$ के लिए, समस्या को पूरी तरह से प्रतीकात्मक अनुकूलन के माध्यम से हल किया गया (कोई सामान्य सेट-कवर सॉल्वर की आवश्यकता नहीं थी)। $n=10$ के लिए, समस्या को सैद्धांतिक आकार $10! \times 2^{45}$ से घटाकर एक प्रबंधनीय $199 \times 197$ मैट्रिक्स में बदल दिया गया।
एन्कोडिंग आकार (Encoding Size): प्राप्त सिमेट्री ब्रेकिंग बाधाएं (नेगेटेड पैटर्न के माध्यम से एनकोड की गई) प्रत्यक्ष LexLeader एन्कोडिंग की तुलना में 3 ऑर्डर ऑफ मैग्नीट्यूड छोटी हैं।
सत्यापन (Verification): सभी समाधानों को गैर-आइसोमोर्फिक ग्राफों (OEIS अनुक्रम A000088) की सटीक संख्या सुनिश्चित करने के लिए मॉडल काउंटर GANAK का उपयोग करके सत्यापित किया गया था।

5. महत्व (Significance)

सैद्धांतिक प्रगति: इस कार्य ने सिमेट्री ब्रेकिंग बाधाओं के ह्यूरिस्टिक निर्माण से हटकर एक कठोर अनुकूलन ढांचे की ओर बदलाव किया है। यह सिद्ध करता है कि छोटे-से-मध्यम क्रम वाले ग्राफों के लिए न्यूनतम पूर्ण सिमेट्री ब्रेक खोजना संभव है।
व्यावहारिक प्रभाव: प्राप्त बाधाएं पिछले अत्याधुनिक तरीकों की तुलना में काफी अधिक कॉम्पैक्ट हैं, जो ग्राफ खोज समस्याओं पर SAT/SMT सॉल्वर और CP सॉल्वर के प्रदर्शन में भारी सुधार कर सकती हैं।
नए अवसर: समस्या को सेट-कवरिंग के रूप में फ्रेम करके, लेखकों ने दशकों के सटीक और अनुमानित सेट-कवर एल्गोरिदम (जैसे, ग्रीडी ह्यूरिस्टिक्स, LP रिलैक्सेशन) को सिमेट्री ब्रेकिंग पर लागू करने का द्वार खोल दिया है।
आंशिक ब्रेक: यह खोज कि "बैकबोन्स" एक शक्तिशाली आंशिक सिमेट्री ब्रेक बनाते हैं, बड़े पैमाने की समस्याओं के लिए एक नई रणनीति का सुझाव देती है जहाँ पूर्ण ब्रेक अकल्पनीय है: उच्च-परिशुद्धता आंशिक ब्रेक प्राप्त करने के लिए बैकबोन सेट की गणना करें।

संक्षेप में, यह शोध पत्र सेट-कवर सिद्धांत, पैटर्न-आधारित प्रतीकात्मक प्रतिनिधित्व और बैकबोन पहचान का लाभ उठाकर क्रम 10 तक के ग्राफों के लिए इष्टतम परिणाम प्राप्त करते हुए सिमेट्री ब्रेकिंग की जटिलता को सफलतापूर्वक नियंत्रित करता है।