K برش کمینه

در ریاضیات، مسئلهٔ حداقل k برش، یک مسئلهٔ بهینه‌سازی ترکیبیاتی است که به یافتن یک مجموعه از یال‌ها اشاره دارد که حذف این مجموعه، گراف را به حداقل k مولفهٔ همبندی تقسیم‌بندی کند. به این یال‌ها k-برش گفته می‌شود و به یالی که حذف آن باعث افزایش مولفه‌های همبندی شود پل (نظریه گراف) گفته می‌شود. این مسئله زیرمجموعه و مشتق شدهٔ مسئلهٔ حداقل برش است که کارکرد جزئی تری نسبت به مسئله اصلی دارد. هدف یافتن k-برش با وزن کمینه است. این تقسیم‌بندی می‌تواند کاربردهایی در طراحی وی‌ال‌اس‌آی، داده کاوی، روش اجزاء محدود و ارتباطات در رایانش موازی داشته باشد.

مسئله حداقل k برش به دنبال یافتن مجموعه ای از k یال با وزن کمینه است که با حذف این یال‌ها گراف به k مؤلفه همبندی تبدیل شود.

تعریف رسمی

گراف بدون جهت G = (E, V) و عدد k ∈ {۲, ۳, …, |V|} داده شده‌است. به هر یال گراف G یک‌وزن w: E → N اختصاص یافته‌است. V را به k مجموعه جدا تقسیم‌بندی کنید در حالی که عبارت زیر کمینه شود

$\sum _{i=1}^{k-1}\sum _{j=i+1}^{k}\sum _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})$

برای k ثابت، این مسئله، مسئله زمان چند جمله ای است که در O(|V|^k2)قابل حل است. با این حال، اگر k بخشی از ورودی باشد، مسئله به یک مسئلهٔ NP کامل است. در صورتی که ما k رأس را مشخص کنیم و کمترین k برش برای جدا کردن این k رأس را بخواهیم این مسئله بازهم یک مسئلهٔ NP کامل خواهد شد.

کاربرد

کمترین برش هنگامی اهمیت پیدا می‌کند که گرافی بسیار بزرگ در اختیار داشته باشیم و بخواهیم آن را مورد بررسی قرار دهیم. در این حالت بررسی کل گراف به صورت کلی کاربردی نخواهد بود و ما در تلاشیم با تقسیم گراف به صورت معقول و عملی هزینه اجرای الگوریتم‌های گراف را بر روی تمام داده‌های خود بهینه کنیم. با تقسیم گراف به مؤلفه‌های همبندی، اصطلاحاً تعدادی تکه شکسته خواهیم داشت که به معنای سهولت قراردهی داده‌ها در سرورهای مختلف خواهد بود.

مسئلهٔ k برش کمینه در حوزه‌های متنوعی که موضوع شبکه مطرح می‌شود، کاربرد دارد، به عنوان مثال از آن برای تقسیم‌بندی گروه‌های علاقه‌مندی در شبکه‌های اجتماعی یا برای یافتن ضعیف‌ترین اتصالات در شبکه‌های مخابراتی یا در یافتن خلوت‌ترین معابر در شبکه‌های ترافیکی استفاده می‌شود.

الگوریتم‌های تقریبی

چندین الگوریتم تقریبی با تقریب 2 - 2/k وجود دارد. یک الگوریتم حریصانه ساده با این عامل تقریبی این است که حداقل برش در هر یک از اجزای متصل(مؤلفه همبندی) را محاسبه می‌کند و سنگین‌ترین را حذف می‌کند. این الگوریتم به‌طور کلی به n-1 بار محاسبه بیشینه جریان دارد. الگوریتم دیگری برای دستیابی به همان تقریب از نمای درخت گوموری‌هو از حداقل برش‌ها استفاده می‌کند. ساخت درخت گوموری‌هو به n-1 بار محاسبه جریان بیشینه احتیاج دارد که الگوریتم آن با محاسبه کلی بیشینه جریان از O(kn(انجام می‌دهد. با این حال، تجزیه و تحلیل عامل تقریب الگوریتم دوم آسان‌تر است. علاوه بر این، تحت فرضیه گسترش مجموعه کوچک (حدسی بسیار مرتبط با حدس بازی منحصر به فرد)، مسئله تقریباً نزدیک به NP است با عامل $(2-\epsilon )$ برای هر ثابت $\epsilon >0$. این به معنای آن است که الگوریتم‌های تقریبی فوق‌الذکر در اصل برای kهای بزرگ به جواب اصلی نزدیک تر هستند.

یکی از انواع مسائل یافتن کمترین وزن k-برش است هنگامی که مولفه‌های همبندی پس از اعمال برش‌ها اندازهٔ از پیش تعیین شده داشته باشند. اگر یک نمودار را به یک فضای متریک محدود کنید، به این معنی است که در یک عامل ۳ برای هر k ثابت وجود دارد، به این معنی که یک نمودار کامل که نابرابری مثلث را برآورده می‌کند. اخیراً، طرح‌های تقریبی زمان چند جمله ای (PTAS) برای آن مسائل کشف شده‌اند.

الگوریتم حریصانه

الگوریتم مورد نظر توسط Mikkel Thorup پیشنهاد شده‌است.

استفاده از الگوریتم حریصانه به عنوان یک راه حل (نه همیشه بهینه) برای این مسئله تلقی می‌شود. الگوریتم به‌طور کلی به این صورت تعریف می‌شود که در هر مرحله از k مرحله یال با کمترین ارزش را حذف می‌کنیم به طوری که حذف این یال تعداد مولفه‌های همبندی را به تعداد ۱ واحد اضافه کند.

توضیح دقیق

برای a>0 و 0.9>a اگر T یک مجموعه از درخت‌های حریصانه با حداقل 3m(k/a)³ln(nmk/a) درخت باشد - به طوری که m تعداد یال‌ها و n تعداد رأس‌های درخت است - در حالت میانگین درختان T از هر یال از یال‌های مطلوب را در کمتر 2(k-1+2a) بار می‌گذرند. برای a=۱/۴ از هر یال حداکثر 2k-۲ بار توسط برخی درختان T استفاده می‌شود. با فرض a = ۱/۴ مراحل الگوریتم به این صورت خواهد بود:

• ساخت مجموعه درخت حریصانه T
• جمع‌آوری همه یال‌های برشی که کمتر از 2k-۲ بار و حداقل ۱ بار از آن‌ها در درختان استفاده شده‌است.
• انتخاب کمترین یال‌ها به طوری که حاصل تبدیل به k مؤلفه همبندی شود.

پیچیدگی زمانی

در این الگوریتم برای محاسبه پیچیدگی زمانی از تابع soft_O استفاده خواهد شد.

• برای ساخت مجموعه درخت 3m(k/a)³ln(nmk/a)=soft-O(mk³)
• تمام احتمالات برای یال‌های مورد نظر در بخش دوم از توزیع Binom(n-1, 2k-2) پیروی می‌کنند که برابر soft-O(((en/(2k-2))^)2k-2) احتمال برای هر برش است.
• بخش‌بندی به k مجموعه حداکثر k^(2k-1)/k حالت متفاوت دارد که برابر است با soft-O((ek)^(k-1)).

به‌طور کل پیچیدگی زمانی مقدار soft-O(n^(2k)) را خواهد داشت.

راه حل ساده‌تر

می‌توان در هر مرحله کل گراف را پیمایش کرد و کم وزن‌ترین یال مطلوب برای برش را یافت و آن را حذف کرد تا به k مؤلفه همبندی برسیم.

کد الگوریتم بدیهی در زبان c++

#include "paal/greedy/k_cut/k_cut.hpp"
#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
    // sample data
    std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
        {3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
    std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
    boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                    boost::no_property,
                    boost::property<boost::edge_index_t, std::size_t>
                    > graph(8);
    for (std::size_t i = 0; i < edges_p.size(); ++i) {
        add_edge(edges_p[i].first, edges_p[i].second, i, graph);
    }
    const int parts = 3;
    auto edge_id = get(boost::edge_index, graph);
    auto weight = make_iterator_property_map(costs.begin(), edge_id);
    // solve
    int cost_cut;
    std::vector<std::pair<int,int>> vertices_parts;
    cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
            boost::weight_map(weight));
    // alternative form
    // cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
    // this works if the graph has and internal edge weight property map
    // print result
    std::cout << "cost cut:" << cost_cut << std::endl;
    std::vector<int> vertices_to_parts;
    for (auto i: vertices_parts) {
        std::cout << i.first << "(" << i.second << "), ";
    }
    std::cout << std::endl;
}

مرتبه زمانی الگوریتم بدیهی

الگوریتم بالا برای k به عنوان ورودی v تعداد رأس‌های گراف و E تعداد یال‌های گراف از مرتبه زمانی O(|K|∗|V|∗|E|∗log(|E|)|) و مرتبهٔ حافظهٔ O(|K|∗(|V|+|E|)|) خواهد بود.

جستارهای وابسته

• برش بیشینه
• برش کمینه
• NP کامل
• Shard - computer architecture
• پل (نظریه گراف)

منابع

• Goldschmidt, O. ; Hochbaum, D. S. (1988), Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci. , IEEE Computer Society, pp. 444–451
• Garey, M. R. ; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1044-8
• Saran, H. ; Vazirani, V. (1991), "Finding k-cuts within twice the optimal", Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society, pp. 743–751
• Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 978-3-540-65367-7
• Guttmann-Beck, N. ; Hassin, R. (1999), "Approximation algorithms for minimum k-cut" (PDF), Algorithmica, pp. 198–207
• Comellas, Francesc; Sapena, Emili (2006), "A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci.", Algorithmica, 3907 (2): 279–285, CiteSeerX 10.۱٫۱٫۵۵٫۵۶۹۷, doi:10.1007/s004530010013, ISSN 0302-9743, archived from the original on 2009-12-12
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum k-cut", A Compendium of NP Optimization Problems
• Fernandez de la Vega, W. ; Karpinski, M. ; Kenyon, C. (2004). "Approximation schemes for Metric Bisection and partitioning". Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. pp. 506–515, .CS1 maint: extra punctuation (link)
• Manurangsi, P. (2017). "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis". 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. pp. 79:1–79:14,. doi:10.4230/LIPIcs.ICALP.2017.79.