Максимальный разрез
Ключевые слова и синонимы
Максимальный двудольный подграф (Maximum bipartite subgraph)
Постановка задачи
Пусть дан неориентированный граф G = (V, E). Задача о максимальном разрезе (MAX-CUT) заключается в нахождении такого биразбиения вершин, при котором суммарный вес ребер, пересекающих это разбиение, оказывается максимальным. Если веса ребер неотрицательны, то эта задача эквивалентна нахождению подмножества ребер с максимальным весом, которое образует двудольный подграф, то есть задаче о максимальном двудольном подграфе. Все результаты, обсуждаемые далее в статье, предполагают неотрицательные веса ребер. MAX-CUT входит в число изначальных NP-полных задач Карпа [19] [1]. На самом деле она является NP-трудной для аппроксимации с точностью до коэффициента, лучшего, чем 16/17 [16, 33].
На протяжении почти двадцати лет лучшим известным коэффициентом аппроксимации для MAX-CUT был 1/2, который можно получить с помощью очень простого алгоритма. Сформируем множество S, помещая каждую вершину в S с вероятностью 1/2. Поскольку каждое ребро пересекает разрез (S, V \ S) с вероятностью 1/2, ожидаемое значение этого разреза равно половине суммарного веса ребер. Отсюда следует, что для любого графа существует разрез со значением не менее половины суммарного веса ребер. В 1976 году Сахни и Гонсалес представили детерминированный полуаппроксимационный алгоритм для задачи MAX-CUT, который, по сути, представляет собой дерандомизацию вышеупомянутого рандомизированного алгоритма [31]. Выполним итеративный обход вершин и сформируем множества [math]\displaystyle{ S }[/math] и [math]\displaystyle{ \bar{S} }[/math], помещая каждую вершину в то из них, которое максимизирует вес разреза [math]\displaystyle{ (S, \bar{S}) }[/math] на текущий момент. После каждой итерации этого процесса вес этого разреза составит не менее половины суммарного веса ребер, конечные точки которых находятся в [math]\displaystyle{ S \cup \bar{S} }[/math].
Этот простой полуаппроксимационный алгоритм использует тот факт, что для любого графа с неотрицательными весами ребер суммарный вес его ребер является верхней границей величины его максимального разреза. Существуют классы графов, для которых максимальный разрез произвольно близок к половине суммарного веса ребер, то есть графы, для которых эта «тривиальная» верхняя граница может быть близка к удвоенному истинному значению оптимального решения. Примером такого класса графов являются полные графы с n вершинами – [math]\displaystyle{ K_n }[/math]. Чтобы получить коэффициент аппроксимации лучше 1/2, необходимо уметь вычислять верхнюю границу значения максимального разреза, которая была бы лучше, то есть меньше, тривиальной верхной границы для таких классов графов.
Релаксации линейного программирования
Было показано, что для многих задач оптимизации (максимизации) линейное программирование [2] дает лучшие верхние границы на значение оптимального решения, чем те, которые можно получить с помощью комбинаторных методов. Существует несколько хорошо изученных релаксаций линейного программирования для задачи MAX-CUT. Например, в классической целочисленной программе имеются переменная [math]\displaystyle{ x_e }[/math] для каждого ребра и ограничение для каждого нечетного цикла, требующее, чтобы нечетный цикл C вносил не более |C|-1 ребер в оптимальное решение.
[math]\displaystyle{ \sum_{e \in E} w_e x_e }[/math]
[math]\displaystyle{ \sum_{e \in C} x_e \le |C| - 1, \forall }[/math] нечетных циклов C
[math]\displaystyle{ x_e \in \{ 0, 1 \} }[/math].
Последнее ограничение может быть ослаблено так, что каждое [math]\displaystyle{ x_e }[/math] должно лежать между 0 и 1, но не обязательно должно быть целым, то есть [math]\displaystyle{ 0 \le x_e \le 1 }[/math]. Хотя у этой релаксации может быть экспоненциальное число ограничений, существует оракул разделения с полиномиальным временем работы (эквивалентный нахождению нечетного цикла минимального веса) и, таким образом, эта релаксация может быть решена за полиномиальное время [13]. Другая классическая целочисленная программа содержит переменную [math]\displaystyle{ x_{ij} }[/math] для каждой пары вершин. При любом разбиении вершин разрез пересекают либо ноль, либо два ребра из 3-цикла. Это требование выполняется в следующей целочисленной программе. Если ребро [math]\displaystyle{ (i, j) \ne E }[/math], то [math]\displaystyle{ w_{ij} }[/math] присваивается значение 0.
[math]\displaystyle{ max \sum_{i, j \in E} w_{ij} x_{ij} }[/math]
[math]\displaystyle{ x_{ij} + x_{jk} + x_{ki} \le 2 \; \; \forall i, j, k \in V }[/math]
[math]\displaystyle{ x_{ij} + x_{jk} - x_{ki} \ge 0 \; \; \forall i, j, k \in V }[/math]
[math]\displaystyle{ x_{ij} \in \{ 0, 1 \} }[/math].
Опять же, последнее ограничение может быть ослаблено таким образом, что каждый xij должен лежать между 0 и 1. В отличие от вышеупомянутой линейной программы, основанной на ограничениях цикла, данная релаксация ЛП имеет полиномиальное число ограничений.
Обе эти релаксации фактически имеют одно и то же оптимальное значение для любого графа с неотрицательными весами ребер [3, 26, 30]. Упрощенное доказательство этого можно найти в работе [25]. Поляк показал, что разрыв целостности для каждой из этих релаксаций произвольно близок к 2 [26]. Иными словами, существуют классы графов, у которых максимальный разрез содержит около половины ребер, но для которых каждая из приведенных выше релаксаций дает верхнюю границу, близкую ко всем ребрам, то есть не лучше, чем тривиальная «всереберная» граница. В частности, для демонстрации этого разрыва можно использовать графы с максимальным разрезом, близким к половине ребер, и с высоким обхватом. Полный обзор этих релаксаций линейного программирования содержится в обзоре Поляка и Тузы [30].
Верхние границы собственного значения
Делорм и Поляк [7] представили верхнюю границу собственного значения для величины максимального разреза, которая является усиленной версией предыдущей границы собственного значения, рассмотренной Мохаром и Поляком [24]. Вычисление верхней границы Делорма и Поляка эквивалентно решению задачи минимизации собственных значений. Они показали, что их граница вычисляется за полиномиальное время с произвольной точностью. В ряде работ Делорм, Поляк и Рендл показали, что эта верхняя граница ведет себя «иначе», чем верхние границы, основанные на линейном программировании. Например, они изучили классы разреженных случайных графов (такие как G(n,p) с p = 50/n) и показали, что на таких графах их верхняя граница близка к оптимальной [8]. Поскольку графы такого типа также могут использоваться для демонстрации разрыва целостности, произвольно близкого к 2, для вышеупомянутых релаксаций линейного программирования, их работа подчеркнула разницу в поведении этих двух верхних границ. Последующие вычислительные эксперименты на других классах графов дали больше доказательств того, что эта граница действительно сильнее ранее изученных [27, 29]. Делорм и Поляк предположили, что 5-цикл демонстрирует поведение наихудшего случая для их границы: отношение [math]\displaystyle{ 32/(25 + 5 \sqrt{5}) \approx 0,88445 }[/math] между их границей и оптимальным целочисленным решением. Однако они не смогли доказать, что их граница строго меньше удвоенной величины максимального разреза в наихудшем случае.
Основные результаты
В 1994 году Гуманс и Уильямсон представили рандомизированный алгоритм решения задачи MAX-CUT с коэффициентом аппроксимации 0,87856 [11]. Их прорывная работа была основана на округлении релаксации полуопределенного программирования [3] и стала первым случаем применения этого метода в алгоритмах аппроксимации. Поляк и Рендл показали, что верхняя граница, достигаемая этой полуопределенной релаксацией, эквивалентна границе собственных значений Делорма и Поляка [28]. Таким образом, Гёеманс и Уильямсон доказали, что собственное значение Делорма и Поляка не более чем в 1,138 раза превышает значение максимального разреза.
Полуопределенная релаксация
Задачу MAX-CUT можно сформулировать в виде следующей квадратичной целочисленной программы, решение которой является NP-трудным. Каждая вершина [math]\displaystyle{ i \in V }[/math] представлена переменной [math]\displaystyle{ y_i }[/math], которой присваивается значение 1 либо -1 в зависимости от того, с какой стороны от разреза она располагается.
[math]\displaystyle{ max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_i y_j) }[/math]
[math]\displaystyle{ y_i \in \{ -1, 1 \} \; \; \forall i \in E }[/math].
Гуманс и Уильямсон рассмотрели следующую релаксацию этой целочисленной программы, в которой каждая вершина представлена единичным вектором.
[math]\displaystyle{ max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - v_i \cdot v_j) }[/math]
[math]\displaystyle{ v_i \cdot v_i = 1 \; \; \forall i \in V }[/math]
[math]\displaystyle{ v_i \in \mathcal{R}^n \; \; \forall i \in V }[/math].
Они показали, что данная релаксация эквивалентна полуопределенной программе. Рассмотрим следующую полуопределенную релаксацию:
[math]\displaystyle{ max \frac{1}{2} \sum_{(i, j) \in E} w_{ij} (1 - y_{ij}) }[/math]
[math]\displaystyle{ y_{ii} = 1 \; \; \forall i \in V }[/math]
Y – положительно полуопределенная матрица.
Эквивалентность этих двух релаксаций обусловлена тем, что матрица Y является положительно полуопределенной тогда и только тогда, когда существует матрица B такая, что [math]\displaystyle{ B^T B = Y }[/math]. Последняя релаксация может быть решена с произвольной точностью за полиномиальное время с помощью метода эллипсоидов, поскольку имеет полиномиальный по времени оракул разделения [14]. Таким образом, решение первой релаксации можно получить, найдя решение второй релаксации и найдя матрицу B такую, что [math]\displaystyle{ B^T B = Y }[/math]. Если столбцы B соответствуют векторам [math]\displaystyle{ \{ v_i \} }[/math], то [math]\displaystyle{ y_{ij} = v_i \cdot v_j }[/math], что дает решение первой релаксации.
Округление с помощью случайной гиперплоскости
Гуманс и Уильямсон показали, как округлить релаксацию полуопределенного программирования MAX-CUT с помощью новой техники, которая с тех пор стала называться округлением с помощью случайной гиперплоскости (random-hyperplane rounding) [11]. Вначале получим решение первой релаксации, которое состоит из набора единичных векторов [math]\displaystyle{ \{ v_i \} }[/math], по одному вектору для каждой вершины. Затем выберем случайный вектор [math]\displaystyle{ r \in \mathcal{R}^n }[/math], каждая координата [math]\displaystyle{ r }[/math] которого выбирается из стандартного нормального распределения. Наконец, положим [math]\displaystyle{ S = \{ i | vi \cdot r \ge 0 \} }[/math] и выведем разрез (S, V \ S).
Вероятность того, что конкретное ребро [math]\displaystyle{ (i, j) \in E }[/math] пересекает разрез, равна вероятности того, что скалярные произведения [math]\displaystyle{ v_i \cdot r }[/math] и [math]\displaystyle{ vj \cdot r }[/math] различаются по знаку. Эта вероятность в точности равна [math]\displaystyle{ \theta_{ij} / \pi }[/math], где [math]\displaystyle{ \theta_{ij} }[/math] – угол между векторами [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ v_j }[/math]. Таким образом, ожидаемый вес ребер, пересекающих разрез, равен [math]\displaystyle{ \sum_{(i, j) \in E} \theta_{ij} / \pi }[/math]. Насколько это больше по сравнению с объективным значением, которое дает релаксация полуопределенного программирования, то есть каков коэффициент аппроксимации?
Определим [math]\displaystyle{ \alpha_{gw} }[/math] как отношение ожидаемого вклада ребра в разрез к его вкладу в целевую функцию релаксации полуопределенного программирования в наихудшем случае. Иными словами, [math]\displaystyle{ \alpha_{gw} = min_{0 \le \theta \le \pi} \frac{2}{\pi} \frac{\theta}{1 - cos \theta} }[/math]. Можно показать, что [math]\displaystyle{ \alpha_{gw} \gt 0,87856 }[/math]. Таким образом, ожидаемое значение разреза не меньше [math]\displaystyle{ \alpha_{gw} \cdot SDP_{OPT} }[/math], что дает коэффициент аппроксимации не менее 0,87856 для задачи MAX-CUT. Аналогичный анализ применим к взвешенным графам с неотрицательными весами ребер.
Этот алгоритм был дерандомизирован Махаджаном и Харихараном в [23]. Гуманс и Уильямсон также применили свои методы округления с помощью случайной гиперплоскости, чтобы получить улучшенные гарантии аппроксимации для других задач, таких как MAX-DICUT и MAX-2SAT.
Разрыв целостности и сложность
Карлофф показал, что существуют графы, для которых наилучшая гиперплоскость лишь на коэффициент [math]\displaystyle{ \alpha_{gw} }[/math] отличается от максимального разреза [18], продемонстрировав , что существуют графы, для которых анализ в работе [11] является строгим. Поскольку оптимальное значение разрыва целостности в задаче полуопределенного программирования (SDP) для таких графов равно оптимальному значению максимального разреза, эти графы не могут быть использованы для демонстрации разрыва целостности. Однако Фейге и Шехтман показали, что существуют графы, для которых максимальный разрез составляет [math]\displaystyle{ \alpha_{gw} }[/math]-долю от границы SDP [9], тем самым установив, что гарантия аппроксимации алгоритма Гуманса и Уильямсона соответствует разрыву целостности в их релаксации полуопределенного программирования. Недавно Хот, Киндлер, Моссел и О'Доннел [21] показали, что если предположить, что гипотеза об уникальной игре Хота [20] верна, то аппроксимация MAX-CUT с точностью до любого коэффициента, большего [math]\displaystyle{ \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].
См. также
Литература
1. Andersson, G., Engebretsen, L, Hastad, J.: A new way to use semidefinite programming with applications to linear equations mod p. J. Algorithms 39,162-204 (2001)
2. Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 36th Annual Symposium on the Theory of Computing (STOC), Chicago 2004, pp. 222-231
3. Barahona, F.: On cuts and matchings in planar graphs. Math. Program. 60, 53-68 (1993)
4. Blum, A., Konjevod, G., Ravi, R., Vempala, S.: Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems. Theor. Comput. Sci. 235, 25-42 (2000)
5. Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Boston 2003, pp. 524-533
6. Chor, B., Sudan, M.: A geometric approach to betweeness. SIAM J. Discret. Math. 11,511 -523 (1998)
7. Delorme, C., Poljak, S.: Laplacian eigenvalues and the maximum cut problem. Math. Program. 62, 557-574 (1993)
8. Delorme, C., Poljak, S.: The performance of an eigenvalue bound in some classes of graphs. Discret. Math. 111, 145-156 (1993). Also appeared in: Proceedings of the Conference on Combinatorics, Marseille, 1990
9. Feige, U., Schechtman, G.: On the optimality of the random hyperplane rounding technique for MAX-CUT. Random Struct. Algorithms 20(3), 403-440 (2002)
10. Frieze, A., Jerrum, M.R.: Improved approximation algorithms for MAX-k-CUT and MAX BISECTION. Algorithmica 18, 61-77 (1997)
11. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J.ACM 42,1115-1145 (1995)
12. Goemans, M.X., Williamson, D.P.: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. STOC 2001 Special Issue of J. Comput. Syst. Sci. 68, 442^70 (2004)
13. Grotschel,M., Lovasz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1,169-197 (1981)
14. Grotschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)
15. Halperin, E., Zwick, U.: A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems. Random Struct. Algorithms 20(3), 382-402 (2002)
16. Hastad, J.: Some optimal inapproximability results. J. ACM 48, 798-869(2001)
17. Karger, D.R., Motwani, R., Sudan, M.: Improved graph coloring via semidefinite programming. J. ACM 45(2), 246-265 (1998)
18. Karloff, H.J.: How good is the Goemans-Williamson MAX CUT algorithm? SIAM J. Comput. 29(1), 336-350 (1999)
19. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations, pp. 85-104. Plenum Press, New York (1972)
20. Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th Annual Symposium on the Theory of Computing (STOC), Montreal 2002, pp. 767-775
21. Khot, S., Kindler, G., Mossel, E.,O'Donnell,R.: Optimal inapproximability results for MAX CUT and other 2-variable CSPs? In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Rome 2004, pp. 146-154
22. de Klerk, E., Pasechnik, D., Warners, J.: On approximate graph colouring and MAX-k-CUT algorithms based on the 9 function. J. Combin. Optim. 8(3), 267-294 (2004)
23. Mahajan, R., Hariharan, R.: Derandomizing semidefinite programming based approximation algorithms. In: Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Milwaukee 1995, pp. 162-169
24. Mohar, B., Poljak, S.: Eigenvalues and the max-cut problem. Czechoslov Math. J. 40(115), 343-352 (1990)
25. Newman, A.: A note on polyhedral relaxations for the maximum cut problem (2004). Unpublished manuscript
26. Poljak, S.: Polyhedral and eigenvalue approximations of the max-cut problem. Sets, Graphs and Numbers. Colloqiua Mathematica Societatis Janos Bolyai 60, 569-581 (1992)
27. Poljak, S., Rendl, F.: Node and edge relaxations of the max-cut problem. Comput. 52,123-137 (1994)
28. Poljak, S., Rendl, F.: Nonpolyhedral relaxations of graph-bisection problems. SIAM J. Opt. 5,467^87 (1995)
29. Poljak, S., Rendl, F.: Solving the max-cut using eigenvalues. Discret. Appl. Math. 62(1-3), 249-278 (1995)
30. Poljak, S., Tuza, Z.: Maximum cuts and large bipartite subgraphs. DIMACS Ser. Discret. Math. Theor. Comput. Sci. 20, 181-244(1995)
31. Sahni, S., Gonzalez, T.: P-complete approximation problems. J. ACM 23(3), 555-565 (1976)
32. Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans 2004, pp. 526-527
33. Trevisan, L., Sorkin, G., Sudan, M., Williamson, D.: Gadgets, approximation, and linear programming. SIAM J. Comput. 29(6), 2074-2097 (2000)