ग्राफ अनियमितता किनारा विलोपन के माध्यम से

मूल जानकारी

• पेपर ID: 2511.14514
• शीर्षक: ग्राफ अनियमितता किनारा विलोपन के माध्यम से
• लेखक: Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille, Nacim Oijid
• वर्गीकरण: math.CO (संयोजक गणित), cs.CC (कम्प्यूटेशनल जटिलता), cs.DM (असतत गणित)
• प्रकाशन तिथि: 18 नवंबर 2025 (arXiv प्रीप्रिंट)
• पेपर लिंक: https://arxiv.org/abs/2511.14514

सारांश

यह पेपर ग्राफ के किनारा अनियमितकरण समस्या का अध्ययन करता है, अर्थात् पैरामीटर Ie(G), जो न्यूनतम k किनारों को हटाकर ग्राफ G को स्थानीय अनियमित ग्राफ (किसी भी दो आसन्न शीर्षों की डिग्री भिन्न) बनाने के लिए आवश्यक न्यूनतम k मान को दर्शाता है। यद्यपि यह समस्या NP-कठोर और W1-कठोर सिद्ध हुई है, लेखकों ने दो FPT एल्गोरिदम प्रस्तावित किए: एक समाधान के आकार प्लस अधिकतम डिग्री ∆ के संबंध में, और दूसरा शीर्ष कवर संख्या के संबंध में। इसके अलावा, लेखकों ने सघन ग्राफ, विशेषकर पूर्ण ग्राफ का गहन अध्ययन किया है, और एक महत्वपूर्ण अनुमान प्रस्तावित किया है: किसी भी जुड़े ग्राफ G के लिए, Ie(G) ≤ m/3 + c, जहां m किनारों की संख्या है और c एक स्थिरांक है। यह अनुमान कई ग्राफ वर्गों (पेड़ों सहित) पर सत्यापित किया गया है।

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

समस्या परिभाषा

ग्राफ सिद्धांत में, नियमित ग्राफ वे हैं जहां सभी शीर्षों की डिग्री समान है। द्वैत अवधारणा के रूप में, शोधकर्ताओं ने अनियमितता की कई परिभाषाएं प्रस्तावित की हैं:

1. अनियमित ग्राफ: सभी शीर्षों की डिग्री पारस्परिक रूप से भिन्न
2. अत्यधिक अनियमित ग्राफ: प्रत्येक शीर्ष के पड़ोसियों की डिग्री भिन्न
3. स्थानीय अनियमित ग्राफ: किसी भी दो आसन्न शीर्षों की डिग्री भिन्न

यह पेपर स्थानीय अनियमित ग्राफ की अवधारणा पर केंद्रित है।

अनुसंधान का महत्व

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

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

• Fioravantes आदि 10 ने हाल ही में किनारा अनियमितकरण उप-ग्राफ की अवधारणा प्रस्तावित की, जिसमें इष्टतम किनारा अनियमितकरण उप-ग्राफ की गणना NP-कठोर है
• यह समस्या समाधान के आकार और प्रतिक्रिया शीर्ष सेट दोनों के संबंध में W1-कठोर है
• सघन ग्राफ (जैसे पूर्ण ग्राफ) और कुछ संरचनात्मक पैरामीटर (पड़ोस विविधता, क्लिक तक की दूरी) के व्यवहार अभी स्पष्ट नहीं हैं

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

लेखकों का उद्देश्य:

1. विशिष्ट पैरामीटर के लिए कुशल FPT एल्गोरिदम डिजाइन करना
2. विभिन्न ग्राफ वर्गों के लिए Ie(G) के सटीक मान या ऊपरी सीमा को समझना
3. Ie(G) और ग्राफ के किनारों की संख्या m के बीच सार्वभौमिक संबंध की खोज करना

मुख्य योगदान

1. पैरामीटरीकृत एल्गोरिदम:
   • समाधान आकार k प्लस अधिकतम डिग्री ∆ के संबंध में FPT एल्गोरिदम प्रस्तावित, कर्नल आकार O(k∆^(2k+2))
   • शीर्ष कवर संख्या vc के संबंध में FPT एल्गोरिदम प्रस्तावित, समय जटिलता 2^O(vc^4)·n^O(1), पूर्व ILP-आधारित विधि से बेहतर
2. संरचनात्मक परिणाम:
   • पथ और चक्रों के लिए Ie के सटीक सूत्र प्रमाणित
   • पूर्ण द्विपक्षीय ग्राफ Kn,m के लिए प्रमाणित: Ie = 0 जब n≠m, Ie = n जब n=m
   • पेड़ों T के लिए प्रमाणित: Ie(T) ≤ |E(T)|/3 (जब तक T पथ न हो)
   • त्रिकोणीय संख्या tk के क्रम वाले पूर्ण ग्राफ के लिए सटीक सूत्र दिया: Ie(Ktk) = |E(Ktk)| - k(k+1)(k-1)(3k+2)/24
3. महत्वपूर्ण अनुमान (अनुमान 1): एक स्थिरांक c मौजूद है जैसे कि किसी भी जुड़े ग्राफ G के लिए m किनारों के साथ, Ie(G) ≤ m/3 + c
4. सैद्धांतिक अंतर्दृष्टि:
   • Ie(G) की सामान्य निचली सीमा प्रदान: Ie(G) ≥ ⌈conf(G)/(2∆-1)⌉
   • इष्टतम किनारा अनियमितकरण उप-ग्राफ में किनारों को संघर्ष किनारों के पास होना चाहिए (लेम्मा 1)

विधि विवरण

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

इनपुट: ग्राफ G = (V, E) और सकारात्मक पूर्णांक k ≥ 1
आउटपुट: यह निर्धारित करें कि क्या Ie(G) ≤ k (निर्णय संस्करण) या इष्टतम किनारा अनियमितकरण उप-ग्राफ की गणना करें (अनुकूलन संस्करण)

परिभाषाएं:

• ग्राफ G स्थानीय अनियमित है, यदि किसी भी किनारे uv ∈ E के लिए, dG(u) ≠ dG(v)
• किनारा अनियमितकरण उप-ग्राफ: किनारों का सेट S ⊆ E जैसे कि G-S स्थानीय अनियमित है
• Ie(G): न्यूनतम किनारा अनियमितकरण उप-ग्राफ का आकार
• conf(G): संघर्ष संख्या, अर्थात् किनारों uv की संख्या जहां dG(u) = dG(v)

मुख्य तकनीकी विधि

1. k+∆ के संबंध में कर्नलाइजेशन एल्गोरिदम (प्रमेय 2)

मुख्य लेम्मा 1: मान लीजिए S, G का इष्टतम किनारा अनियमितकरण उप-ग्राफ है, तो S में किसी भी किनारे e की किसी संघर्ष किनारे तक की दूरी अधिकतम 2|S|-1 है।

प्रमाण रणनीति (आगमन विधि):

• आधार: k=1 के लिए, हटाया गया एकमात्र किनारा किसी संघर्ष के आसन्न होना चाहिए
• आगमन: k≥2 के लिए, किसी भी संघर्ष uv के लिए, e∈S मौजूद होना चाहिए जो u या v के आसन्न हो; G-{e} में आगमन परिकल्पना लागू करें

कर्नलाइजेशन नियम:

1. यदि conf(G) ≥ k(2∆+1), तो नहीं उदाहरण लौटाएं
2. प्रत्येक संघर्ष किनारे e के लिए, गोला B(e, 2k+1) परिभाषित करें जिसमें e के अंतबिंदु से अधिकतम 2k+1 दूरी पर सभी शीर्ष हों
3. उप-ग्राफ H = G∪e∈EC Ve का निर्माण करें, जहां Ve, e का गोला है
4. H में शीर्ष डिग्री को समायोजित करें ताकि वह G में समान हो (पत्तियों को जोड़कर)

कर्नल आकार विश्लेषण:

• संघर्ष संख्या |EC| ≤ k(2∆+1)
• प्रत्येक गोले में अधिकतम 2∆^(2k) शीर्ष हैं
• कुल शीर्ष संख्या: |V(H)| ≤ 2k(2∆+1)∆^(2k+1) = O(k∆^(2k+2))

2. शीर्ष कवर संख्या के संबंध में एल्गोरिदम (प्रमेय 5)

एल्गोरिदम ढांचा:

1. मान लीजिए C = {u1,...,uvc} न्यूनतम शीर्ष कवर है, I = V\C स्वतंत्र सेट है
2. I को I1 और I2 में विभाजित करें:
   • I1: स्वतंत्र सेट शीर्ष जो C में कुछ डिग्री ≤ 5vc के शीर्ष के आसन्न हैं
   • I2: शेष स्वतंत्र सेट शीर्ष
3. G1 = GC∪I1, G2 = GC∪I2 परिभाषित करें
4. S1 = S∩E(G1) की सभी संभावनाओं की गणना करें (अधिकतम 2^O(vc^4) प्रकार)
5. प्रत्येक S1 के लिए, न्यूनतम S2⊆E2 की गणना करें जैसे कि G-(S1∪S2) स्थानीय अनियमित हो

मुख्य अवलोकन (दावा 7): किसी भी S1-सुसंगत इष्टतम किनारा अनियमितकरण उप-ग्राफ S के लिए, |S∩E2| ≤ vc^2

अनुकूलन तकनीक (दावा 8): u∈C और v1,v2∈I2 के लिए, यदि uv1∈S लेकिन uv2∉S, तो समतुल्य इष्टतम समाधान प्राप्त करने के लिए विनिमय कर सकते हैं। इसलिए केवल प्रत्येक u∈C के लिए हटाए गए किनारों की संख्या ki का अनुमान लगाने की आवश्यकता है, जहां Σki ≤ vc^2।

समय जटिलता: 2^(vc+5vc^2)^2 · vc^(vc^2) · n^2 = 2^O(vc^4) · n^O(1)

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

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

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

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

अध्ययन किए गए ग्राफ वर्ग

1. पथ Pn और चक्र Cn
2. पूर्ण द्विपक्षीय ग्राफ Kn,m
3. पेड़
4. पूर्ण ग्राफ Kn (विशेषकर त्रिकोणीय संख्या क्रम के)
5. सामान्य जुड़े द्विपक्षीय ग्राफ
6. सामान्य जुड़े ग्राफ

विश्लेषण विधि

• सटीक सूत्र व्युत्पत्ति: पथ, चक्र, विशिष्ट पूर्ण ग्राफ के लिए
• ऊपरी सीमा प्रमाण: पेड़, द्विपक्षीय ग्राफ, सामान्य ग्राफ के लिए
• रचनात्मक प्रमाण: सीमा तक पहुंचने वाले विशिष्ट किनारा अनियमितकरण उप-ग्राफ प्रदर्शित करें
• पुनरावर्ती एल्गोरिदम: पेड़ के लिए O(n∆^3) सटीक गणना एल्गोरिदम

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

मुख्य परिणाम

1. पथ और चक्र (प्रमेय 9)

n≥2 के पथ Pn के लिए:

• Ie(Pn) = (n-1)/3, जब n≡1 (mod 3)
• Ie(Pn) = ⌈(n-1)/3⌉, जब n≡2 (mod 3)
• Ie(Pn) = ⌊(n-1)/3⌋, अन्यथा

n≥3 के चक्र के लिए: Ie(Cn) = Ie(Pn) + 1

प्रमाण रणनीति: पथ को लगातार तीन-किनारों के समूहों में विभाजित करें, प्रत्येक समूह से कम से कम एक किनारा हटाएं

2. पूर्ण द्विपक्षीय ग्राफ (प्रमेय 10)

• Ie(Kn,m) = 0, जब n≠m (पहले से ही स्थानीय अनियमित है)
• Ie(Kn,n) = n (एक शीर्ष के सभी किनारों को हटाएं)

3. पेड़ (प्रमेय 13)

मुख्य प्रमेय: किसी भी पेड़ T के लिए, या तो T एक पथ है, या Ie(T) ≤ |E(T)|/3

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

• तारे और द्विपक्षीय तारे के उप-विभाजन के लिए, केंद्र से दूरी 2 के किनारों को हटाएं
• सामान्य पेड़ के लिए, आगमन विधि का उपयोग करें, सबसे गहरे डिग्री ≥3 के शीर्ष को चुनें
• विस्तृत केस विश्लेषण (उप-पेड़ संरचना और डिग्री के अनुसार)

एल्गोरिदम परिणाम (प्रमेय 15): पेड़ के Ie(G) को O(n∆^3) समय में सटीक रूप से गणना की जा सकती है

4. पूर्ण ग्राफ (प्रमेय 16)

क्रम n = tk = k(k+1)/2 (kवीं त्रिकोणीय संख्या) के लिए:

Ie(Ktk) = |E(Ktk)| - mk

जहां mk = k(k+1)(k-1)(3k+2)/24

निर्माण: अधिकतम किनारों वाला स्थानीय अनियमित ग्राफ Tk में डिग्री अनुक्रम है: 1 शीर्ष डिग्री n-1 के साथ, 2 शीर्ष डिग्री n-2 के साथ, ..., k शीर्ष डिग्री n-k के साथ

5. सामान्य ग्राफ की ऊपरी सीमा

द्विपक्षीय ग्राफ (प्रमेय 11): न्यूनतम डिग्री 1 वाले जुड़े द्विपक्षीय ग्राफ के लिए: Ie(G) ≤ n-1

सामान्य ग्राफ (प्रमेय 12): किसी भी जुड़े ग्राफ के लिए: Ie(G) ≤ ⌊m/2⌋ + n + ∆ - 2

अनुमान सत्यापन

अनुमान 1: एक स्थिरांक c मौजूद है जैसे कि किसी भी m किनारों वाले जुड़े ग्राफ G के लिए, Ie(G) ≤ m/3 + c

सत्यापित ग्राफ वर्ग:

• ✓ चक्र (c≥2)
• ✓ पेड़
• ✓ त्रिकोणीय संख्या क्रम वाले पूर्ण ग्राफ
• ✓ पूर्ण द्विपक्षीय ग्राफ
• ✓ प्रमेय 12 के माध्यम से, सामान्य ग्राफ कमजोर सीमा को संतुष्ट करते हैं

कसापन (प्रमेय 1): H के प्रत्येक किनारे को दो बार उप-विभाजित करके प्राप्त ग्राफ G के लिए: Ie(G) ≥ m/3 इसलिए 1/3 गुणांक कसा हुआ है।

मुख्य अंतर्दृष्टि

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

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

ग्राफ अनियमितता अनुसंधान का स्पेक्ट्रम

1. अनियमित ग्राफ 6: Chartrand आदि द्वारा अनियमितता शक्ति (irregularity strength) का परिचय, किनारों की बहुलता बढ़ाकर सभी डिग्री को भिन्न बनाना
2. अत्यधिक अनियमित ग्राफ 1,5: Alavi आदि द्वारा ग्राफ का अध्ययन जहां प्रत्येक शीर्ष के पड़ोसियों की डिग्री भिन्न हो
3. स्थानीय अनियमित ग्राफ 2,12:
   • Karoński, Luczak, Thomason द्वारा 1-2-3 अनुमान का प्रस्ताव (हाल ही में Keusch द्वारा हल 13)
   • Baudon आदि द्वारा नियमित ग्राफ को स्थानीय अनियमित उप-ग्राफ में विघटित करने का अध्ययन

विलोपन संचालन के माध्यम से गुण प्रस्तुत करना

4. नियमितता प्रस्तुत करना 3,4:
   • Bazgan आदि द्वारा किनारा घुमाव के माध्यम से डिग्री गुमनामी प्राप्त करना
   • Belmonte और Sau द्वारा बड़े विषम प्रेरित उप-ग्राफ खोजने का अध्ययन
5. शीर्ष अनियमितकरण उप-ग्राफ 11:
   • Fioravantes आदि द्वारा शीर्षों को हटाकर स्थानीय अनियमितता प्राप्त करने की अवधारणा
   • पेड़ की चौड़ाई और अधिकतम डिग्री के संबंध में FPT एल्गोरिदम सिद्ध किए
6. किनारा अनियमितकरण उप-ग्राफ 10:
   • हाल ही में प्रस्तावित अवधारणा (इस पेपर का सीधा पूर्ववर्ती)
   • NP कठोरता और कई W1 कठोरता परिणाम सिद्ध किए

इस पेपर का अद्वितीय योगदान

संबंधित कार्य की तुलना में:

• पहली बार k+∆ और शीर्ष कवर संख्या के संबंध में FPT एल्गोरिदम प्रस्तावित
• पहली बार कई ग्राफ वर्गों के सटीक मान का व्यवस्थित अध्ययन
• पहली बार m/3+c अनुमान प्रस्तावित और व्यापक रूप से सत्यापित
• पूर्ण ग्राफ का गहन अध्ययन, सघन ग्राफ पैरामीटर को समझने के लिए आधार तैयार करता है

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

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

1. एल्गोरिदम स्तर: यद्यपि समस्या कई पैरामीटर के तहत W1-कठोर है, संयुक्त पैरामीटर (k+∆) या संरचनात्मक पैरामीटर (शीर्ष कवर संख्या) के माध्यम से FPT एल्गोरिदम प्राप्त किए जा सकते हैं
2. संरचनात्मक स्तर:
   • कई ग्राफ वर्गों के Ie(G) को सटीक रूप से निर्धारित या कसा जा सकता है
   • पेड़ और विरल ग्राफ का व्यवहार अपेक्षाकृत सरल है
   • पूर्ण ग्राफ त्रिकोणीय संख्या से संबंधित परिष्कृत संरचना प्रदर्शित करते हैं
3. सैद्धांतिक स्तर: यदि अनुमान 1 सत्य है, तो यह Ie(G) के स्पर्शोन्मुख व्यवहार को एकीकृत करेगा

सीमाएं

1. पूर्ण ग्राफ की अपूर्णता: केवल त्रिकोणीय संख्या क्रम के मामले को हल किया गया है, सामान्य पूर्ण ग्राफ Kn के सटीक मान अभी भी अज्ञात हैं
2. अनुमान 1 की स्थिरांक: यद्यपि कई ग्राफ वर्गों पर सत्यापित, लेकिन स्थिरांक c का सटीक मान और सामान्य प्रमाण अभी भी अनुपलब्ध है
3. एल्गोरिदम दक्षता:
   • k+∆ के FPT एल्गोरिदम की घातांकीय निर्भरता ∆^(2k) पर व्यावहारिक अनुप्रयोग को सीमित करती है
   • शीर्ष कवर एल्गोरिदम ILP विधि में सुधार करता है, लेकिन अभी भी 2^O(vc^4) पर निर्भर है
4. सघन ग्राफ पैरामीटर: पड़ोस विविधता, क्लिक तक की दूरी आदि पैरामीटर की FPT संपत्ति अभी भी अनसुलझी है

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

लेखकों द्वारा स्पष्ट रूप से प्रस्तावित दिशाएं:

1. गतिशील संघर्ष पैरामीटर: संघर्ष विकास को गतिशील रूप से कैप्चर करने के लिए स्थिर conf पैरामीटर में सुधार
2. पूर्ण ग्राफ और घन ग्राफ:
   • सामान्य पूर्ण ग्राफ Kn के Ie के सटीक मान निर्धारित करें
   • घन ग्राफ की सीमा को कसें
3. k-अध: पतन ग्राफ तक विस्तार: समान तकनीकों का उपयोग करके (k-1)n + ⌊n/3⌋ की ऊपरी सीमा प्राप्त करें
4. पेड़ की चौड़ाई पैरामीटरीकरण: साहित्य 11 के शीर्ष संस्करण एल्गोरिदम को किनारा संस्करण में अनुकूलित किया जा सकता है
5. पड़ोस विविधता: पूर्ण ग्राफ समस्या को पूरी तरह हल करने के बाद इसे संभालने की आवश्यकता है

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

शक्तियां

1. सैद्धांतिक गहराई:
   • प्रमाण तकनीकें परिष्कृत हैं, विशेषकर लेम्मा 1 की दूरी सीमा और पेड़ों का आगमन प्रमाण
   • कर्नलाइजेशन एल्गोरिदम पैरामीटरीकृत जटिलता की गहरी समझ प्रदर्शित करता है
   • पूर्ण ग्राफ की त्रिकोणीय संख्या परिणाम गहरी संयोजक संरचना को प्रकट करती है
2. व्यवस्थितता:
   • विरल से सघन तक कई ग्राफ वर्गों को कवर करता है
   • एल्गोरिदम परिणाम और संरचनात्मक परिणाम दोनों हैं
   • सैद्धांतिक विश्लेषण और रचनात्मक प्रमाण संयुक्त
3. अनुमान का प्रस्ताव:
   • अनुमान 1 बहुत एकीकृत और प्रेरणादायक है
   • कई ग्राफ वर्गों पर सत्यापन विश्वसनीयता बढ़ाता है
   • प्रमेय 1 1/3 गुणांक की कसापन साबित करता है
4. लेखन गुणवत्ता:
   • संरचना स्पष्ट है, सरल से जटिल तक क्रमिक विकास
   • प्रमाण विस्तृत लेकिन अनावश्यक नहीं
   • चित्र समझ में सहायता करते हैं (जैसे चित्र 3, 4)
5. व्यावहारिक एल्गोरिदम:
   • पेड़ के लिए O(n∆^3) एल्गोरिदम बहुपद समय जटिलता है
   • FPT एल्गोरिदम व्यावहारिक अनुप्रयोगों के लिए सैद्धांतिक गारंटी प्रदान करते हैं

कमियां

1. पूर्णता अंतराल:
   • पूर्ण ग्राफ के सामान्य मामले अनसुलझे हैं, सघन ग्राफ की समझ को सीमित करता है
   • अनुमान 1 सामान्य प्रमाण से रहित है
2. एल्गोरिदम व्यावहारिकता:
   • k+∆ एल्गोरिदम की द्विगुणी घातांकीय निर्भरता व्यावहारिक अनुप्रयोग को सीमित करती है
   • एल्गोरिदम के व्यावहारिक प्रदर्शन का कोई प्रायोगिक मूल्यांकन नहीं
3. स्थिरांक अनुकूलन:
   • प्रमेय 12 की सीमा ⌊m/2⌋+n+∆-2 कसी नहीं हो सकती
   • विभिन्न ग्राफ वर्गों के स्थिरांक c मान सटीक रूप से निर्धारित नहीं
4. निचली सीमा विश्लेषण:
   • conf(G)/(2∆-1) के अलावा, अधिक परिष्कृत निचली सीमा तकनीकें अनुपलब्ध हैं
   • सन्निकटन एल्गोरिदम पर कोई चर्चा नहीं
5. पैरामीटर पदानुक्रम:
   • FPT और W1-hard के बीच की सीमा पूरी तरह से चिह्नित नहीं है
   • कुछ प्राकृतिक पैरामीटर (जैसे पेड़ की चौड़ाई+∆) अन्वेषित नहीं हैं

प्रभाव

1. सैद्धांतिक योगदान:
   • किनारा अनियमितकरण उप-ग्राफ अनुसंधान के लिए ठोस आधार स्थापित करता है
   • यदि अनुमान 1 सत्य है तो यह एक महत्वपूर्ण संयोजक परिणाम होगा
   • विधि (विशेषकर लेम्मा 1) अन्य ग्राफ संशोधन समस्याओं पर लागू हो सकती है
2. अनुवर्ती अनुसंधान:
   • पूर्ण ग्राफ समस्या संयोजकविदों को आकर्षित करेगी
   • FPT एल्गोरिदम तकनीकें अन्य स्थानीय गुणों तक विस्तारित हो सकती हैं
   • ग्राफ की स्थानीय अनियमितता को समझने के लिए नया दृष्टिकोण प्रदान करता है
3. व्यावहारिक मूल्य:
   • पेड़ एल्गोरिदम नेटवर्क विश्लेषण में सीधे लागू किया जा सकता है
   • ग्राफ गुमनामीकरण, नेटवर्क मजबूती आदि अनुप्रयोगों के लिए सैद्धांतिक समर्थन प्रदान करता है
4. खुलापन:
   • स्पष्ट और आकर्षक खुली समस्याएं छोड़ता है
   • विभिन्न कठिनाई स्तर विभिन्न शोधकर्ताओं के लिए उपयुक्त हैं

लागू परिदृश्य

1. नेटवर्क डिजाइन: ऐसे परिदृश्य जहां आसन्न नोड्स की समान डिग्री से बचना आवश्यक है (जैसे लोड संतुलन)
2. ग्राफ गुमनामीकरण: डिग्री पैटर्न को तोड़ने के लिए किनारों को हटाकर गोपनीयता की रक्षा करना
3. सैद्धांतिक कंप्यूटर विज्ञान:
   • पैरामीटरीकृत जटिलता की शिक्षण सामग्री
   • ग्राफ संशोधन समस्याओं के अनुसंधान का उदाहरण
4. संयोजक अनुकूलन: अधिक जटिल अनुकूलन समस्याओं के उप-समस्या के रूप में

संदर्भ (मुख्य उद्धरण)

2 Baudon आदि (2015): नियमित ग्राफ को स्थानीय अनियमित उप-ग्राफ में विघटित करना
6 Chartrand आदि (1988): अनियमित नेटवर्क, अनियमितता शक्ति का परिचय
10 Fioravantes आदि (2024): किनारा अनियमितकरण उप-ग्राफ का परिचय, मूल कठोरता परिणाम सिद्ध करना
11 Fioravantes आदि (2025): शीर्ष अनियमितकरण उप-ग्राफ की जटिलता
12 Karoński आदि (2004): 1-2-3 अनुमान
13 Keusch (2024): 1-2-3 अनुमान को हल करना

समग्र मूल्यांकन: यह सैद्धांतिक कंप्यूटर विज्ञान का एक उच्च गुणवत्ता वाला पेपर है, जो पैरामीटरीकृत जटिलता और ग्राफ सिद्धांत के प्रतिच्छेदन में वास्तविक योगदान देता है। यद्यपि कुछ समस्याएं (विशेषकर पूर्ण ग्राफ) पूरी तरह से हल नहीं हुई हैं, पेपर किनारा अनियमितकरण उप-ग्राफ की समझ को व्यवस्थित रूप से आगे बढ़ाता है, प्रस्तावित अनुमान का महत्वपूर्ण सैद्धांतिक महत्व है। विधि नवीन है, प्रमाण कठोर हैं, और अनुवर्ती अनुसंधान के लिए स्पष्ट दिशाएं प्रदान करता है। संयोजक गणित या सैद्धांतिक कंप्यूटर विज्ञान की शीर्ष पत्रिकाओं में प्रकाशन की सिफारिश की जाती है।