🔢 mathematics

Merge-width and First-Order Model Checking

यह शोध पत्र "मर्ज-विड्थ" (merge-width) को प्रस्तुत करता है, जो एक एकीकृत संरचनात्मक ग्राफ पैरामीटर है जो ट्रेewidth और ट्विन-विड्थ जैसे मापों को समाहित करता है, और यह सिद्ध करता है कि प्रथम-क्रम मॉडल चेकिंग (first-order model checking), सीमित मर्ज-विड्थ वाले ग्राफ वर्गों पर फिक्स्ड-पैरामीटर ट्रैक्टेबल (fixed-parameter tractable) है, जिससे बाउंडेड एक्सपेंशन और बाउंडेड ट्विन-विड्थ दोनों ढांचों के प्रमुख परिणामों का सामान्यीकरण होता है।

मूल लेखक: Jan Dreier, Szymon Toruńczyk

प्रकाशित 2026-06-25

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

CC BY 4.0

मूल लेखक: Jan Dreier, Szymon Toruńczyk

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

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

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

यहाँ सरल उपमाओं (analogies) का उपयोग करके इसका विवरण दिया गया है:

1. समस्या: जटिलता मापने के बहुत सारे तरीके

लंबे समय से, गणितज्ञों के पास ग्राफ की जटिलता मापने के लिए अलग-अलग पैमाने (rulers) रहे हैं।

ट्री-विड्थ (Treewidth) एक पेड़ की शाखाओं के विस्तार को मापने जैसा है।
ट्विन-विड्थ (Twin-width) इस बात को मापने जैसा है कि आपके पास कितने "जुड़वां" समूहों को आपस में जोड़ने की आवश्यकता है।
डिजेनेरेसी (Degeneracy) इस बात को मापने जैसा है कि कमरे का सबसे भीड़भाड़ वाला हिस्सा कितना भरा हुआ है।

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

2. नया उपकरण: कंस्ट्रक्शन सीक्वेंस (लेगो (Lego) की उपमा)

लेखकों ने ग्राफ बनाने का एक नया तरीका ईजाद किया जिसे कंस्ट्रक्शन सीक्वेंस (Construction Sequence) कहा जाता है। कल्पना कीजिए कि आप लेगो ब्रिक्स से एक ग्राफ बना रहे हैं, लेकिन आप इसे उल्टा कर रहे हैं:

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

मर्ज-विड्थ (Merge-width) यह मापता है कि इस प्रक्रिया के दौरान आप कितने "भ्रमित" होते हैं। विशेष रूप से, यह पूछता है: यदि मैं एक ईंट पर खड़ा हूँ, तो मैं एक निश्चित दूरी के भीतर कितने अलग-अलग "ब्लॉक्स" देख सकता हूँ?

यदि देखे जा सकने वाले ब्लॉक्स की संख्या कम है, तो ग्राफ में लो मर्ज-विड्थ (low merge-width) है (यह व्यवस्थित है)।
यदि संख्या बहुत अधिक है, तो ग्राफ में हाई मर्ज-विड्थ (high merge-width) है (यह अराजक है)।

3. बड़ी खोज: पैमानों का एकीकरण

यह शोध पत्र दिखाता है कि यह नया "मर्ज-विड्थ" पैमाना एक मास्टर कुंजी है। यह सच है कि:

जो ग्राफ पुराने "ट्विन-विड्थ" पैमाने के अनुसार सरल हैं, वे नए मर्ज-विड्थ पैमाने के अनुसार भी सरल हैं।
जो ग्राफ "बाउंडेड एक्सपेंशन" (स्पार्स, पेड़ जैसे ग्राफ के लिए एक अवधारणा) पैमाने के अनुसार सरल हैं, वे भी मर्ज-विड्थ के अंतर्गत सरल हैं।
यह उच्च "डिजेनेरेसी" वाले ग्राफों को भी कवर करता है।

अनिवार्य रूप से, मर्ज-विड्थ एक सुपर-रूलर (super-ruler) है जो जटिलता मापने के कई अलग-अलग तरीकों को एक ही परिवार में एकीकृत करता है।

4. मुख्य परिणाम: पहेली को तेज़ी से हल करना

सबसे महत्वपूर्ण हिस्सा फर्स्ट-ऑर्डर मॉडल चेकिंग (First-Order Model Checking) के बारे में है। यह ग्राफ के बारे में तार्किक प्रश्न पूछने का एक तकनीकी शब्द है (जैसे, "क्या यहाँ एक त्रिभुज है?" या "क्या हर कोई किसी से जुड़ा हुआ है?")।

बुरी खबर: सामान्य, अव्यवस्त ग्राफों के लिए, इन प्रश्नों का उत्तर देने में अनंत काल लग सकता है।
अच्छी खबर: लेखक सिद्ध करते हैं कि यदि आपके पास एक ऐसा ग्राफ है जिसका बाउंडेड मर्ज-विड्थ है (वह बहुत अधिक जटिल नहीं है) और आपको उसकी "रेसिपी" (निर्माण अनुक्रम/construction sequence) दी गई है जो इसे बनाने का तरीका दिखाती है, तो आप इन तार्किक प्रश्नों का उत्तर बहुत तेज़ी से दे सकते हैं।

वे इसे फिक्स्ड-पैरामीटर ट्रेक्टेबिलिटी (Fixed-Parameter Tractability) कहते हैं। सरल शब्दों में: "यदि ग्राफ बहुत जटिल नहीं है, तो हम इन समस्याओं को कुशलतापूर्वक हल कर सकते हैं, भले ही ग्राफ बहुत बड़ा हो।"

5. यह क्यों महत्वपूर्ण है (बिना तकनीकी शब्दों के)

यह बिंदुओं को जोड़ता है: यह दिखाता है कि ग्राफ थ्योरी के दो प्रमुख विचार (एक जो स्पार्स ग्राफ पर केंद्रित है और दूसरा जो "जुड़वां" संरचनाओं पर केंद्रित है) वास्तव में एक ही अंतर्निहित संरचना को देख रहे हैं, बस अलग-अलग दृष्टिकोणों से।
यह मजबूत है: लेखक दिखाते हैं कि यदि आप एक सरल ग्राफ क्लास लेते हैं और मानक तार्किक नियमों का उपयोग करके कनेक्शन बदलते हैं, तो नया क्लास भी "सरल" (बाउंडेड मर्ज-विड्थ वाला) रहता है। इसका मतलब है कि यह गुण स्थिर और विश्वसनीय है।
यह नए द्वार खोलता है: लेखकों को संदेह है कि मर्ज-विड्थ उन ग्राफों की एक और व्यापक श्रेणी के लिए इन तार्किक समस्याओं को हल करने की कुंजी हो सकती है जिनके लिए गणितज्ञ वर्षों से संघर्ष कर रहे हैं। उनका मानना है कि यदि कोई ग्राफ क्लास "डिपेंडेंट" (यानी उसमें हर संभव अराजक पैटर्न मौजूद नहीं है) है, तो उसमें संभवतः बाउंडेड मर्ज-विड्थ होगा।

सारांश

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

तकनीकी सारांश: मर्ज-विड्थ (Merge-width) और फर्स्ट-ऑर्डर मॉडल चेकिंग (First-Order Model Checking)

समस्या विवरण

यह शोध पत्र संरचनात्मक ग्राफ मापदंडों (structural graph parameters) के एकीकरण और फर्स्ट-ऑर्डर (FO) मॉडल चेकिंग की एल्गोरिद्मिक चुनौती को संबोधित करता है। जबकि ट्रेewidth (treewidth), डिजेनेरेसी (degeneracy), ट्विन-विड्थ (twin-width), और क्लिक-विड्थ (clique-width) जैसे मापदंडों ने विशिष्ट ग्राफ वर्गों (जैसे, स्पार्स ग्राफ या सीमित ट्विन-विड्थ वाले ग्राफ) के लिए प्रभावशीलता सिद्ध की है, वे अलग-अलग अपघटन तंत्रों (decomposition mechanisms) पर निर्भर करते हैं और अक्सर ग्राफ घनत्व के पूर्ण स्पेक्ट्रम में सामान्यीकरण करने में विफल रहते हैं। विशेष रूप से, बाउंडेड एक्सपेंशन (bounded expansion - स्पार्स) और बाउंडेड ट्विन-विड्थ (संभावित रूप से डेंस) के वर्ग वर्तमान में तुलनात्मक रूप से असंयोजित हैं, और कोई भी एकल ढांचा उनके एल्गोरिद्मिक गुणों को एकीकृत नहीं करता है।

केंद्रीय समस्या एक एकीकृत संरचनात्मक मापदंड को परिभाषित करने की है जो:

मौजूदा मापों (treewidth, degeneracy, twin-width, clique-width, generalized coloring numbers) को समाहित करे।
कुशल FO मॉडल चेकिंग (फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी, या FPT) का समर्थन करे।
फर्स्ट-ऑर्डर ट्रांसडक्शन (first-order transductions) के तहत सुदृढ़ (robust) हो।
संभावित रूप से मोनाडिकली डिपेंडेंट (monadically dependent) ग्राफों के वर्ग को अभिलक्षणिक (characterize) करे, जो कि FPT मॉडल चेकिंग के लिए सटीक सीमा होने का अनुमान है।

कार्यप्रणाली

लेखक मर्ज-विड्थ (merge-width) पेश करते हैं, जो निर्माण अनुक्रमों (construction sequences) पर आधारित एक नया ग्राफ पैरामीटर परिवार है। पारंपरिक अपघटन (जो केवल भागों को मर्ज करने (जैसे ट्विन-विड्थ के लिए कॉन्ट्रैक्शन सीक्वेंस) या विभाजित करने (जैसे ट्री डिकम्पोजिशन) पर निर्भर करते हैं) के विपरीत, निर्माण अनुक्रम वर्टेक्स सेट के विभाजन को बनाए रखते हुए साथ ही साथ भागों के जोड़ों की आसन्नता स्थिति (adjacency status) को भी हल करते हैं।

निर्माण अनुक्रम (Construction Sequences)

एक ग्राफ $G=(V, E)$ के लिए निर्माण अनुक्रम, जो वर्टेक्स सेट $\mathcal{P}$ के एक विभाजन और "रिज़ॉल्व्ड" जोड़ों (किनारों या गैर-किनारों) के एक सेट $R \subseteq \binom{V}{2}$ को बनाए रखता है, चरणों का एक क्रम है। यह अनुक्रम सिंगलटन (singletons) से शुरू होता है और एक एकल भाग के साथ समाप्त होता है जिसमें $V$ शामिल होता है। अनुमत ऑपरेशन हैं:

मर्ज (Merge): दो भागों $A, B \in \mathcal{P}$ को मिलाना।
रिज़ॉल्व (Resolve): दो भागों $A, B$ के बीच के सभी अनरिज़ॉल्व्ड (unresolved) जोड़ों को या तो किनारों या गैर-किनारों के रूप में घोषित करना।

महत्वपूर्ण रूप से, अनुक्रम को एक "डिफ़ॉल्ट कनेक्शन" गुण बनाए रखना चाहिए: किन्हीं भी दो भागों $A, B$ के लिए, उनके बीच के सभी अनरिज़ॉल्व्ड जोड़े अंतिम ग्राफ में या तो सभी किनारे होंगे या सभी गैर-किनारे। मर्ज होने से पहले होमोजेनिटी (homogeneity) सुनिश्चित करने के लिए रिज़ॉल्यूशन किया जाता है।

रेडियस- $r$ मर्ज-विड्थ (Radius- $r$ Merge-width)

जटिलता को रेडियस- $r$ मर्ज-विड्थ ($mwr(G) $) द्वारा मापा जाता है। एक दिए गए रेडियस$ r$ के लिए, विड्थ (width) उन भागों की अधिकतम संख्या है जो वर्तमान में रिज़ॉल्व्ड जोड़ों द्वारा निर्मित ग्राफ में किसी भी वर्टेक्स $v$ से लंबाई $r$ के पथ के माध्यम से पहुँचा जा सकता है। एक ग्राफ वर्ग का मर्ज-विड्थ बाउंडेड तब होता है जब प्रत्येक निश्चित $r$ के लिए $mwr_r(C)$ एक स्थिरांक (constant) द्वारा सीमित होता है।

एल्गोरिद्मिक दृष्टिकोण

मुख्य एल्गोरिद्मिक योगदान फर्स्ट-ऑर्डर लॉजिक (विशेष रूप से, डिस्टेंस लॉजिक या dist-FO) के लिए एक नवीन लोकैलिटी थ्योरम (locality theorem) पर आधारित है। लेखक सिद्ध करते हैं कि एक स्ट्रक्चर में किसी वर्टेक्स का ग्लोबल टाइप (global type), उसके लोकल टाइप (एक सीमित रेडियस के भीतर की जानकारी) और एक स्कैटर टाइप (स्कैटर्ड सेट्स के संबंध में वैश्विक संरचनात्मक गुण) द्वारा निर्धारित किया जा सकता है।

मॉडल चेकिंग एल्गोरिदम निर्माण अनुक्रम के माध्यम से पुनरावृत्ति करता है।
प्रत्येक चरण में, यह वर्टेक्स के लोकल टाइप्स को अपडेट करता है।
बाउंडेड मर्ज-विड्थ यह सुनिश्चित करती है कि विशिष्ट लोकल टाइप्स की संख्या प्रबंधनीय बनी रहे, जिससे एल्गोरिदम कुशलतापूर्वक एक FO वाक्य $\phi$ की संतुष्टि की गणना कर सके।

मुख्य योगदान और परिणाम

1. संरचनात्मक मापदंडों का एकीकरण

शोध पत्र प्रदर्शित करता है कि मर्ज-विड्थ कई प्रमुख संरचनात्मक मापदंडों को समाहित करता है:

बाउंडेड ट्विन-विड्थ: बाउंडेड ट्विन-विड्थ वाले ग्राफों की मर्ज-विड्थ बाउंडेड होती है (थ्योरम 1.4)।
बाउंडेड एक्सपेंशन: बाउंडेड एक्सपेंशन वाले ग्राफ वर्ग बाउंडेड मर्ज-विड्थ रखते हैं (थ्योरम 1.6)।
डिजेनेरेसी: $d$ -डिजेनरेट ग्राफों की रेडियस-1 मर्ज-विड्थ बाउंडेड होती है (थ्योरम 7.3)।
क्लिक-विड्थ: लिमिट पैरामीटर $mw_\infty(G)$ कार्यात्मक रूप से क्लिक-विड्थ के समकक्ष है (थ्योरम 7.1)।

यह "स्पर्सिटी" (bounded expansion) और "ट्विन-विड्थ" (bounded twin-width) फ्रेमवर्क को एकीकृत करता है।

2. फर्स्ट-ऑर्डर मॉडल चेकिंग की फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी (FPT)

थ्योरम 1.11: यदि इनपुट में एक विटिंग (witnessing) निर्माण अनुक्रम शामिल है, तो बाउंडेड मर्ज-विड्थ वाले ग्राफ वर्गों पर FO मॉडल चेकिंग समस्या FPT है।

जटिलता: $O_{q,w}(|V(G)|^3)$ , जहाँ $q$ वाक्य का क्वांटिफायर रैंक (quantifier rank) है और $w$ अनुक्रम की रेडियस- $r$ विड्थ है (जहाँ $r = 2^{O(q^2)}$ )।
महत्व: यह परिणामों को ड्वोरज़ाक, क्राल और थॉमस (बाउंडेड एक्सपेंशन) और बोनेट एट अल. (बाउंडेड ट्विन-विड्थ) से एक एकीकृत वर्ग तक विस्तारित करता है। हालांकि वर्तमान रनटाइम क्यूबिक है, लेखक अनुमान लगाते हैं कि इसे लीनियर (linear) में सुधारा जा सकता है।

3. क्लोजर प्रॉपर्टीज (Closure Properties)

थ्योरम 1.12: बाउंडेड मर्ज-विड्थ वाले वर्ग फर्स्ट-ऑर्डर इंटरप्रिटेशन (ट्रांसडक्शन) के तहत क्लोज्ड हैं। इसका तात्पर्य यह है कि ग्राफ स्क्वायर्स लेना या संरचनात्मक रूपांतरण लागू करने जैसे ऑपरेशन बाउंडेड मर्ज-विड्थ को संरक्षित करते हैं। फलस्वरूप, संरचनात्मक रूप से बाउंडेड एक्सपेंशन वाले वर्ग भी बाउंडेड मर्ज-विड्थ रखते हैं।

4. फ्लिप-विड्थ (Flip-width) के साथ संबंध

लेखक सिद्ध करते हैं कि बाउंडेड मर्ज-विड्थ, बाउंडेड फ्लिप-विड्थ को इंगित करता है (थ्योरम 1.7 और थ्योरम 7.6)। फ्लिप-विड्थ को पर्सूट-इवेजन गेम (pursuit-evasion game) के माध्यम से परिभाषित किया गया था और इसे पहले बाउंडेड एक्सपेंशन और ट्विन-विड्थ को सामान्यीकृत करने वाला दिखाया गया था।

अनुमान 1.17: लेखक अनुमान लगाते हैं कि इसका विलोम भी सत्य है: बाउंडेड फ्लिप-विड्थ, बाउंडेड मर्ज-विड्थ को दर्शाता है। यदि सत्य हुआ, तो यह इन तीन धारणाओं (बाउंडेड मर्ज-विड्थ, बाउंडेड फ्लिप-विड्थ, और बाउंडेड एक्सपेंशन का डेंस एनालॉग) की समानता स्थापित करेगा।

5. लगभग बाउंडेड मर्ज-विड्थ और मोनाडिकली डिपेंडेंट वर्ग

यह शोध पत्र लगभग बाउंडेड मर्ज-विड्थ (almost bounded merge-width) पेश करता है, जहाँ विड्थ स्थिरांक के बजाय उप-पॉलीनोमियल ( $n^{o(1)}$ ) रूप से बढ़ती है।

थ्योरम 1.14: सभी 'ना-कहीं-भी-घने' (nowhere dense) ग्राफ वर्ग लगभग बाउंडेड मर्ज-विड्थ रखते हैं।
थ्योरम 1.15: लगभग बाउंडेड मर्ज-विड्थ वाले हेरेडिटरी (hereditary) वर्ग लगभग बाउंडेड फ्लिप-विड्थ रखते हैं।
अनुमान 1.18: लेखक अनुमान लगाते हैं कि हेरेडिटरी ग्राफ वर्गों के लिए, निम्नलिखित समकक्ष हैं:
1. लगभग बाउंडेड मर्ज-विड्थ।
2. लगभग बाउंडेड फ्लिप-विड्थ।
3. मोनाडिकली डिपेंडेंट (वह वर्ग जो सभी ग्राफों को ट्रांसड्यूस नहीं करता है)।

यह अनुमान सुझाव देता है कि लगभग बाउंडेड मर्ज-विड्थ, मोनाडिकली डिपेंडेंट वर्गों के लिए लंबे समय से चली आ रही "मॉडल चेकिंग कंजैक्चर" को हल करने के लिए आवश्यक संरचनात्मक अपघटन प्रदान करता है।

महत्व और दावे

शोध पत्र दावा करता है कि यह संरचनात्मक ग्राफ सिद्धांत का एक वैचारिक एकीकरण प्रदान करता है। निर्माण अनुक्रमों को पेश करके, यह स्पार्स ग्राफ थ्योरी (Sparsity) और डेंस ग्राफ थ्योरी (Twin-width) के बीच की खाई को पाटता है।

एल्गोरिद्मिक प्रभाव: यह एक एकल FPT मेटा-थ्योरम स्थापित करता है जो बाउंडेड एक्सपेंशन और बाउंडेड ट्विन-विड्थ दोनों को कवर करता है, बशर्ते कि एक विटिंग (witnessing) अनुक्रम उपलब्ध हो।
सैद्धांतिक प्रभाव: यह एक नया संरचनात्मक पैरामीटर (मर्ज-विड्थ) प्रस्तावित करता है जो ट्रांसडक्शन के तहत सुदृढ़ है और फ्लिप-विड्थ के समकक्ष होने का अनुमान है।
भविष्य की दिशाएं: लेखक सुझाव देते हैं कि बाउंडेड मर्ज-विड्थ और बाउंडेड फ्लिप-विड्थ के बीच समानता (अनुमान 1.17) को सिद्ध करना, मर्ज-विड्थ के लिए FPT सन्निकटन (approximation) एल्गोरिदम की ओर ले जा सकता है। इसके अलावा, लगभग बाउंडेड मर्ज-विड्थ और मोनाडिक डिपेंडेंस के बीच समानता (अनुमान 1.18) को सिद्ध करना, व्यापकतम संभव वर्ग के ग्राफों (मोनाडिकली डिपेंडेंट क्लासेस) के लिए FO मॉडल चेकिंग समस्या को हल करने की दिशा में एक महत्वपूर्ण कदम माना गया है, जिसके पास वर्तमान में उपयुक्त अपघटन का अभाव है।

यह शोध पत्र एल्गोरिदम के वर्तमान रनटाइम (क्यूबिक बनाम लीनियर) के संबंध में विनम्र रहता है और स्वीकार करता है कि सामान्य ग्राफ वर्गों के लिए स्वयं निर्माण अनुक्रम को कंप्यूट करने के लिए एक FPT सन्निकटन एल्गोरिदम का अस्तित्व अभी भी एक खुला और चुनौतीपूर्ण प्रश्न बना हुआ है।