K برش کمینه
در ریاضیات، مسئلهٔ حداقل k برش، یک مسئلهٔ "بهینه‌سازی ترکیبی" است که به یافتن یک مجموعه از یال‌ها اشاره دارد که حذف این مجموعه، گراف را به حداقل k مولفهٔ همبندی تقسیم‌بندی کند. به این یال‌ها k-برش گفته می‌شود و به یالی که حذف آن باعث افزایش مولفه‌های همبندی شود پل (نظریه گراف) گفته می‌شود. این مسئله زیرمجموعه و مشتق شدهٔ مسئلهٔ حداقل برش است که کارکرد جزئی تری نسبت به مسئله اصلی دارد. هدف یافتن k-برش با وزن کمینه است. این تقسیم‌بندی می‌تواند کاربردهایی در طراحی وی‌ال‌اس‌آی، داده کاوی، روش اجزاء محدود و ارتباطات در رایانش موازی داشته باشد. گراف بدون جهت G = (E, V) و عدد "k" ∈ {۲, ۳, …, |"V"|} داده شده‌است. به هر یال گراف G یک‌وزن "w": "E" → "N اختصاص یافته‌است. V را به k مجموعه جدا تقسیم‌بندی کنید در حالی که عبارت زیر کمینه شود"
برای "k" ثابت، این مسئله، مسئله زمان چند جمله ای است که در "O"(|"V"|)قابل حل است. با این حال، اگر "k" بخشی از ورودی باشد، مسئله به یک مسئلهٔ NP کامل است. در صورتی که ما k رأس را مشخص کنیم و کمترین k برش برای جدا کردن این k رأس را بخواهیم این مسئله بازهم یک مسئلهٔ NP کامل خواهد شد.
کمترین برش هنگامی اهمیت پیدا می‌کند که گرافی بسیار بزرگ در اختیار داشته باشیم و بخواهیم آن را مورد بررسی قرار دهیم. در این حالت بررسی کل گراف به صورت کلی کاربردی نخواهد بود و ما در تلاشیم با تقسیم گراف به صورت معقول و عملی هزینه اجرای الگوریتم‌های گراف را بر روی تمام داده‌های خود بهینه کنیم. با تقسیم گراف به مؤلفه‌های همبندی، اصطلاحاً تعدادی خواهیم داشت که به معنای سهولت قراردهی داده‌ها در سرورهای مختلف خواهد بود.
مسئلهٔ k برش کمینه در حوزه‌های متنوعی که موضوع شبکه مطرح می‌شود، کاربرد دارد، به عنوان مثال از آن برای تقسیم‌بندی گروه‌های علاقه‌مندی در شبکه‌های اجتماعی یا برای یافتن ضعیف‌ترین اتصالات در شبکه‌های مخابراتی یا در یافتن خلوت‌ترین معابر در شبکه‌های ترافیکی استفاده می‌شود.
چندین الگوریتم تقریبی با تقریب 2 - 2/k وجود دارد. یک الگوریتم حریصانه ساده با این عامل تقریبی این است که حداقل برش در هر یک از اجزای متصل(مؤلفه همبندی) را محاسبه می‌کند و سنگین‌ترین را حذف می‌کند. این الگوریتم به‌طور کلی به n-1 بار محاسبه بیشینه جریان دارد. الگوریتم دیگری برای دستیابی به همان تقریب از نمای درخت گوموری‌هو از حداقل برش‌ها استفاده می‌کند. ساخت درخت گوموری‌هو به n-1 بار محاسبه جریان بیشینه احتیاج دارد که الگوریتم آن با محاسبه کلی بیشینه جریان از O(kn(انجام می‌دهد. با این حال، تجزیه و تحلیل عامل تقریب الگوریتم دوم آسان‌تر است. علاوه بر این، تحت فرضیه گسترش مجموعه کوچک (حدسی بسیار مرتبط با حدس بازی منحصر به فرد)، مسئله تقریباً نزدیک به NP است با عامل formula_2 برای هر ثابت formula_3. این به معنای آن است که الگوریتم‌های تقریبی فوق‌الذکر در اصل برای kهای بزرگ به جواب اصلی نزدیک تر هستند.
یکی از انواع مسائل یافتن کمترین وزن k-برش است هنگامی که مولفه‌های همبندی پس از اعمال برش‌ها اندازهٔ از پیش تعیین شده داشته باشند. اگر یک نمودار را به یک فضای متریک محدود کنید، به این معنی است که در یک عامل ۳ برای هر "k" ثابت وجود دارد، به این معنی که یک نمودار کامل که نابرابری مثلث را برآورده می‌کند. اخیراً، طرح‌های تقریبی زمان چند جمله ای (PTAS) برای آن مسائل کشف شده‌اند.
الگوریتم مورد نظر توسط Mikkel Thorup پیشنهاد شده‌است.
استفاده از الگوریتم حریصانه به عنوان یک راه حل (نه همیشه بهینه) برای این مسئله تلقی می‌شود. الگوریتم به‌طور کلی به این صورت تعریف می‌شود که در هر مرحله از k مرحله یال با کمترین ارزش را حذف می‌کنیم به طوری که حذف این یال تعداد مولفه‌های همبندی را به تعداد ۱ واحد اضافه کند.
برای a>0 و 0.9>a اگر T یک مجموعه از درخت‌های حریصانه با حداقل 3"m"("k"/"a")³ln("nmk"/"a") درخت باشد - به طوری که m تعداد یال‌ها و n تعداد رأس‌های درخت است - در حالت میانگین درختان T از هر یال از یال‌های مطلوب را در کمتر 2("k-"1+2"a") بار می‌گذرند. برای a=۱/۴ از هر یال حداکثر 2k-۲ بار توسط برخی درختان T استفاده می‌شود. با فرض a = ۱/۴ مراحل الگوریتم به این صورت خواهد بود:
در این الگوریتم برای محاسبه پیچیدگی زمانی از تابع soft_O استفاده خواهد شد.
به‌طور کل پیچیدگی زمانی مقدار "soft-O"("n"^(2"k")) را خواهد داشت.
می‌توان در هر مرحله کل گراف را پیمایش کرد و کم وزن‌ترین یال مطلوب برای برش را یافت و آن را حذف کرد تا به k مؤلفه همبندی برسیم.
int main() {  // sample data
الگوریتم بالا برای k به عنوان ورودی v تعداد رأس‌های گراف و E تعداد یال‌های گراف از مرتبه زمانی O(|K|∗|V|∗|E|∗log(|E|)|) و مرتبهٔ حافظهٔ O(|K|∗(|V|+|E|)|) خواهد بود.