💻 computer science

$\tilde{O}$ ptimal Algorithm for 2-Approximate All Pair Shortest Paths -- almost

यह शोध पत्र एक रैंडमाइज्ड एल्गोरिदम प्रस्तुत करता है जो अनडिरेक्टेड, अनवेटेड ग्राफ्स में सभी-जोड़ों के लघुतम पथों (all-pairs shortest paths) की $\tilde{O}(n^2)$ समय में 2-अनुमान (2-approximation) की गणना करने के लिए कॉम्बिनेटोरियल तकनीकों को फास्ट मैट्रिक्स मल्टीप्लिकेशन के साथ जोड़ता है, जो $c \ge 0$ के एक स्थिरांक (constant) से अधिक दूरी पर स्थित सभी जोड़ों के लिए सटीकता की गारंटी देता है।

मूल लेखक: Manoj Gupta, Mrigankashekhar Shandilya

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

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

CC BY 4.0

मूल लेखक: Manoj Gupta, Mrigankashekhar Shandilya

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

कल्पना कीजिए कि आप एक विशाल, विस्तृत शहर में एक डिलीवरी ड्राइवर हैं जहाँ हर सड़क की लंबाई बिल्कुल एक समान है। आपका काम शहर के हर संभव पते के बीच सबसे तेज़ रास्ता पता लगाना है। यदि शहर में दस लाख घर हैं, तो आपको एक ट्रिलियन अलग-अलग रास्तों की गणना करनी होगी। कंप्यूटर विज्ञान की दुनिया में, इसे "ऑल-पेयर्स शॉर्टेस्ट पाथ" (All-Pairs Shortest Path) समस्या कहा जाता है। यह एक भूलभुलैया में हर एक शॉर्टकट को मैप करने की डिजिटल समानता है।

दशकों से, कंप्यूटर इन रास्तों को खोजने में बहुत अच्छे रहे हैं, लेकिन एक पेच है: नक्शा जितना सटीक होगा, उसे बनाने में उतना ही अधिक समय लगेगा। यदि आप परफेक्ट रास्ता चाहते हैं, तो कंप्यूटर को इतनी मेहनत करनी पड़ सकती है कि वह अनंत काल तक चलता रहे, खासकर बहुत बड़े शहरों के लिए। लेकिन क्या होगा अगर आप एक ऐसा रास्ता खोजने के लिए तैयार हैं जो "काफी अच्छा" हो—मान लीजिए, वास्तविक सबसे अच्छे पथ से दोगुना लंबा भी हो? इसे "2-approximation" कहा जाता है। यह एक ड्राइवर को यह बताने जैसा है कि, "चिंता मत करो कि तुम्हें एक अकेला परफेक्ट शॉर्टकट ढूंढना है; बस मुझे एक ऐसा रास्ता दे दो जो तुम्हें वास्तविक रास्ते से दो गुना से ज्यादा लेट न करे।" मुख्य सवाल वैज्ञानिकों के लिए यह रहा है: क्या हम एक लाख घरों वाले पूरे शहर के लिए ऐसा "काफी अच्छा" नक्शा लगभग उतनी ही तेज़ी से बना सकते हैं जितनी तेज़ी से सभी घरों की सूची लिखी जा सकती है?

यह शोध पत्र, जिसे मनोज गुप्ता और मृगांकशेखरandशिखा (Mrigankashekhar Shandilya) द्वारा लिखा गया है, ठीक इसी चुनौती से निपटता है। उन्होंने एक नया, चतुर तरीका डिज़ाइन किया है जिससे वे लगभग हर स्थान के जोड़े के लिए ये "काफी अच्छे" नक्शे बना सकते हैं, और वे इसे ऐसी गति से करते हैं जो सैद्धांतिक रूप से संभवतः सबसे तेज़ है।

समस्या: ट्रिलियन-रूट का दुःस्वप्न

मान लीजिए कि आपके पास एक ग्राफ है, जो केवल बिंदुओं (vertices) के एक नेटवर्क का एक फैंसी शब्द है जो रेखाओं (edges) द्वारा जुड़े हुए हैं। इन बिंदुओं को एक पार्टी में लोगों और रेखाओं को उनकी दोस्ती के रूप में सोचें। यदि आप किन्हीं भी दो लोगों के बीच परिचय की सबसे छोटी कड़ी जानना चाहते हैं, तो वह एक 'शॉर्टेस्ट पाथ' है।

यदि पार्टी छोटी है, तो आप बस हर किसी से पूछ सकते हैं। लेकिन यदि पार्टी में $n$ लोग हैं, तो $n^2$ (n गुना n) जोड़े हैं। यदि $n$ एक मिलियन है, तो $n^2$ एक ट्रिलियन है। शोध पत्र नोट करता है कि हर जोड़े के लिए उत्तर लिखना ही इस ट्रिलियन के अनुपात में समय लेता है। इसलिए, इस समस्या की "स्पीड लिमिट" $n^2$ है। आप इससे तेज़ नहीं जा सकते क्योंकि आपको उत्तर लिखना ही होगा।

इस शोध का लक्ष्य उस स्पीड लिमिट तक पहुँचना है। वे चाहते हैं कि एल्गोरिदम लगभग $n^2$ समय ( $\tilde{O}(n^2)$ में, जो कुछ छोटे, परेशान करने वाले गणितीय कारकों को छिपा देता है) में चले और यह गारंटी दे कि पाया गया रास्ता वास्तविक सबसे छोटे पथ की लंबाई से दोगुना से अधिक न हो।

पुराने तरीके: अनुमान लगाना और जांचना

इस शोध पत्र से पहले, वैज्ञानिकों ने इसे हल करने के प्रयास किए थे। कुछ विधियाँ घास के ढेर में सुई खोजने जैसी थीं, जहाँ हर घास के तिनके की जाँच की जाती थी। अन्य अधिक स्मार्ट थीं लेकिन उनमें एक अंधा धब्बा (blind spot) था।

डोर, हलपेरिन और ज़्विक (Dor, Halperin, and Zwick) का एक प्रसिद्ध दृष्टिकोण बहुत तेज़ी से इन "काफी अच्छे" रास्तों को खोज सकता था, लेकिन केवल उन लोगों के लिए जो पहले से ही काफी दूर (कम से कम $O(\log n)$ कदम दूर) थे। यदि दो लोग बिल्कुल पास बैठे थे, तो वह विधि विफल हो सकती थी या धीमी हो सकती थी। गुप्ता (2025 में) द्वारा किए गए एक अधिक हालिया सुधार ने इस सीमा को आगे बढ़ाया, जो उन लोगों को संभालता है जो कम से कम $O(\log \log n)$ कदम दूर हैं। लेकिन अभी भी एक छोटा सा अंतर बाकी था: उन लोगों का क्या जो केवल कुछ ही कदम दूर हैं? पुराने तरीके सभी के लिए "दोगुने लंबे" के नियम की गारंटी नहीं दे सकते थे जबकि अत्यधिक तेज़ बने रह सकें।

नया विचार: "बॉल" और "क्लस्टर"

लेखकों का समाधान दो अलग-अलग रणनीतियों का मिश्रण है: एक सावधानीपूर्वक, चरण-दर-चरण कॉम्बिनेटोरियल दृष्टिकोण और एक शक्तिशाली गणितीय ट्रिक जिसे फास्ट मैट्रिक्स मल्टीप्लिकेशन (FMM) कहा जाता है।

उनके इस तरीके को समझने के लिए, फिर से पार्टी की कल्पना करें। वे कुछ रैंडम लोगों को "पिवोट्स" (Pivots) के रूप में चुनते हैं।

द बॉल (The Ball): हर व्यक्ति के चारों ओर, वे एक अदृश्य "बॉल" बनाते हैं जिसमें वे सभी लोग शामिल हैं जो उनके निकटतम पिवोट की तुलना में उनके करीब हैं।
द क्लस्टर (The Cluster): इसके विपरीत, एक "क्लस्टर" उन लोगों का समूह है जिनके बॉल्स में एक विशिष्ट व्यक्ति शामिल है।

जादुई अंतर्दृष्टि यह है कि अधिकांश लोगों के लिए, ये "बॉल्स" छोटे और प्रबंधनीय होते हैं। यदि आप किसी के बॉल के अंदर हैं, तो आप उनके करीब हैं, और आप वास्तविक दूरी जल्दी से पा सकते हैं।

दो लोगों के बीच का रास्ता, मान लीजिए एलीस और बॉब, तीन भागों में विभाजित किया जा सकता है:

द प्रिफिक्स (The Prefix): एलीस का अपनी बॉल के किनारे तक चलना।
द मिडिल (The Middle): एलीस की बॉल के किनारे से बॉब की बॉल के किनारे तक का रास्ता।
द सफिक्स (The Suffix): बॉब का अपनी बॉल से अपने गंतव्य तक का रास्ता।

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

दो तरफा हमला: स्पार्स बनाम डेंस

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

परिदृश्य A: द स्पार्स केस (कम पड़ोसी)
कल्पना कीजिए कि पथ का मध्य भाग बहुत कम लोगों से घिरा हुआ है। इस मामले में, एल्गोरिदम बस "करीब" के सभी संभावित जोड़ों की जाँच करता है। चूंकि वे बहुत कम हैं, इसलिए यह जाँच तेज़ है। यह एक शांत पड़ोस में हर संभव शॉर्टकट की जाँच करने जैसा है; आप इसे जल्दी कर सकते क्योंकि वहाँ बहुत कम सड़कें हैं।

परिदृश्य B: द डेंस केस (अधिक पड़ोसी)
अब, कल्पना कीजिए कि मध्य भाग एक भीड़भाड़ वाले शहर के केंद्र में है जहाँ हजारों लोग पास में हैं। यहाँ हर जोड़े की जाँच करना बहुत समय ले लेगा। यहीं पर लेखक "फास्ट मैट्रिक्स मल्टीप्लिकेशन" (FMM) का उपयोग करते हैं।

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

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

परिणाम: एक लगभग परफेक्ट मैप

इन दोनों रणनीतियों को मिलाकर, लेखक यह सिद्ध करते हैं कि वे उन सभी जोड़ों के लिए एक ऐसा रास्ता खोज सकते हैं जो वास्तविक दूरी के दोगुने से कम है जो कम से कम एक निश्चित संख्या (विशेष रूप से, एक दूरी $c$ के बराबर, जहाँ $c$ एक स्थिरांक जैसे 906 है) के अंतर पर हैं।

पेपर दिखाता है कि इसे $\tilde{O}(n^2)$ समय में किया जा सकता है। यह एक बड़ा सुधार है क्योंकि इसका मतलब है कि एल्गोरिदम उस सैद्धांतिक सीमा के रूप में तेज़ है जिसकी अनुमति दी गई है (क्योंकि आपको $n^2$ उत्तर लिखने ही होंगे)।

इसका क्या अर्थ है

यह पेपर केवल यह सुझाव नहीं देता कि यह काम कर सकता है; वे एक कठोर गणितीय प्रमाण प्रदान करते हैं कि उनका रैंडमाइज्ड एल्गोरिदम "उच्च संभावना" (इसका अर्थ है कि यह लगभग हर बार काम करता है) के साथ काम करता है।

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

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

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

तकनीकी सारांश: 2-अनुमानित ऑल पेयर्स शॉर्टेस्ट पाथ्स के लिए इष्टतम एल्गोरिदम

समस्या विवरण
यह शोध पत्र एक अनडिरेक्टेड (undirected), अनवेटेड (unweighted) ग्राफ $G$ में $n$ वर्टिसेस (vertices) के लिए 2-एप्रोक्सिमेशन (2-approximation) ऑल-पेयर्स शॉर्टेस्ट पाथ्स (2-APSP) की गणना करने की समस्या को संबोधित करता है। जबकि आउटपुट का आकार $\Theta(n^2)$ है, जो $\Omega(n^2)$ का निचला स्तर (lower bound) दर्शाता है, मुख्य लक्ष्य $\tilde{O}(n^2)$ (लगभग द्विघाती/nearly quadratic) रनिंग टाइम प्राप्त करना है। पिछले कार्य द्वारा (DHZ00) यह समय जटिलता (time complexity) तो प्राप्त की गई थी, लेकिन केवल उन जोड़ों के लिए जो $O(\log n)$ की दूरी पर थे। हाल ही में, गुप्ता (Gup25) ने इसे $O(\log \log n)$ की दूरी तक सुधार दिया। खुला प्रश्न अभी भी एक ऐसा 2-APSP एल्गोरिदम डिजाइन करने का है जो $\tilde{O}(n^2)$ में चल सके और किसी भी स्थिर (constant) $c \ge 0$ की दूरी वाले सभी जोड़ों के लिए कार्य करे।

कार्यप्रणाली (Methodology)
प्रस्तावित एल्गोरिदम एक रैंडमाइज्ड (randomized) दृष्टिकोण है जो कॉम्बिनेटोरियल तकनीकों को फास्ट मैट्रिक्स मल्टीप्लिकेशन (FMM) के साथ जोड़ता है। कार्यप्रणाली किसी भी दो वर्टिसेस $s$ और $t$ के बीच के शॉर्टेस्ट पाथ के स्ट्रक्चरल डीकंपोजिशन (structural decomposition) पर आधारित है, जिसे एक संशोधित नेस्टेड वर्टेक्स सैंपलिंग स्कीम द्वारा सुगम बनाया गया है।

संशोधित नेस्टेड सैंपलिंग और क्लस्टरिंग:
एल्गोरिदम वर्टिसेस के सेट $A_i$ और संबंधित "बॉल्स" ( $ball_i(s)$ ) और "क्लस्टर्स" ( $cluster_i(s)$ ) को परिभाषित करने के लिए एक सैंपलिंग रणनीति का उपयोग करता है। पिछले कार्यों के विपरीत, जो केवल बॉल के आकार को सीमित करते थे, यह शोध पत्र थुरप और ज़विक (Thorup and Zwick) के एक परिणाम को अनुकूलित करता है ताकि यह सुनिश्चित किया जा सके कि एक विशिष्ट स्तर $\alpha$ के लिए, बॉल का आकार $|ball_\alpha(s)|$ और क्लस्टर का आकार $|cluster_\alpha(s)|$ दोनों $\tilde{O}(2^{2\alpha})$ द्वारा सीमित हों। यह सीमित क्लस्टर आकार एल्गोरिदम की दक्षता के लिए अत्यंत महत्वपूर्ण है।
पाथ डीकंपोजिशन (Path Decomposition):
जोड़े $(s, t)$ के लिए, शॉर्टेस्ट पाथ का विश्लेषण $ball_\alpha(s)$ और $ball_\alpha(t)$ की सीमाओं के सापेक्ष किया जाता है। पाथ को तीन खंडों में विभाजित किया गया है:

प्रिफिक्स (Prefix - $s \to p_s$ ): $s$ से उसके बॉल की सीमा तक का एक पथ। इस खंड के भीतर के वर्टिसेस का डिग्री कम है।
सफिक्स (Suffix - $p_t \to t$ ): $t$ के बॉल की सीमा से $t$ तक का पथ। इसी प्रकार, इन वर्टिसेस की डिग्री भी कम है।
मिडल सेगमेंट (Middle Segment - $p_s \to p_t$ ): दोनों बॉल्स की सीमाओं को जोड़ने वाला खंड।
मुख्य तकनीकी अंतर्दृष्टि यह सिद्ध करना है कि मिडल सेगमेंट $p_s p_t$ छोटा (एक स्थिरांक $c$ द्वारा सीमित) है। इसे ENSUREBALLPROXIMITY नामक एक सबरूटीन के माध्यम से स्थापित किया गया है, जो यह सुनिश्चित करता है कि या तो 2-एप्रोक्सिमेशन पहले ही मिल चुका है, या बॉल्स $s$ और $t$ पर्याप्त रूप से करीब हैं जिससे $|p_s p_t| \le c$ हो जाता है।

स्पार्स बनाम डेंस केस हैंडलिंग (Sparse vs. Dense Case Handling):
दूरी को कुशलतापूर्वक गणना करने के लिए, एल्गोरिदम संभावित वर्टिसेस $x$ (संभावित बाउंड्री पॉइंट्स) पर इटरेट करता है और उनके क्लस्टर्स में जोड़ों की जाँच करता है। यह दृष्टिकोण $ESTIMATEDCLOSE(x) $के आकार के आधार पर विभाजित है, जिसमें$ x$ के एक स्थिर दूरी के भीतर के वर्टिसेस शामिल हैं:

स्पार्स केस ( $|ESTIMATEDCLOSE(x)| \le n^{0.875}$ ): एल्गोरिदम उन जोड़ों $(x, y)$ को स्पष्ट रूप से सूचीबद्ध करता है जहाँ $y \in ESTIMATEDCLOSE(x)$ है। सीमित क्लस्टर आकार और स्पार्स कंडीशन के कारण, यह चरण $\tilde{O}(n^2)$ में चलता है।
डेंस केस ( $|ESTIMATEDCLOSE(x)| > n^{0.875}$ ): जब करीबी वर्टिसेस का सेट बड़ा होता है, तो एल्गोरिदम वर्टिसेस के एक रैंडम सैंपल $L$ का उपयोग करता है। यह एक सबग्राफ $G(\gamma)$ बनाता है जिसमें केवल लो-डिग्री एज (degree $\le \tilde{O}(\gamma)$ ) होते हैं। यह सिद्ध किया गया है कि $s$ और $t$ के बीच का शॉर्टेस्ट पाथ (और एक सैंपल किए गए वर्टेक्स $z \in L$ तक का पथ) पूरी तरह से $G(\gamma)$ के भीतर स्थित है।
फास्ट मैट्रिक्स मल्टीप्लिकेशन (FMM): डेंस केस के लिए, एल्गोरिदम $G(\gamma)$ में अनुमानों से प्राप्त दो मैट्रिसेस के मिन-प्लस प्रोडक्ट (डिस्टेंस प्रोडक्ट) का उपयोग करके दूरी का अनुमान लगाता है। विशेष रूप से, यह एक $n \times \tilde{O}(n^{0.125})$ मैट्रिक्स को $\tilde{O}(n^{0.125}) \times n$ मैट्रिक्स के साथ गुणा करता है। ज्ञात रेक्टेंगुलर मैट्रिक्स मल्टीप्लिकेशन परिणामों का उपयोग करते हुए जहाँ आंतरिक आयाम छोटा ( $r \le 0.17227$ ) है, इस प्रोडक्ट को $\tilde{O}(n^2)$ समय में कंप्यूट किया जा सकता है।

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

कांस्टेंट डिस्टेंस बाउंड का समाधान: शोध पत्र एक रैंडमाइज्ड एल्गोरिदम प्रस्तुत करता है जो उच्च संभावना (high probability) के साथ, कम से कम एक स्थिरांक $c$ (विशेष रूप से $c \le 906$ ) की दूरी पर सभी जोड़ों के लिए $\tilde{O}(n^2)$ समय में 2-एप्रोक्सिमेशन की गणना करता है। यह लॉगरिदमिक दूरी थ्रेशोल्ड से परे $\tilde{O}(n^2)$ प्राप्त करने के खुले प्रश्न को लगभग हल करता है।
कॉम्बिनेटोरियल तकनीकों के साथ FMM का एकीकरण: पिछले शुद्ध कॉम्बिनेटोरियल दृष्टिकोणों (जैसे DHZ00, Gup25) के विपरीत, यह कार्य "डेंस" केस को संभालने के लिए फास्ट मैट्रिक्स मल्टीप्लिकेशन को महत्वपूर्ण रूप से एकीकृत करता है, जिससे यह इस विशिष्ट एप्रोक्सिमेशन के लिए निहित $\tilde{O}(n^{2+\epsilon})$ बाधा को पार करने में सक्षम होता है।
सीमित क्लस्टर आकार: बॉल साइज के साथ-साथ क्लस्टर साइज को भी सीमित करने के लिए थुरप और ज़विक की सैंपलिंग का अनुकूलन एक स्ट्रक्चरल योगदान है, जो स्पार्स केस में कुशल गणना को सक्षम बनाता है।

परिणाम
मुख्य प्रमेय बताता है कि एक रैंडमाइज्ड एल्गोरिदम मौजूद है जो, उच्च संभावना के साथ, $\tilde{O}(n^2)$ समय में चलता है और कम से कम एक स्थिरांक $c \ge 0$ की दूरी पर वर्टिसेस के सभी जोड़ों के लिए 2-एप्रोक्सिमेशन की गारंटी देता है। एल्गोरिदम $c$ की दूरी वाले जोड़ों के लिए एक कांस्टेंट एडिटिव एप्रोक्सिमेशन ($|st| + O(1)$) प्राप्त करता है, जो पर्याप्त बड़ी दूरियों के लिए 2-मल्टीप्लिकेटिव एप्रोक्सिमेशन का संकेत देता है।

महत्व
यह शोध पत्र दावा करता है कि यह एक स्थिरांक दूरी वाले सभी जोड़ों के लिए 2-APSP एल्गोरिदम के लिए लगभग द्विघाती रनिंग टाइम वाला एल्गोरिदम डिजाइन करने की समस्या को "लगभग हल" करता है। कॉम्बिनेटोरियल स्ट्रक्चरल इनसाइट्स (लो-डिग्री पाथ्स, बाउंडेड क्लस्टर्स) को फास्ट मैट्रिक्स मल्टीप्लिकेशन की शक्ति के साथ जोड़कर, लेखक $\tilde{O}(n^2)$ समय जटिलता और कांस्टेंट डिस्टेंस जोड़ों को संभालने की आवश्यकता के बीच के अंतर को पाटते हैं, जो कि शुद्ध कॉम्बिनेटोरियल एल्गोरिदम के लिए पहले अप्राप्य था। यह कार्य प्रदर्शित करता है कि इन तकनीकों का संयोजन 2-एप्रोक्सिमेशन के लिए इष्टतम समय जटिलता प्राप्त करने के लिए पर्याप्त है, बशर्ते कि दूरी थ्रेशोल्ड $n$ का फंक्शन होने के बजाय एक स्थिरांक हो।