Наименьший k-разрез

Если задан неориентированный граф G = (V, E) с заданными весами для рёбер w: E → N и целое число k ∈ {2, 3, …, |V|}, разбиение V на k непересекающихся множеств F = {C₁, C₂, …, C_k}, для которых минимизируется

${\displaystyle \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) [1]. Однако задача является NP-полной, если k является частью входных данных[2]. Задача также NP-полна, если мы фиксируем ${\displaystyle k}$ вершин и пытаемся найти наименьший ${\displaystyle k}$-разрез, который разделяет эти вершины [3]

Существуют некоторые аппроксимационные алгоритмы с аппроксимацией 2 − 2/k. Простой жадный алгоритм, который даёт такой коэффициент аппроксимации, вычисляет наименьший разрез в каждой связной компоненте и удаляет самый лёгкий из них. Алгоритм требует суммарно n − 1 вычислений максимального потока. Другой алгоритм, дающий тот же коэффициент, использует представление дерева Гомори — Ху наименьших разрезов. Построение дерева Гомори — Ху требует n − 1 вычислений максимального потока, но алгоритм требует в общей сложности O(kn) вычислений максимального потока. Всё же проще анализировать аппроксимационный коэффициент втотого алгоритма[4][5].

Если мы ограничиваемся графами в метрическом пространстве, предполагая, что соответствующий полный граф удовлетворяет неравенству треугольника, и если будем требовать, чтобы результирующие разбиения имели заданные заранее размеры, задача аппроксимируется с коэффициентом 3 для любого фиксированного k[6]. Точнее, были обнаружены приближенные схемы полиномиального времени (PTAS) для таких задач[7].

• Максимальный разрез графа
• Наименьший разрез