Максимальный разрез: различия между версиями

Пусть дан неориентированный граф G = (V, E). Задача о максимальном разрезе (MAX-CUT) заключается в нахождении такого биразбиения вершин, при котором суммарный вес ребер, пересекающих это разбиение, оказывается максимальным. Если веса ребер неотрицательны, то эта задача эквивалентна нахождению подмножества ребер с максимальным весом, которое образует двудольный подграф, то есть задаче о максимальном двудольном подграфе. Все результаты, обсуждаемые далее в статье, предполагают неотрицательные веса ребер. MAX-CUT входит в число изначальных NP-полных задач Карпа [19] [https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0]. На самом деле она является NP-трудной для аппроксимации с точностью до коэффициента, лучшего, чем 16/17 [16, 33].

На протяжении почти двадцати лет лучшим известным коэффициентом аппроксимации для MAX-CUT был 1/2, который можно получить с помощью очень простого алгоритма. Сформируем множество S, помещая каждую вершину в S с вероятностью 1/2. Поскольку каждое ребро пересекает разрез (S, V \ S) с вероятностью 1/2, ожидаемое значение этого разреза равно половине суммарного веса ребер. Отсюда следует, что для любого графа существует разрез со значением не менее половины суммарного веса ребер. В 1976 году Сахни и Гонсалес представили детерминированный полуаппроксимационный алгоритм для задачи MAX-CUT, который, по сути, представляет собой дерандомизацию вышеупомянутого рандомизированного алгоритма [31]. Выполним итеративный обход вершин и сформируем множества <math>S</math> и <math>\bar{S}</math>, помещая каждую вершину в то из них, которое максимизирует вес разреза <math>(S, \bar{S})</math> на текущий момент. После каждой итерации этого процесса вес этого разреза составит не менее половины суммарного веса ребер, конечные точки которых находятся в <math>S \cup \bar{S}</math>.

Этот простой полуаппроксимационный алгоритм использует тот факт, что для любого графа с неотрицательными весами ребер суммарный вес его ребер является верхней границей [[величина разреза|величины]] его максимального разреза. Существуют классы графов, для которых максимальный разрез произвольно близок к половине суммарного веса ребер, то есть графы, для которых эта «тривиальная» верхняя граница может быть близка к удвоенному истинному значению оптимального решения. Примером такого класса графов являются полные графы с n вершинами – <math>K_n</math>. Чтобы получить коэффициент аппроксимации лучше 1/2, необходимо уметь вычислять верхнюю границу значения максимального разреза, которая была бы лучше, то есть меньше, тривиальной верхной границы для таких классов графов.

Было показано, что для многих задач оптимизации (максимизации) линейное программирование [https://ru.wikipedia.org/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5] дает лучшие верхние границы на значение оптимального решения, чем те, которые можно получить с помощью комбинаторных методов. Существует несколько хорошо изученных релаксаций линейного программирования для задачи MAX-CUT. Например, в классической целочисленной программе имеются переменная <math>x_e</math> для каждого ребра и ограничение для каждого нечетного цикла, требующее, чтобы нечетный цикл C вносил не более |C|-1 ребер в оптимальное решение.