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

Пусть имеется неориентированный граф 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>.

Было показано, что для многих задач оптимизации (максимизации) линейное программирование [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 ребер в оптимальное решение.

<math>\sum_{e \in E} w_e x_e</math>

Последнее ограничение может быть ослаблено так, что каждое <math>x_e</math> должно лежать между 0 и 1, но не обязательно должно быть целым, то есть <math>0 \le x_e \le 1</math>. Хотя у этой релаксации может быть экспоненциальное число ограничений, существует оракул разделения с полиномиальным временем работы (эквивалентный нахождению нечетного цикла минимального веса) и, таким образом, эта релаксация может быть решена за полиномиальное время [13]. Другая классическая целочисленная программа содержит переменную <math>x_{ij}</math> для каждой пары вершин. При любом разбиении вершин разрез пересекают либо ноль, либо два ребра из 3-цикла. Это требование выполняется в следующей целочисленной программе. Если ребро <math>(i, j) \ne E</math>, то <math>w_{ij}</math> присваивается значение 0.

Опять же, последнее ограничение может быть ослаблено таким образом, что каждый xij должен лежать между 0 и 1. В отличие от вышеупомянутой линейной программы, основанной на ограничениях цикла, данная релаксация ЛП имеет полиномиальное число ограничений.

Обе эти релаксации фактически имеют одно и то же оптимальное значение для любого графа с неотрицательными весами ребер [3, 26, 30]. Упрощенное доказательство этого можно найти в работе [25]. Поляк показал, что разрыв целостности для каждой из этих релаксаций произвольно близок к 2 [26]. Иными словами, существуют классы графов, у которых максимальный разрез содержит около половины ребер, но для которых каждая из приведенных выше релаксаций дает верхнюю границу, близкую ко всем ребрам, то есть не лучше, чем тривиальная «всереберная» граница. В частности, для демонстрации этого разрыва можно использовать графы с максимальным разрезом, близким к половине ребер, и с высоким обхватом. Полный обзор этих релаксаций линейного программирования содержится в обзоре Поляка и Тузы [30].

Делорм и Поляк [7] представили верхнюю границу собственного значения для величины максимального разреза, которая является усиленной версией предыдущей границы собственного значения, рассмотренной Мохаром и Поляком [24]. Вычисление верхней границы Делорма и Поляка эквивалентно решению задачи минимизации собственных значений. Они показали, что их граница вычисляется за полиномиальное время с произвольной точностью. В ряде работ Делорм, Поляк и Рендл показали, что эта верхняя граница ведет себя «иначе», чем верхние границы, основанные на линейном программировании. Например, они изучили классы разреженных случайных графов (такие как G(n,p) с p = 50/n) и показали, что на таких графах их верхняя граница близка к оптимальной [8]. Поскольку графы такого типа также могут использоваться для демонстрации разрыва целостности, произвольно близкого к 2, для вышеупомянутых релаксаций линейного программирования, их работа подчеркнула разницу в поведении этих двух верхних границ. Последующие вычислительные эксперименты на других классах графов дали больше доказательств того, что эта граница действительно сильнее ранее изученных [27, 29]. Делорм и Поляк предположили, что 5-цикл демонстрирует поведение наихудшего случая для их границы: отношение <math>32/(25 + 5 \sqrt{5}) \approx 0,88445</math> между их границей и оптимальным целочисленным решением. Однако они не смогли доказать, что их граница строго меньше удвоенной величины максимального разреза в наихудшем случае.

В 1994 году Гуманс и Уильямсон представили рандомизированный алгоритм решения задачи MAX-CUT с коэффициентом аппроксимации 0,87856 [11]. Их прорывная работа была основана на округлении релаксации полуопределенного программирования [https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D1%83%D0%BE%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D1%91%D0%BD%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] и стала первым случаем применения этого метода в алгоритмах аппроксимации. Поляк и Рендл показали, что верхняя граница, достигаемая этой полуопределенной релаксацией, эквивалентна границе собственных значений Делорма и Поляка [28]. Таким образом, Гёеманс и Уильямсон доказали, что собственное значение Делорма и Поляка не более чем в 1,138 раза превышает величину максимального разреза.

Они показали, что данная релаксация эквивалентна полуопределенной программе. Рассмотрим следующую полуопределенную релаксацию:

Гуманс и Уильямсон показали, как округлить релаксацию полуопределенного программирования MAX-CUT с помощью новой техники, которая с тех пор стала называться округлением с помощью случайной гиперплоскости (random-hyperplane rounding) [11]. Вначале получим решение первой релаксации, которое состоит из набора единичных векторов <math>\{ v_i \}</math>, по одному вектору для каждой вершины. Затем выберем случайный вектор <math>r \in \mathcal{R}^n</math>, каждая координата <math>r</math> которого выбирается из стандартного нормального распределения. Наконец, положим <math>S = \{ i | vi \cdot r \ge 0 \}</math> и выведем разрез (S, V \ S).

Вероятность того, что конкретное ребро <math>(i, j) \in E</math> пересекает разрез, равна вероятности того, что скалярные произведения <math>v_i \cdot r</math> и <math>vj \cdot r</math> различаются по знаку. Эта вероятность в точности равна <math>\theta_{ij} / \pi</math>, где <math>\theta_{ij}</math> – угол между векторами <math>v_i</math> и <math>v_j</math>. Таким образом, ожидаемый вес ребер, пересекающих разрез, равен <math>\sum_{(i, j) \in E} \theta_{ij} / \pi</math>. Насколько это больше по сравнению с объективным значением, которое дает релаксация полуопределенного программирования, то есть каков коэффициент аппроксимации?

Карлофф показал, что существуют графы, для которых наилучшая гиперплоскость лишь на коэффициент <math>\alpha_{gw}</math> отличается от максимального разреза [18], продемонстрировав , что существуют графы, для которых анализ в работе [11] является строгим. Поскольку оптимальное значение разрыва целостности в задаче полуопределенного программирования (SDP) для таких графов равно оптимальной величине максимального разреза, эти графы не могут быть использованы для демонстрации разрыва целостности. Однако Фейге и Шехтман показали, что существуют графы, для которых максимальный разрез составляет <math>\alpha_{gw}</math>-долю от границы SDP [9], тем самым установив, что гарантия аппроксимации алгоритма Гуманса и Уильямсона соответствует разрыву целостности в их релаксации полуопределенного программирования. Недавно Хот, Киндлер, Моссел и О'Доннел [21] показали, что если предположить, что гипотеза об уникальной игре Хота [20] верна, то аппроксимация MAX-CUT с точностью до любого коэффициента, большего <math>\alpha_{gw}</math>, является NP-трудной задачей.

Работа Гуманса и Уильямсона открыла путь для последующего применения полуопределенного программирования в алгоритмах аппроксимации, в частности, в задачах разбиения графов. Методы, основанные на технике случайных гиперплоскостей, были успешно применены ко многим оптимизационным задачам, которые можно отнести к задачам разбиения. Можно привести такие примеры, как 3-раскраска (3-COLORING) [17], максимальный тройной разрез (MAX-3-CUT) [10, 12, 22], максимальная бисекция (MAX-BISECTION) [15], корреляционная кластеризация (CORRELATION-CLUSTERING) [5, 32] и [[самый неплотный разрез]] (SPARSEST-CUT) [2]. Кроме того, был достигнут определенный прогресс в расширении методов полуопределенного программирования за пределы области разбиения графов на такие задачи, как промежуточность (BETWEENNESS) [6], пропускная способность (BANDWIDTH) [4] и линейные уравнения с модулем p (LINEAR EQUATIONS modp) [1].

* [[Самое неплотное сечение]]