2025-11-20T02:31:13.678138

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles

Yan

A common step in algorithms related to shortest paths in undirected graphs is that, we select a subset of vertices as centers, then grow a ball around each vertex until a center is reached. We want the balls to be as small as possible. A randomized algorithm can uniformly sample $r$ centers to achieve the optimal (expected) ball size of $Î(n/r)$. A folklore derandomization is to use the $O(\log n)$ approximation for the set cover problem in the hitting set version where we want to hit all the balls with the centers. However, the extra $O(\log n)$ factor is sometimes too expensive. For example, the recent $O(m\sqrt{\log n\log\log n})$ undirected single-source shortest path algorithm [DMSY23] beats Dijkstra's algorithm in sparse graphs, but the folklore derandomization would make it dominated by Dijkstra's. In this paper, we exploit the fact that the sizes of these balls can be adaptively chosen by the algorithm instead of fixed by the input. We propose a simple deterministic algorithm achieving the optimal ball size of $Î(n/r)$ on average. Furthermore, given any polynomially large cost function of the ball size, we can still achieve the optimal cost on average. It allows us to derandomize [DMSY23], resulting in a deterministic $O(m\sqrt{\log n\log\log n})$ algorithm for undirected single-source shortest path. In addition, we show that the same technique can also be used to derandomize the seminal Thorup-Zwick approximate distance oracle [TZ05], also without any loss in the time/space complexity.

academic

अनिर्देशित एकल-स्रोत सबसे छोटे पथ और अनुमानित दूरी ओरेकल के लिए हानिरहित विसंयोजन

मूल जानकारी

पेपर ID: 2510.12598
शीर्षक: अनिर्देशित एकल-स्रोत सबसे छोटे पथ और अनुमानित दूरी ओरेकल के लिए हानिरहित विसंयोजन
लेखक: शुयी यान (BARC, कोपेनहेगन विश्वविद्यालय)
वर्गीकरण: cs.DS (डेटा संरचनाएं और एल्गोरिदम)
प्रकाशन समय: 14 अक्टूबर 2025 (arXiv प्रीप्रिंट)
पेपर लिंक: https://arxiv.org/abs/2510.12598

सारांश

यह पेपर अनिर्देशित ग्राफ सबसे छोटे पथ संबंधित एल्गोरिदम में एक मूल समस्या का अध्ययन करता है: शीर्षों के उपसमुच्चय को केंद्र बिंदु के रूप में कैसे चुनें और प्रत्येक शीर्ष से गेंदें बढ़ाएं जब तक कि केंद्र बिंदु तक न पहुंच जाएं, जिसका लक्ष्य गेंदों का आकार यथासंभव छोटा रखना है। यादृच्छिक एल्गोरिदम r केंद्र बिंदुओं को समान रूप से नमूना करके इष्टतम अपेक्षित गेंद आकार Θ(n/r) प्राप्त कर सकते हैं, लेकिन पारंपरिक विसंयोजन विधियां अतिरिक्त O(log n) कारक का परिचय देती हैं, जो कुछ अनुप्रयोगों में अत्यधिक महंगा है। यह पेपर इस तथ्य का लाभ उठाता है कि गेंद का आकार एल्गोरिदम द्वारा अनुकूल रूप से चुना जा सकता है, और एक सरल नियतात्मक एल्गोरिदम प्रस्तावित करता है जो औसत अर्थ में इष्टतम गेंद आकार Θ(n/r) प्राप्त करता है, और यह मनमाने बहुपद आकार के लागत कार्यों तक विस्तारित हो सकता है। यह तकनीक DMSY23 के O(m√(log n log log n)) एकल-स्रोत सबसे छोटे पथ एल्गोरिदम और शास्त्रीय Thorup-Zwick अनुमानित दूरी ओरेकल को विसंयोजित करने में सफलतापूर्वक लागू होती है, समय/स्पेस जटिलता में कोई नुकसान नहीं।

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

मूल समस्या

यह पेपर वर्धनशील गेंदों को मारने की समस्या (Hitting Growable Balls) को हल करता है। कई ग्राफ एल्गोरिदम में, विशेष रूप से सबसे छोटे पथ, दूरी ओरेकल और विरल सबग्राफ एल्गोरिदम में, निम्नलिखित पैटर्न का सामना करना पड़ता है:

शीर्षों के उपसमुच्चय R को केंद्र बिंदु के रूप में चुनें
प्रत्येक शीर्ष v से गेंद B(v) को तब तक बढ़ाएं जब तक कि कोई केंद्र बिंदु तक न पहुंच जाए
एल्गोरिदम का प्रदर्शन |R| के आकार और सभी गेंदों के आकार के योग पर निर्भर करता है

समस्या की महत्ता

यह समस्या ग्राफ एल्गोरिदम में मौलिक महत्व रखती है, जो कई महत्वपूर्ण एल्गोरिदम की दक्षता को प्रभावित करती है:

एकल-स्रोत सबसे छोटा पथ: DMSY23 एल्गोरिदम विरल ग्राफ पर पहली बार Dijkstra एल्गोरिदम की O(m + n log n) सीमा को तोड़ता है
दूरी ओरेकल: Thorup-Zwick ओरेकल अनुमानित दूरी प्रश्नों के लिए एक शास्त्रीय डेटा संरचना है
ग्राफ विरलीकरण: विरल सबग्राफ बनाते समय भी समान तकनीकें उपयोग की जाती हैं

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

पारंपरिक विसंयोजन विधियों में महत्वपूर्ण खामियां हैं:

लोकप्रिय विधि की लागत: सेट कवर समस्या के O(log n) अनुमान एल्गोरिदम का उपयोग करके विसंयोजन करने से अतिरिक्त O(log n) कारक का परिचय होता है
गंभीर प्रदर्शन हानि: DMSY23 एल्गोरिदम के लिए, यह अतिरिक्त कारक इसकी समय जटिलता को O(m√(log n log log n)) से O(m log n √(log log n)) तक कम कर देता है, जिससे Dijkstra एल्गोरिदम इसे फिर से पार कर जाता है
निश्चित गेंद आकार की धारणा: पारंपरिक विधियां मानती हैं कि गेंद का आकार इनपुट द्वारा निश्चित है, एल्गोरिदम की अनुकूलन क्षमता का उपयोग नहीं कर सकते

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

इस पेपर की मुख्य अंतर्दृष्टि यह है: गेंद का आकार एल्गोरिदम द्वारा अनुकूल रूप से चुना जा सकता है, न कि इनपुट द्वारा निश्चित किया जा सकता है। यह बेहतर विसंयोजन एल्गोरिदम डिजाइन करने के लिए नई संभावनाएं प्रदान करता है।

मूल योगदान

वर्धनशील गेंदों को मारने के लिए नियतात्मक एल्गोरिदम प्रस्तावित किया: Algorithm 1 डिजाइन किया गया है, जो औसत अर्थ में इष्टतम गेंद आकार Θ(n/r) प्राप्त कर सकता है, बिना अतिरिक्त लॉगरिदमिक कारक के
DMSY23 एल्गोरिदम का हानिरहित विसंयोजन प्राप्त किया: यादृच्छिक O(m√(log n log log n)) एकल-स्रोत सबसे छोटे पथ एल्गोरिदम को समान जटिलता के नियतात्मक एल्गोरिदम में परिवर्तित किया
Thorup-Zwick दूरी ओरेकल को विसंयोजित किया: पिछली विसंयोजन विधियों में O(log n) कारक को हटाया, यादृच्छिक संस्करण के समान O(kn^(1/k)(m + n log n)) प्रीप्रोसेसिंग समय प्राप्त किया
सामान्य सैद्धांतिक ढांचा प्रदान किया: विधि मनमाने बहुपद आकार के लागत कार्यों तक विस्तारित हो सकती है, व्यापक प्रयोज्यता के साथ

विधि विस्तार

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

वर्धनशील गेंदों को मारने की समस्या का औपचारिक परिभाषा निम्नलिखित है:

इनपुट: n शीर्ष, m प्रारंभिक रूप से खाली गेंदें, पैरामीटर r ∈ 1,n, लागत कार्य f(·)
संचालन: एल्गोरिदम एक गेंद चुन सकता है और विरोधी को इसमें एक नया शीर्ष जोड़ने के लिए कह सकता है
लक्ष्य: r शीर्षों को केंद्र के रूप में चुनें ताकि प्रत्येक गेंद मारी जाए (कम से कम एक केंद्र शामिल हो), कुल लागत ∑f(|Bi|) को कम करें

मूल एल्गोरिदम आर्किटेक्चर

Algorithm 1 इस पेपर का मूल योगदान है:

Algorithm 1: वर्धनशील गेंदों को मारना
इनपुट: शीर्षों की संख्या n, गेंदों की संख्या m, लक्ष्य केंद्र संख्या r, लागत पैरामीटर p
आउटपुट: सभी गेंदों को मारने वाले अधिकतम r केंद्र

1: सभी गेंदों को खाली के रूप में प्रारंभ करें, कोई केंद्र चुना नहीं गया
2: b ← ⌈2^(p+2)n/r⌉
3: प्रत्येक गेंद को आकार min{b, n} तक बढ़ाएं
4: जबकि सभी गेंदें मारी न जाएं do
5:   m' ← अमारी गई गेंदों की संख्या
6:   सबसे अधिक अमारी गई गेंदों को मारने वाले नए केंद्रों को दोहराएं चुनें,
     जब तक अमारी गई गेंदों की संख्या ≤ m'/2^(p+1)
7:   b ← 2b
8:   प्रत्येक अमारी गई गेंद को आकार min{b, n} तक बढ़ाएं
9: सभी चुने गए केंद्रों को लौटाएं

एल्गोरिदम की मूल अवधारणा

घातीय ह्रास रणनीति: i-वें दौर में, केवल O(r/2^i) केंद्रों का उपयोग करें, लेकिन गेंदों को 2^i n/r तक बढ़ने दें
संतुलन व्यापार: हालांकि बाद के दौर में गेंदें बड़ी होती हैं, लेकिन अमारी गई गेंदों की संख्या घातीय रूप से घटती है
अनुकूल वृद्धि: वर्तमान अमारी गई गेंदों की स्थिति के आधार पर गेंद के आकार को गतिशील रूप से समायोजित करें

सैद्धांतिक विश्लेषण

Theorem 4 एल्गोरिदम की सही्ता को प्रमाणित करता है:

केंद्र संख्या: अधिकतम r केंद्र चुनें
कुल लागत: O_p(m(n/r)^p) = O_p(m·f(n/r))
समय जटिलता: O_p(r + mn/r)

प्रमाण के मुख्य बिंदु:

प्रत्येक दौर में केंद्र संख्या की ऊपरी सीमा विश्लेषण
अमारी गई गेंदों की संख्या का घातीय ह्रास
ज्यामितीय श्रृंखला योग के माध्यम से कुल लागत सीमा प्राप्त करना

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

सैद्धांतिक सत्यापन

यह पेपर मुख्य रूप से सैद्धांतिक कार्य है, कठोर गणितीय प्रमाण के माध्यम से एल्गोरिदम की सही्ता और जटिलता सीमा को सत्यापित करता है।

अनुप्रयोग सत्यापन

दो विशिष्ट अनुप्रयोगों के माध्यम से विधि की प्रभावशीलता को सत्यापित किया:

एकल-स्रोत सबसे छोटा पथ:
- Algorithm 1 को DMSY23 के bundle construction चरण में एकीकृत करें
- लागत कार्य को f(x) = x log x के रूप में सेट करें
- पैरामीटर चयन r = m√(log log n)/√(log n)
Thorup-Zwick दूरी ओरेकल:
- प्रत्येक स्तर i में A_{i+1} चुनने के लिए Algorithm 1 लागू करें
- RTZ05 की तकनीक के साथ संयोजित करके कुशल गेंद वृद्धि संचालन को लागू करें
- पैरामीटर सेटिंग r = n^(-1/k)|A_i|

कार्यान्वयन विवरण

डेटा संरचना अनुकूलन:

प्रत्येक शीर्ष j द्वारा मारी जा सकने वाली अमारी गई गेंदों की संख्या a_j को बनाए रखें
द्विदिशीय सूची L_k का उपयोग करके a_j = k वाले शीर्षों को बनाए रखें
O(1) समय में सम्मिलन, विलोपन और अधिकतम मान खोजने का समर्थन करें

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

मुख्य परिणाम

Theorem 2 (एकल-स्रोत सबसे छोटा पथ):

गैर-नकारात्मक किनारे भार वाले अनिर्देशित ग्राफ में, एक नियतात्मक तुलना-जोड़ एल्गोरिदम मौजूद है
समय जटिलता: O(m√(log n log log n))
DMSY23 के यादृच्छिक एल्गोरिदम की जटिलता के समान

Theorem 3 (Thorup-Zwick ओरेकल):

आकार O(kn^{1+1/k}) का Thorup-Zwick अनुमानित दूरी ओरेकल
O(kn^{1/k}(m + n log n)) समय में नियतात्मक रूप से निर्मित किया जा सकता है
मूल यादृच्छिक एल्गोरिदम की प्रीप्रोसेसिंग समय के समान

जटिलता तुलना

एल्गोरिदम	प्रकार	समय जटिलता	टिप्पणी
Dijkstra	नियतात्मक	O(m + n log n)	शास्त्रीय एल्गोरिदम
DMSY23	यादृच्छिक	O(m√(log n log log n))	पहली बार Dijkstra को तोड़ता है
DMSY23+लोकप्रिय विसंयोजन	नियतात्मक	O(m log n √(log log n))	Dijkstra द्वारा पार किया गया
यह पेपर	नियतात्मक	O(m√(log n log log n))	हानिरहित विसंयोजन

तकनीकी नवाचार सत्यापन

Corollary 5 विभिन्न लागत कार्यों के लिए विधि की प्रयोज्यता को प्रदर्शित करता है:

f(x) = x log x के लिए, Jensen असमानता के अनुप्रयोग के माध्यम से
कुल लागत सीमा: O(m(n/r)log(n/r))
अन्य बहुपद आकार के लागत कार्यों तक विस्तारित हो सकता है

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

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

सैद्धांतिक सफलता: गेंदों को मारने की समस्या का पहली बार हानिरहित विसंयोजन, औसत अर्थ में इष्टतम सीमा प्राप्त करता है
व्यावहारिक अनुप्रयोग: दो महत्वपूर्ण ग्राफ एल्गोरिदम में सफलतापूर्वक लागू, यादृच्छिक संस्करण के समान जटिलता बनाए रखता है
सामान्य ढांचा: विभिन्न लागत कार्यों के लिए लागू सामान्य विधि प्रदान करता है

सीमाएं

मॉडल धारणाएं:
- ग्राफ की डिग्री O(m/n) होने की आवश्यकता है (शीर्ष विभाजन के माध्यम से प्राप्त)
- तुलना-जोड़ मॉडल की आवश्यकता है
- DMSY23 अनुप्रयोग के लिए, स्थिर डिग्री ग्राफ मान लें
प्रयोज्यता की सीमा:
- मुख्य रूप से उन परिस्थितियों में लागू होता है जहां गेंद का आकार अनुकूल रूप से चुना जा सकता है
- उन स्थितियों में लागू नहीं है जहां गेंद का आकार पूरी तरह से इनपुट द्वारा निश्चित है
व्यावहारिक दक्षता:
- हालांकि渐近 जटिलता इष्टतम है, लेकिन छिपे हुए स्थिरांक बड़े हो सकते हैं
- छोटे ग्राफ पर सरल यादृच्छिकीकरण विधियों से बेहतर नहीं हो सकता है

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

एल्गोरिदम अनुकूलन:
- एल्गोरिदम में स्थिरांक कारकों को कम करें
- अधिक व्यावहारिक कार्यान्वयन संस्करण डिजाइन करें
अनुप्रयोग विस्तार:
- अन्य ग्राफ एल्गोरिदम में अनुप्रयोग की खोज करें
- गतिशील ग्राफ सेटिंग में विस्तार का अनुसंधान करें
सैद्धांतिक गहनता:
- निचली सीमाओं का अनुसंधान करें, विधि की इष्टतमता को प्रमाणित करें
- अधिक सामान्य लागत कार्यों तक विस्तार करें

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

शक्तियां

तकनीकी नवाचार:
- पहली बार गेंद की वर्धनशील संपत्ति का उपयोग करके हानिरहित विसंयोजन प्राप्त किया
- एल्गोरिदम डिजाइन सरल और चतुर है, घातीय ह्रास रणनीति बहुत रचनात्मक है
सैद्धांतिक योगदान:
- कठोर गणितीय प्रमाण, पूर्ण सैद्धांतिक विश्लेषण
- सामान्य ढांचा प्रदान करता है, विभिन्न लागत कार्यों के लिए लागू
व्यावहारिक महत्व:
- DMSY23 जैसे महत्वपूर्ण एल्गोरिदम की विसंयोजन समस्या को हल करता है
- Thorup-Zwick ओरेकल में सुधार मौलिक मूल्य रखता है
स्पष्ट अभिव्यक्ति:
- पेपर संरचना स्पष्ट है, तकनीकी विवरण सटीक है
- एल्गोरिदम छद्मकोड सरल और समझने में आसान है

कमियां

प्रायोगिक सत्यापन की कमी:
- शुद्ध सैद्धांतिक कार्य, वास्तविक प्रदर्शन परीक्षण की कमी है
- अन्य विधियों के साथ अनुभवजन्य तुलना नहीं है
स्थिरांक कारक विश्लेषण:
- हालांकि渐近इष्टतम है, लेकिन छिपे हुए स्थिरांक बड़े हो सकते हैं
- व्यावहारिक अनुप्रयोग में दक्षता सत्यापन की आवश्यकता है
अनुप्रयोग की सीमा:
- मुख्य रूप से विशिष्ट प्रकार की समस्याओं के लिए लक्षित
- सामान्य विसंयोजन समस्याओं के लिए सीमित मार्गदर्शन

प्रभाव

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

उपयुक्त परिदृश्य

सैद्धांतिक अनुसंधान: अन्य यादृच्छिक एल्गोरिदम के विसंयोजन के लिए संदर्भ
प्रणाली अनुप्रयोग: नियतात्मक व्यवहार की आवश्यकता वाली प्रणालियों में यादृच्छिक एल्गोरिदम को प्रतिस्थापित करें
शिक्षण उद्देश्य: विसंयोजन तकनीकों का उत्कृष्ट उदाहरण

संदर्भ

पेपर संबंधित कार्यों के समृद्ध संदर्भों का हवाला देता है, मुख्य रूप से:

DMSY23: Duan et al. का यादृच्छिक एकल-स्रोत सबसे छोटे पथ एल्गोरिदम
TZ05: Thorup-Zwick अनुमानित दूरी ओरेकल का मूल कार्य
RTZ05: Roditty et al. का विसंयोजन सुधार
Dij59: Dijkstra का शास्त्रीय सबसे छोटे पथ एल्गोरिदम
FT87: Fibonacci ढेर संबंधित कार्य

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