💻 computer science

Graph Partitioning with Demands: Generalized Conductance and its Applications

यह शोध पत्र एक सामान्य मांग मॉडल (demand model) के तहत ग्राफ विभाजन के लिए 'सामान्यीकृत कंडक्टेंस समस्या' (Generalized Conductance Problem) प्रस्तुत करता है और एक $\mathcal{O}(\log n)$ -अनुमानित एल्गोरिदम (approximation algorithm) पेश करता है जो 'डिमांड के साथ ग्राफ विभाजन' (Graph Partitioning with Demands) और 'डिमांड के साथ पदानुक्रमित क्लस्टरिंग' (Hierarchical Clustering with Demands) के लिए द्वि-मानदंड अनुमानों (bicriteria approximations) तक विस्तृत है, जिसमें मल्टीप्लिकेटिव डिमांड्स और ट्रीज़ (trees) के लिए बेहतर गारंटी दी गई है।

मूल लेखक: Michał Szyfelbein, Dariusz Dereniowski

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

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

CC BY 4.0

मूल लेखक: Michał Szyfelbein, Dariusz Dereniowski

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

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

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

हालाँकि, इस पहेली का क्लासिक संस्करण यह मानता है कि सभी लोग एक-दूसरे से समान रूप से बात करना चाहते हैं, या कनेक्शन का "महत्व" केवल एक साधारण संख्या है। लेकिन वास्तविक दुनिया में, मांगें अव्यवस्थित होती हैं। कभी-कभी द्वीपों का एक पूरा समूह एक एकल इकाई के रूप में कार्य करता है, या कनेक्शन का महत्व विशिष्ट जोड़ी के आधार पर बदल जाता है। यह शोध पत्र, जिसका शीर्षक "ग्राफ पार्टीशनिंग विद डिमांड्स" (Graph Partitioning with Demands) है, इस अधिक जटिल संस्करण को संबोधित करता है जिसे जनरलाइज्ड कंडक्टेंस (Generalized Conductance) कहा जाता है। यहाँ, लक्ष्य केवल स्लाइस के आकार को संतुलित करना नहीं है, बल्कि उनमें बहने वाली कुल मांग को संतुलित करना है। लेखक पूछते हैं: हम एक जटिल, भारी मांग वाले शहर को उचित मोहल्लों में कैसे विभाजित कर सकते हैं बिना पुलों को तोड़ने में एक बड़ी कीमत चुकाए?

मुख्य विचार: एक दो-तरफा हमला

लेखक, मिचाऊ शिफ़ेलबीन (Michał Szyfelbein) और डेरियस डेरेनिएव्स्की (Dariusz Dereniowski), जो ग्डान्स्क यूनिवर्सिटी ऑफ टेक्नोलॉजी से हैं, ने महसूस किया कि इन ग्राफ्स को काटने के पुराने तरीके इस नई, अव्यवस्थित वास्तविकता के लिए सही नहीं थे। उन्होंने एक नया तरीका पेश किया जिससे यह मापा जा सके कि एक कट कितना "अच्छा" है, जिसे वे जनरलाइज्ड कंडक्टेंस कहते हैं। इसे एक स्कोरकार्ड के रूप में समझें: आप एक कम स्कोर चाहते हैं, जिसका अर्थ है कि आपने सस्ते पुल काटे (कम लागत) लेकिन मोहल्लों के भीतर मांगों का भारी ट्रैफ़िक (उच्च आंतरिक मांग) बनाए रखा।

इसे हल करने के लिए, उन्होंने केवल एक जादुई हथौड़ा नहीं बनाया। इसके बजाय, उन्होंने एक चतुर दो-तरफा जाल बनाया। उन्होंने महसूस किया कि इस तरह की कोई भी ग्राफ समस्या दो समूहों में से एक में आती है, और प्रत्येक के लिए उनकी एक अलग रणनीति है:

"बिग कट" (Big Cut) समूह: कभी-कभार, शहर को विभाजित करने का सबसे अच्छा तरीका एक साथ बहुत अधिक मांग को काटना होता है। इस परिदृश्य में, समस्या k-मल्टीकट (k-Multicut) नामक एक ज्ञात पहेली जैसी दिखती है। लेखक यहाँ एक ऐसी रणनीति का उपयोग करते हैं जो पर्याप्त मांग को काटती है ताकि शहर को अलग किया जा सके, लेकिन फिर वे एक "मैक्स-कट" (Max-Cut) ट्रिक (जैसे कि खींचतान का एक लालची खेल) का उपयोग करते हैं ताकि यह सुनिश्चित हो सके कि परिणामी हिस्से अभी भी उचित रूप से संतुलित हों।
"स्मॉल कट" (Small Cut) समूह: कभी-कभी, सबसे अच्छा विभाजन बहुत कम मांग को काटकर होता है। इस मामले में, समस्या जनरलाइज्ड स्पारसेस्ट कट जैसी दिखती है, लेकिन एक सख्त नियम के साथ: आप बहुत अधिक मांग नहीं काट सकते। इसे हल करने के लिए, वे पेड़ों (trees) से जुड़ी एक गणितीय "जादुई ट्रिक" का उपयोग करते हैं। वे कल्पना करते हैं कि वे जटिल शहर के मानचित्र को एक सरल पेड़ की संरचना (जैसे कि एक वंशावली) में बदल रहे हैं जहाँ कनेक्शनों का विश्लेषण करना आसान है। वे पेड़ों पर समस्या को हल करते हैं और फिर समाधान को वास्तविक शहर पर वापस मैप करते हैं।

दोनों रणनीतियों को चलाकर और बेहतर परिणाम चुनकर, वे गारंटी देते हैं कि उनका समाधान कभी भी आदर्श, असंभव-से-खोजने वाले समाधान से केवल एक लॉगरिदमिक कारक (लगभग O(log n)) खराब नहीं होगा। पेड़ों के लिए, समाधान सटीक (constant factor) है। यदि मांगें एक विशिष्ट गणितीय पैटर्न (multiplicative) का पालन करती हैं, तो वे इससे भी बेहतर कर सकते हैं, जिससे O(√log n) की गारंटी मिलती है।

यह क्यों मायने रखता है: स्लाइस से लेकर पदानुक्रम तक

यह शोध पत्र केवल एक अच्छा स्लाइस खोजने तक ही सीमित नहीं है। लेखक दिखाते हैं कि यह नया "जनरलाइज्ड कंडक्टेंस" उपकरण अन्य समस्याओं के लिए एक स्विस आर्मी नाइफ की तरह है।

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

दूसक, और शायद सबसे रोमांचक, वे इसका उपयोग Hierarchical Clustering with Demands को हल करने के लिए करते हैं। यह एक लाइब्रेरी को केवल दो कमरों में नहीं, बल्कि शेल्फ, दराज और बक्सों के एक पूरे पदानुक्रम (hierarchy) में व्यवस्थित करने जैसा है। आप पूरी लाइब्रेरी से शुरू करते हैं, उसे दो भागों में विभाजित करते हैं, फिर उन दो को विभाजित करते हैं, और इसी तरह चलते रहते हैं, जब तक कि हर किताब अकेली न हो जाए। लक्ष्य यह सुनिश्चित करना है कि जो किताबें अक्सर एक साथ उधार ली जाती हैं, वे लंबे समय तक एक ही बॉक्स में रहें। लेखक दिखाते हैं कि उनके नए कटिंग टूल का बार-बार उपयोग करके, वे इस पूरे पदानुक्रम को सर्वोत्तम संभव व्यवस्था के बहुत अच्छे अनुमान के साथ बना सकते हैं।

निष्कर्ष

यह शोध पत्र सिद्ध करता है कि सामान्य ग्राफों के लिए, आप सर्वोत्तम संभव कट के O(log n) कारक के भीतर एक समाधान प्राप्त कर सकते हैं। पेड़-नुमा नेटवर्क के लिए, यह और भी बेहतर है, जो एक कांस्टेंट-फैक्टर सन्निकटन (constant-factor approximation) देता है। यदि मांगें "मल्टीप्लिकेटिव" (एक विशिष्ट गणितीय संबंध) हैं, तो गारंटी O(√log n) में सुधर जाती है।

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

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

तकनीकी सारांश: मांगों के साथ ग्राफ विभाजन: सामान्यीकृत कंडक्टेंस (Generalized Conductance) और इसके अनुप्रयोग

समस्या की परिभाषा
यह कार्य एक सामान्य मांग मॉडल (demand model) के तहत ग्राफ विभाजन समस्याओं को संबोधित करता है। इनपुट एक ग्राफ $G = (V, E, c, w)$ है, जहाँ $c: E \to \mathbb{N}$ एक क्षमता फलन (capacity function/edge costs) है और $w: V \times V \to \mathbb{N}$ एक मांग फलन है जो शीर्ष युग्मों (vertex pairs) को अलग करने के महत्व को दर्शाता है।

प्रस्तुत मुख्य समस्या सामान्यीकृत कंडक्टेंस समस्या (Generalized Conductance Problem) है। इसका लक्ष्य एक कट $(S, \bar{S})$ खोजना है जो इस मात्रा को कम करता हो:
$\psi_w(S) = \frac{c(S, \bar{S})}{w(S, V) \cdot w(\bar{S}, V)}$
जहाँ $c(S, \bar{S})$ कट को पार करने वाले किनारों (edges) की लागत है, और $w(X, V) = w(X) + w(X, \bar{X})$ सेट $X$ से जुड़ी कुल मांग (आंतरिक और क्रॉसिंग दोनों) को दर्शाता है।

लेखक ध्यान देते हैं कि जबकि क्लासिक स्पारसेस्ट कट (Sparsest Cut - $c(S, \bar{S}) / w(S, \bar{S})$ को न्यूनतम करना) अच्छी तरह से अध्ययन किया गया है, यह सामान्य मांग सेटिंग्स में "संतुलन" (balance) को पकड़ने में विफल रहता है। उदाहरण के लिए, एक पूर्णतः संतुलित कट जिसमें क्रॉसिंग डिमांड शून्य है, एक स्पारसेस्ट कट का मान अनंत देता है, जबकि सामान्यीकृत कंडक्टेंस परिमित (finite) और सार्थक रहता है। यह मीट्रिक डिवाइड-एंड-कॉन्कर (divide-and-conquer) जैसी रणनीतियों के लिए महत्वपूर्ण है, जिनमें संतुलित विभाजन की आवश्यकता होती है।

कार्यप्रणाली और एल्गोरिद्मिक ढांचा
पेपर सामान्यीकृत कंडक्टेंस समस्या को हल करने के लिए एक दो-तरफा रिडक्शन (reduction) रणनीति प्रस्तावित करता है, जिसके परिणामस्वरूप सामान्य ग्राफों के लिए $O(\log n)$ -अनुमान (approximation) प्राप्त होता है। एल्गोरिदम दो संभावित कट्स, $S_1$ और $S_2$ , की गणना करता है, और बेहतर ऑब्जेक्टिव वैल्यू वाला कट वापस करता है। चुनाव इष्टतम कट द्वारा पार की गई मांग $w(S^*, \bar{S}^*)$ के परिमाण पर निर्भर करता है।

केस 1: छोटी क्रॉसिंग डिमांड ( $w(S^*, \bar{S}^*) \le w(V)/3$ )
- रिडक्शन: समस्या को सामान्यीकृत स्पारसेस्ट $K$ -बाउंडेड कट (Generalized Sparsest $K$ -Bounded Cut) समस्या में बदला जाता है।
- तकनीक: एक सहायक ग्राफ $G'$ बनाया जाता है जिसमें सभी मूल शीर्षों (vertices) से शून्य-लागत वाले किनारों के साथ एक यूनिवर्सल वर्टेक्स $r$ जोड़ा जाता है। $r$ से किसी भी वर्टेक्स $u$ तक की मांग को मूल ग्राफ में $u$ से जुड़ी कुल मांग के रूप में सेट किया जाता है।
- प्रतिबंध: एल्गोरिदम $G'$ में एक कट के लिए समाधान खोजता है जो कुल कट डिमांड पर $K = \frac{4}{3}w(V)$ के ऊपरी बंधन के अधीन स्पर्सिटी (sparsity) को कम करता है। यह प्रतिबंध सुनिश्चित करता है कि ट्रिवियल कट ( $S=V$ ) नहीं चुना जाए और एक संतुलित विभाजन को मजबूर करे।
- सबरूटीन: यह चरण स्पारसेस्ट $K$ -बाउंडेड कट के लिए एक $\alpha$ -अनुमान का उपयोग करता है।
केस 2: बड़ी क्रॉसिंग डिमांड ( $w(S^*, \bar{S}^*) \ge w(V)/3$ )
- रिडक्शन: समस्या को सामान्यीकृत $k$ -मल्टीकट (Generalized $k$ -Multicut) समस्या और उसके बाद एक मैक्स-कट (Max-Cut) चरण में बदला जाता है।
- तकनीक: पहले, एक महत्वपूर्ण हिस्से की मांग को अलग करने के लिए $k = w(V)/3$ के साथ एक $k$ -मल्टीकट की गणना की जाती है, जिससे कनेक्टेड कंपोनेंट्स (connected components) का एक सेट प्राप्त होता है।
- रिफाइनमेंट: ये कंपोनेंट्स एक नए पूर्ण ग्राफ (complete graph) $R$ के वर्टेक्स बनाते हैं, जहाँ किनारों के भार कंपोनेंट्स के बीच की मांग को दर्शाते हैं। $R$ पर एक मैक्स-कट की गणना की जाती है (एक ग्रीडी 2-अनुमान का उपयोग करके) ताकि कंपोनेंट्स को दो समूहों में विभाजित किया जा सके।
- सबरूटीन: यह चरण सामान्यीकृत $k$ -मल्टीकट के लिए $\beta$ -अनुमान का उपयोग करता है।

उप-समस्याओं को हल करना
अंतिम अनुमान गारंटी प्राप्त करने के लिए, पेपर रैके (Räcke) के कट-स्पारसिफायर ट्री डीकंपोजिशन (cut-sparsifier tree decomposition) का उपयोग करता है।

सामान्य ग्राफ को बहुपदीय (polynomial) संख्या में पेड़ों के एक संभाव्यता वितरण (probability distribution) में एम्बेड किया जाता है।
यह एम्बेडिंग अपेक्षा (expectation) में $O(\log n)$ विरूपण (distortion) के भीतर कट मानों को संरक्षित करता है।
एल्गोरिदम वितरण के सपोर्ट में प्रत्येक पेड़ पर उप-समस्याओं को इष्टतम रूप से हल करता है।
पेड़ों पर, ये समस्याएं सिंगल-एज कट (single-edge cuts) पर विचार करके बहुपद समय (अक्सर लीनियर) में हल की जा सकती हैं।
वितरण के सभी पेड़ों में से सर्वश्रेष्ठ समाधान चुना जाता है, जो सामान्य ग्राफों के लिए $O(\log n)$ अनुमान प्रदान करता है।

मुख्य परिणाम
पेपर निम्नलिखित अनुमान गारंटी स्थापित करता है:

सामान्यीकृत कंडक्टेंस (Generalized Conductance):
- सामान्य ग्राफ: $O(\log n)$ -अनुमान।
- वृक्ष (Trees): $O(1)$ -अनुमान (सटीक समाधान क्षमता)।
- मल्टीप्लिकेटिव डिमांड्स: यदि $w(u, v) = \pi(u)\pi(v)$ , तो गारंटी सुधरकर $O(\sqrt{\log n})$ हो जाती है। यह समस्या को मिन-रेशियो वर्टेक्स कट (Min-Ratio Vertex Cut) समस्या में बदलकर प्राप्त किया जाता है।
मांगों के साथ ग्राफ विभाजन (Graph Partitioning with Demands):
- लक्ष्य: एक ऐसा न्यूनतम-लागत किनारा सेट $C$ खोजना कि $G \setminus C$ में प्रत्येक कनेक्टेड कंपोनेंट $H$ इस प्रकार हो कि $w(H) \le \rho \cdot w(V)$ ।
- परिणाम: एक $O(\log n)$ -बाइक्राइटेरिया (bicriteria) अनुमान प्राप्त किया जाता है। एल्गोरिदम एक कट लौटाता है जिसकी लागत $O(\log n) \cdot \text{OPT}$ है, जबकि यह सुनिश्चित करता है कि कंपोनेंट डिमांड $\eta \cdot w(V)$ से अधिक न हो (जहाँ $\rho < \eta < 1$ )।
- मल्टीप्लिकेटिव/वृक्ष: गारंटी क्रमशः $O(\sqrt{\log n})$ और $O(1)$ तक सुधर जाती है।
मांगों के साथ पदानुक्रमित क्लस्टरिंग (Hierarchical Clustering with Demands):
- लक्ष्य: दासगुप्ता (Dasgupta) के ऑब्जेक्टिव (क्लस्टर डिमांड द्वारा भारित कट लागतों का योग) को कम करना, ग्राफ को पुनरावर्ती रूप से विभाजित करके।
- परिणाम: ग्राफ विभाजन एल्गोरिदम को बार-बार लागू करके, पेपर सामान्य ग्राफों के लिए $O(\log n)$ -अनुमान, वृक्षों के लिए $O(1)$ , और मल्टीप्लिकेटिव डिमांड्स के लिए $O(\sqrt{\log n})$ अनुमान प्राप्त करता है।

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

यह कार्य प्रदर्शित करता है कि सामान्य डिमांड की जटिलता के बावजूद, समस्या लॉगरिदमिक अनुमान कारकों के साथ सुलभ (tractable) बनी रहती है। पेपर स्पष्ट रूप से दावा करता है कि ये परिणाम पदानुक्रमित क्लस्टरिंग जैसे डाउनस्ट्रीम कार्यों तक विस्तारित होते हैं, जो सामान्य डिमांड मॉडल के तहत इन समस्याओं के लिए पहले गैर-तुच्छ (non-trivial) अनुमान गारंटी प्रदान करते हैं। लेखक नोट करते हैं कि मल्टीप्लिकेटिव डिमांड्स के लिए, परिणाम यूनिफॉर्म स्पारसेस्ट कट के स्टेट-ऑफ-द-आर्ट के अनुरूप हैं, और वृक्षों के लिए, वे निरंतर-कारक (constant-factor) अनुमान प्राप्त करते हैं।

पेपर भविष्य की दिशाओं का सुझाव देते हुए समाप्त होता है, जिसमें हाइपरग्राफ (hypergraph) तक ढांचे का विस्तार करना (जिसके लिए एक नए हाइपरग्राफ कंडक्टेंस की आवश्यकता होगी) और स्पेक्ट्रल ग्राफ थ्योरी के साथ संबंधों की खोज करना शामिल है, विशेष रूप से यह कि क्या एक सामान्यीकृत लैपलेसियन (generalized Laplacian), क्लासिक चीगर इनइक्वलिटी (Cheeger inequality) की तरह सामान्यीकृत कंडक्टेंस से संबंधित हो सकता है।

मुख्य विचार: एक दो-तरफा हमला

यह क्यों मायने रखता है: स्लाइस से लेकर पदानुक्रम तक

निष्कर्ष

इसी तरह के और पेपर