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

Наименьший k-разрез — это задача комбинаторной оптимизации, в которой требуется найти множество рёбер, удаление которых разбивает граф на k связных компонент. Эти рёбра называются k-разрезом. Целью задачи является поиск 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].

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