💻 computer science

The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems

यह शोध पत्र यह सिद्ध करके कि कोई भी बीजगणितीय लंबाई 1 वाला बिना स्यूडो-लूप (pseudo-loop) का स्मूथ डाइग्राफ प्रत्येक परिमित संरचना का निर्माण कर सकता है, अनंत निर्देशित ग्राफ-रंगण (directed graph-colouring) समस्याओं के लिए प्रथम NP-कठिनता मानदंड स्थापित करता है, जिससे $\omega$ -कैटेगोरिकल सेटिंग में प्रमुख परिमित-डोमेन जटिलता परिणामों को सफलतापूर्वक उन्नत किया जा सका है।

मूल लेखक: Johanna Brunar, Marcin Kozik, Tomáš Nagy, Michael Pinsker

प्रकाशित 2026-04-07

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

CC BY 4.0

मूल लेखक: Johanna Brunar, Marcin Kozik, Tomáš Nagy, Michael Pinsker

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

यहाँ "The Sorrows of a Smooth Digraph" पेपर का सरल भाषा, उपमाओं और रूपकों का उपयोग करते हुए हिंदी अनुवाद दिया गया है।

बड़ी तस्वीर: "रंग भरने" का खेल

कल्पना कीजिए कि आपके पास एक विशाल, अनंत मानचित्र (एक ग्राफ) है जो शहरों (बिंदुओं) और एकतरफा सड़कों (तीरों) से बना है। आप हर शहर को एक विशिष्ट रंग से पेंट करना चाहते हैं। हालाँकि, यहाँ सख्त नियम हैं:

मानचित्र के नियम: यदि शहर A से शहर B तक एक सड़क है, तो A का रंग B के रंग के साथ "संगत" (compatible) होना चाहिए।
सूची के नियम (संरक्षण/Conservativity): प्रत्येक शहर के पास अनुमत रंगों की एक विशिष्ट खरीदारी सूची होती है। आप कोई भी रंग नहीं चुन सकते; आपको उस शहर की सूची में से ही एक चुनना होगा।

यह एक कन्स्ट्रेंट सेटिस्फैक्शन प्रॉब्लम (CSP) है। सवाल यह है: क्या यह पता लगाना आसान है कि क्या एक वैध रंग मौजूद है, या यह एक दुःस्वप्न (NP-hard) है?

छोटे, परिमित (finite) मानचित्रों के लिए, गणितज्ञों को लंबे समय से उत्तर पता है: यह या तो आसान है या कठिन, बीच का कोई रास्ता नहीं है। लेकिन क्या होता है जब मानचित्र अनंत (infinite) हो? यही वह रहस्य है जिसे यह पेपर हल करता है।

हमारी कहानी के पात्र

स्मूथ डाइग्राफ (The Smooth Digraph - मानचित्र):
इसे एक ऐसे शहर के रूप में सोचें जहाँ हर चौराहे पर कम से कम एक सड़क आ रही है और एक सड़क जा रही है। वहाँ कोई डेड एंड (sink) नहीं है और न ही कोई शुरुआती बिंदु है जहाँ से कोई ट्रैफिक न आता हो (source)। यह एक पूरी तरह से सुचारू रूप से बहने वाली ट्रैफिक व्यवस्था है।

उपमा: एक राउंडअबाउट (गोल चक्कर) जहाँ ट्रैफिक कभी नहीं रुकता।

ऑर्बिट्स (Orbits - पड़ोस/इलाके):
चूँकि मानचित्र अनंत है, हम हर एक शहर को व्यक्तिगत रूप से नहीं देख सकते। इसके बजाय, हम "पड़ोसों" (orbits) को देखते हैं। ये शहरों के वे समूह हैं जो मानचित्र के समरूपता समूह (symmetry group) के लिए बिल्कुल एक जैसे दिखते हैं। यदि आप ज़ूम आउट करते हैं, तो आप ऑर्बिट A के एक शहर को दूसरे से अलग नहीं पहचान सकते; वे एक-दूसरे के स्थान पर बदले जा जा सकते हैं।

उपमा: एक शहर में, सभी "डाउनटाउन" की गगनचुंबी इमारतें एक जैसी दिखती हैं। आपको विशिष्ट इमारत की परवाह नहीं है; आपको "डाउनटाउन" ज़ोन की परवाह है।

"स्यूडो-लूप" (Pseudo-Loop - शॉर्टकट कोड):
आमतौर पर, एक सड़क शहर A से शहर B तक जाती है। एक "लूप" A से वापस A तक जाने वाली सड़क है। एक स्यूडो-लूप वह सड़क है जो एक ही पड़ोस के अंदर रहती है।

रूपक: कल्पना कीजिए कि एक ऐसा पड़ोस जहाँ आप बिना पड़ोस छोड़े, उसी पड़ोस के भीतर एक घर से दूसरे घर तक जा सकते हैं। यह एक "स्यूडो-लूप" है।

मुख्य खोज: मानचित्र के "शोक" (The Sorrows)

लेखक इन अनंत मानचित्रों के लिए एक "डाइकोटॉमी" (दो अलग-अलग रास्तों में विभाजन) को सिद्ध करते हैं। यह सड़क के दोराहे जैसा है:

पथ 1: आसान तरीका (Tractable)
यदि मानचित्र में एक स्यूडो-लूप (एक पड़ोस के भीतर रहने वाली सड़क) है, तो रंग भरने की समस्या आसान है। आप इसे जल्दी से हल कर सकते हैं।

क्यों? स्यूडो-लूप एक "सेफ्टी वाल्व" या "शॉर्टकट कोड" की तरह काम करता है। यह सिस्टम को इतनी लचीलापन देता है कि वह किसी जटिल भूलभुलैया में फंसे बिना हमेशा एक समाधान ढूंढ लेता है।

पथ 2: कठिन तरीका (NP-Hard)
यदि मानचित्र में कोई स्यूडो-लूप नहीं है (आप कभी भी एक ही पड़ोस के भीतर नहीं रह सकते; आपको हमेशा दूसरे पड़ोस में जाना ही होगा), तो रंग भरने की समस्या असंभव रूप से कठिन है (जब तक कि आपके पास रंगों की एक बहुत विशिष्ट सूची न हो)।

क्यों? उस आंतरिक "शॉर्टकट कोड" के बिना, मानचित्र एक कठोर, जटिल संरचना बन जाता है। इसे रंगना एक ऐसे सुडोकू पहेली को हल करने जैसा है जिसे अनंत तक फैला दिया गया है। इसमें हर संभव परिमित (finite) पहेली की जटिलता समाहित है।

"जादुई ट्रिक" (कार्यप्रणाली)

उन्होंने एक अनंत मानचित्र के लिए इसे कैसे सिद्ध किया? आप एक अनंत मानचित्र को एक-एक करके नहीं देख सकते।

"फिनाइटाइजिंग" (Finitising) ट्रिक:
लेखकों ने एक तरीका खोजा जिससे वे अनंत मानचित्र को देखते हुए उसकी एक परिमित छाया (finite shadow) देख सकें।

उन्होंने एक विशेष "लेंस" बनाया (जिसे रिफाइनमेंट $\alpha$ कहा जाता है)।
जब उन्होंने इस लेंस के माध्यम से देखा, तो अनंत मानचित्र कुछ ही "सुपर-शहरों" ( $\alpha$ -classes) वाले एक छोटे, परिमित मानचित्र में सिमट गया।
उन्होंने सिद्ध किया कि यदि अनंत मानचित्र "स्मूथ" है और उसमें कोई स्यूडो-लूप नहीं है, तो यह छोटी सी परिमित छाया इतनी जटिल है कि यह किसी भी अन्य परिमित पहेली का अनुकरण (simulate) कर सकती है।
यदि छाया इतनी जटिल है, तो मूल अनंत मानचित्र भी वैसा ही होगा।

उपमा: कल्पना कीजिए कि आप एक विशाल, अनंत महासागर को समझने की कोशिश कर रहे हैं। हर बूंद को मापने के बजाय, आप एक बाल्टी में पानी का नमूना लेते हैं। यदि उस बाल्टी का पानी इतना अशांत है कि वह एक तूफान की नकल कर सकता है, तो आप जानते हैं कि पूरा महासागर भी खतरनाक है।

"शोक" (शीर्षक क्यों?)

शीर्षक "The Sorrows of a Smooth Digraph" थोड़ा काव्यात्मक है।

यदि डाइग्राफ "स्मूथ" (पूरी तरह से सुचारू) है लेकिन उसमें स्यूडो-लूप की कमी है, तो यह "दुखी" है क्योंकि यह गणनात्मक रूप से कठिन होने के लिए अभिशप्त है। इसे वश में नहीं किया जा सकता।
इस "शोक" (कठिनाई) से बचाने का एकमात्र तरीका इसे एक स्यूडो-लूप देना है। यदि इसके पास एक भी नहीं है, तो इसे सब कुछ बनाना होगा (हर परिमित संरचना का निर्माण करना होगा), जो इसका "अभिशाप" है।

सबके लिए मुख्य बातें

अनंत हमेशा कठिन नहीं होता: भले ही मानचित्र अनंत हो, इसकी जटिलता एक सरल संरचनात्मक विशेषता द्वारा निर्धारित होती है: क्या इसमें एक पड़ोस के भीतर रहने वाली सड़क है?
"सूची" मायने रखती है: यह परिणाम विशेष रूप से तब लागू होता है जब आपके पास अनुमत रंगों की सूचियाँ होती है (कंजर्वेटिव CSPs)। यह एक बहुत ही सामान्य वास्तविक दुनिया का परिदृश्य है (जैसे मीटिंग शेड्यूल करना जहाँ व्यक्ति A केवल मंगलवार को मिल सकता है, व्यक्ति B केवल बुधवार को)।
सेतु (The Bridge): पेपर ने सफलतापूर्वक "परिमित गणित" (जिसे हम अच्छी तरह समझते हैं) और "अनंत गणित" (जो आमतौर पर एक दुःस्वप्न होता है) के बीच के अंतर को पाट दिया है। उन्होंने दिखाया कि इस विशिष्ट प्रकार के अनंत ढांचे के लिए, परिमित दुनिया के नियम भी लागू होते हैं, बशर्ते आप सही "पड़ोसों" को देखें।

संक्षेप में: यदि आपके अनंत मानचित्र में एक "स्थानीय लूप" (एक ही पड़ोस में रहने का तरीका) है, तो रंग भरना आसान है। यदि यह आपको लगातार पड़ोसों के बीच कूदने के लिए मजबूर करता है और रुकने का कोई रास्ता नहीं देता, तो रंग भरना असंभव रूप से कठिन है। यह पेपर पहली बार इस विशिष्ट अनंत संदर्भ में इसे सिद्ध करता है।

यहाँ ब्रूनर, कोज़िक, नागी और पिंस्कर के शोध पत्र "The Sorrows of a Smooth Digraph: The First Hardness Criterion for Infinite Directed Graph-Colouring Problems" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या का विवरण और संदर्भ

मुख्य समस्या:
यह शोध पत्र अनंत डोमेन (infinite domains), विशेष रूप से $\omega$ -categorical संरचनाओं पर केंद्रित 'कन्स्ट्रेंट सैटिस्फैक्शन प्रॉब्लम्स' (CSPs) के जटिलता वर्गीकरण (complexity classification) को संबोधित करता है। जबकि परिमित डोमेन (finite-domain) वाले CSPs के लिए जटिलता द्विभाजन (complexity dichotomy - P बनाम NP-complete) को 2017 में बुलेटोव और झुक द्वारा स्थापित किया गया था, इन परिणामों को अनंत डोमेन तक विस्तारित करना एक प्रमुख खुला प्रश्न बना हुआ है।

विशिष्ट फोकस:
लेखक बीजगणिक लंबाई 1 (algebraic length 1) वाले स्मूथ डाइग्राफ (smooth digraphs) पर ध्यान केंद्रित करते हैं।

स्मूथ डाइग्राफ (Smooth Digraph): एक निर्देशित ग्राफ जहाँ प्रत्येक शीर्ष (vertex) का कम से कम एक इनकमिंग और एक आउटगोइंग एज होता है (कोई सोर्स या सिंक नहीं)।
बीजगणिक लंबाई 1 (Algebraic Length 1): यह अनडिरेक्टेड ग्राफों में गैर-द्विभाजी (non-bipartiteness) के गुण का सामान्यीकरण है, जो एक बंद वॉक (closed walk) के अस्तित्व को सुनिश्चित करता है जिसकी शुद्ध "बीजगणिक" लंबाई 1 है।
$\omega$ -categoricity: इस संरचना का एक ओलिगोमॉर्फिक ऑटोमोर्फिज्म समूह (oligomorphic automorphism group) होता है (सभी $k$ -टुपल्स के लिए परिमित ऑर्बिट्स)।

अंतराल (The Gap):
अनंत संरचनाओं के लिए पिछले परिणाम सीमित थे। अनडिरेक्टेड ग्राफों के लिए, एक संरचनात्मक द्विभाजन ज्ञात था (बार्टो और पिंस्कर, 2023), लेकिन डाइग्राफों के लिए, इस बात का कोई संरचनात्मक परिणाम ज्ञात नहीं था कि कैसे सभी परिमित संरचनाओं को "pp-construct" (प्रिमिटिव पॉजिटिव कंस्ट्रक्ट) किया जा सकता है। यह शोध पत्र अनंत $\omega$ -categorical सेटिंग के लिए, विशेष रूप से कंजर्वेटिव (conservative) CSPs (जहाँ अनुमत मानों की सूचियाँ प्रदान की जाती हैं) के लिए परिमित संरचनात्मक द्विभाजन को ऊपर उठाने का लक्ष्य रखता है।

2. कार्यप्रणाली (Methodology)

लेखक उन्नत बीजगणितीय मॉडल सिद्धांत (algebraic model theory), सार्वभौमिक बीजगणित (universal algebra), और संयोजन ग्राफ सिद्धांत (combinatorial graph theory) के मिश्रण का उपयोग करते हैं। उनकी कार्यप्रणाली में कई प्रमुख नवाचार शामिल हैं:

A. "फिनाइटाइजिंग" तुल्यता ( $\alpha$ ):
एक केंद्रीय तकनीकी बाधा यह है कि अनंत संरचनाओं को संरचनात्मक जानकारी (जैसे कनेक्टिविटी) खोए बिना सीधे परिमित कोटिएंट्स (finite quotients) में नहीं बदला जा सकता है।

लेखक एक विशिष्ट तुल्यता संबंध $\alpha$ का निर्माण करते हैं (जो ऑर्बिट तुल्यता $\omega$ का एक परिशोधन है) जो डाइग्राफ को "फिनाइटाइज" (परिमित बनाता) करता है।
$\alpha$ के गुण:
1. $\Omega$ -invariant: $\Omega$ द्वारा संरक्षित।
2. सन्निकट ऑर्बिट्स पर एकैकी (Bijective on Adjacent Orbits): एज संबंध $\alpha$ -क्लासेस के बीच एक बाइजेक्शन प्रेरित करता है।
3. परिमित कोटिएंट: कोटिएंट ग्राफ $G/\alpha$ में प्रत्येक वीकली कनेक्टेड कंपोनेंट के भीतर परिमित वर्टिक्स (क्लासेस) होते हैं।
यह लेखकों को $G/\alpha$ पर परिमित संयोजन तर्क (finite combinatorial arguments) लागू करने की अनुमति देता है और फिर $\alpha$ -ब्लो-अप्स (blow-ups) के माध्यम से परिणामों को $G$ तक वापस ले जाता है।

B. रिडक्शनिस्टिक सेट्स (Reductionistic Sets):
अनंत डोमेन को आगमन (inductively) के रूप में संभालने के लिए, लेखक $\Omega$ -reductionistic सेट्स पेश करते हैं। ये डोमेन के उपसमुच्चय हैं जो $\Omega$ -इनवेरिएंट इक्विवेलेंस रिलेशन की क्लासेज़ हैं। ये लेखकों को आवश्यक बीजगणितीय गुणों और $\alpha$ के प्रतिबंधित ऑटोमोर्फिज्म समूह को सुरक्षित रखते हुए डोमेन को आगमन के रूप में छोटा करने की अनुमति देते हैं।

C. ट्री PP-डेफिनिशन और ब्लो-अप्स:
मानक प्रिमिटिव पॉजिटिव (pp) डेफिनिशन हमेशा एक कोटिएंट से मूल संरचना तक नहीं पहुँच पाते हैं। लेखक अपना ध्यान ट्री pp-डेफिनिशन पर केंद्रित करते हैं, जिन्हें लिफ्ट किया जा सकता है। वे $\alpha$ -ब्लो-अप्स की अवधारणा का उपयोग करते हैं: यदि कोई संबंध $G/\alpha$ पर परिभाषित है, तो उसका $G$ पर ब्लो-अप, $G$ और $\alpha$ -क्लासेस से pp-परिभाषित होता है।

D. आगमन कटौती रणनीति (Inductive Reduction Strategy):
प्रमाण $\alpha$ -क्लासेस की संख्या पर आगमन (induction) द्वारा आगे बढ़ता है।

वे परिमित कोटिएंट $G/\alpha$ पर एज संबंध का विश्लेषण करते हैं।
यदि संबंध "पूर्ण" (k-linked) है, तो वे एक छोटे सबग्राफ तक सीमित हो जाते हैं।
यदि पूर्ण नहीं है, तो वे विशिष्ट संबंध (जैसे $OR(T, T)$ या सेंट्रल रिलेशंस) का निर्माण करते हैं जो या तो और अधिक कटौती की अनुमति देते हैं या सीधे यह प्रदर्शित करते हैं कि संरचना सभी परिमित संरचनाओं को pp-construct करती है (जो NP-hardness को दर्शाता है)।

3. मुख्य योगदान

1. मुख्य प्रमेय (Theorem 1.3):
यह शोध पत्र अनंत सेटिंग में स्मूथ डाइग्राफ के लिए पहला संरचनात्मक द्विभाजन स्थापित करता है।

कथन: मान लीजिए कि $G$ $G$ एक स्मूथ डाइग्राफ है जिसकी बीजगणिक लंबाई 1 है और $\Omega \leq \text{Aut}(G)$ $Ω \leq Aut (G)$ ओलिगोमॉर्फिक है। तब या तो:
1. कोटिएंट $G/\Omega$ में एक स्यूडो-लूप (pseudo-loop) (एक $\Omega$ -ऑर्बिट के भीतर एक एज) होता है; या
2. $G$ का $\Omega$ के सापेक्ष 2-कंजर्वेटिव एक्सपेंशन (2-conservative expansion) सब कुछ (EVERYTHING) pp-construct करता है (प्रत्येक परिमित संरचना)।

2. कंजर्वेटिव CSPs के लिए हार्डनेस मानदंड (Corollary 1.4):
यह इसका सीधा कम्प्यूटेशनल परिणाम है। ऐसे डाइग्राफ के लिए कंजर्वेटिव CSP (लिस्ट होमोमोर्फिज्म समस्या) NP-hard है जब तक कि $G/\Omega$ में स्यूडो-लूप न हो। यह हेल-नेशेट्रिल (Hell-Nešetřil) प्रमेय को लिस्ट के साथ अनंत डाइग्राफों के लिए सामान्यीकृत करता है।

3. बीजगणितीय इनवेरिएंट (Corollary 1.6):
लेखक एक नया बीजगणितीय मानदंड प्राप्त करते हैं। यदि 2-कंजर्वेटिव एक्सपेंशन सब कुछ pp-construct नहीं करता है, तो संरचना के पास एक 4-ary pseudo-Siggers polymorphism होना चाहिए।

इसमें यूनरी पॉलीमोर्फिज्म $u, v$ और एक 4-ary पॉलीमोर्फिज्म $s$ शामिल है जो $u(s(a, r, e, a)) = v(s(r, a, r, e))$ को संतुष्ट करता है।
यह बोडिरस्की-पिंस्कर अनुमान (Bodirsky-Pinsker Conjecture) की ओर एक महत्वपूर्ण कदम है, जो यह दावा करता है कि ऐसे पॉलीमोर्फिज्म का अस्तित्व सभी $\omega$ -categorical CSPs के लिए सुलभता (tractability) को परिभाषित करता है।

4. पिछले अवरोधों को दूर करना:
यह शोध पत्र परिमित से अनंत डाइग्राफ तक परिणामों को उठाने की कठिनाई को हल करता है। पिछले प्रयास विफल रहे क्योंकि सिंगलटन संबंध (ऑर्बिट्स को फिक्स करने के लिए) अनंत संरचनाओं में ओलिगोमॉर्फिक गुण को नष्ट कर देते हैं। ऑर्बिट्स के जोड़ों के यूनियन (unions of pairs of orbits) (2-कंजर्वेटिविटी) का उपयोग करके, लेखक आवश्यक समरूपता (symmetry) बनाए रखते हैं जबकि पर्याप्त कठोरता (rigidity) प्राप्त करते हैं।

4. परिणाम और तकनीकी विवरण

प्रमाण संरचना: प्रमाण "k-linkedness" के कोटिएंट ग्राफ में शामिल "केस एनालिसिस" (जिसे पेपर के चित्र 2 में देखा जा सकता है) पर निर्भर करता है।
- यदि एज संबंध पूर्ण है, तो लेखक समस्या को एक छोटे सबग्राफ तक कम करते हैं।
- यदि पूर्ण नहीं है, तो वे $OR(T, T)$ जैसे संबंधों का निर्माण करते हैं।
- श्रृंखलाबद्ध लेमा (6.6–6.10) के माध्यम से, वे दिखाते हैं कि यदि संरचना में स्यूडो-लूप नहीं है, तो ये निर्माण अंततः एक ऐसा संबंध उत्पन्न करते हैं जो एक ऐसी परिमित संरचना को pp-construct करता है जो ज्ञात रूप से NP-hard है।
प्रपोजिशन 1.7: एक साइड रिजल्ट के रूप में, वे सिद्ध करते हैं कि यदि कोटिएंट ग्राफ $G/\Omega$ एक विशिष्ट 3-वर्टेक्स ग्राफ (जो सिग्र्स आइडेंटिटी के अनुरूप है) के आइसोमोर्फिक है, तो 1-कंजर्वेटिविटी (सिंगल ऑर्बिट्स के यूनियन) भी सब कुछ pp-construct करने के लिए पर्याप्त है। यह सुझाव देता है कि मुख्य प्रमेय में 2-कंजर्वेटिव धारणा केवल सामान्य मामलों के लिए टाइट हो सकती है।

5. महत्व

प्रथम श्रेणी का कार्य: यह अनंत डाइग्राफ (बीजगणिक लंबाई 1 वाले) के लिए पहला संरचनात्मक द्विभाजन परिणाम है। इससे पहले, अनंत डाइग्राफ के लिए कोई संरचनात्मक परिणाम ज्ञात नहीं था जो परिमित संरचनाओं की व्याख्या करने में विफल रहता है।
पूर्ण द्विभाजन की ओर सेतु: यह परिणाम अनंत-डोमेन CSPs के लिए पूर्ण जटिलता द्विभाजन की ओर एक महत्वपूर्ण मील का पत्थर है। यह पुष्टि करता है कि बीजगणितीय दृष्टिकोण (पॉलीमोर्फिज्म) अनंत डाइग्राफ के लिए भी काम करता है, ठीक वैसे ही जैसे परिमित डाइग्राफ के लिए।
नया बीजगणितीय इनवेरिएंट: 4-ary pseudo-Siggers polymorphism की पहचान करना, जो अनंत संरचनाओं के लिए P और NP के बीच विभाजक हो सकता है, एक बड़ी सैद्धांतिक प्रगति है। यह सामान्य बोडिरस्की-पिंस्कर अनुमान के लिए एक ठोस लक्ष्य प्रदान करता है।
पद्धतिगत नवाचार: सावधानीपूर्वक निर्मित इक्विवेलेंस $\alpha$ के माध्यम से अनंत डाइग्राफ को "फिनाइटाइज" करने की तकनीक और रिडक्शनिस्टिक सेट्स का उपयोग करना, अनंत-डोमेन कंस्ट्रेंट सैटिस्फैक्शन पर काम करने वाले शोधकर्ताओं के लिए एक नया टूलकिट प्रदान करता है।

संक्षेप में, यह शोध पत्र सफलतापूर्वक "हेल-नेशेट्रिल" शैली के द्विभाजन को परिमित से अनंत डाइग्राफ तक ले जाता है, यह सिद्ध करता है कि ऑर्बिट कोटिएंट में स्यूडो-लूप की अनुपस्थिति संगत कंजर्वेटिव कलरिंग समस्या के लिए कम्प्यूटेशनल हार्डनेस (NP-hardness) को दर्शाती है, और सुलभता के साक्षी के रूप में विशिष्ट बीजगणितीय पॉलीमोर्फिज्म के अस्तित्व को स्थापित करती है।