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

Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.

Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно.

Существует расширенная версия, задача о взвешенном максимальном разрезе. В этой версии каждому ребру приписано вещественное число, его вес, и целью является максимизация не числа рёбер, а общего веса рёбер между S и его дополнением. Задача о взвешенном максимальном разрезе часто, но не всегда, ограничивается неотрицательными весами, поскольку отрицательные веса могут изменить природу задачи.

Следующая задача разрешимости, связанная с максимальным разрезом, широко изучалась в теоретической информатике:

Задан граф G и целое число k, определить, имеется ли разрез в G размером, не меньшим k.

Известно, что эта задача NP-полная. NP-полноту задачи можно показать, например, приведением от задачи максимальной 2-выполнимости^[англ.] (задача максимальной выполнимости^[англ.] с ограничениями)^[1]. Взвешенная версия задачи разрешимости входит в 21 NP-полную задачу Карпа^[2]. Карп показал NP-полноту путём приведения от задачи разбиения^[англ.].

Канонический оптимизационный вариант вышеупомянутой задачи разрешимости известен как «задача о максимальном разрезе» и определяется следующим образом:

Пусть задан граф G, нужно найти максимальный разрез.

Так как задача о максимальном разрезе является NP-трудной, нет известных алгоритмов полиномиального времени для задачи о максимальном разрезе для общих графов.

Для планарных графов, однако, задача о максимальном разрезе двойственна задаче китайского почтальона (задаче поиска кратчайшего обхода с обходом всех рёбер по меньшей мере один раз), в том смысле, что рёбра, не принадлежащие максимальному разрезу графа G, двойственны рёбрам, которые проходятся многократно в оптимальном обходе двойственного графа для графа G. Оптимальный обход образует самопересекающуюся кривую, которая разбивает плоскость на два подмножества, подмножество точек, для которых порядок относительно кривой чётен, и подмножества точек, порядок которых нечётен. Эти два подмножества образуют разрез, в который входят все рёбра, двойственные рёбрам, которые появляются нечётное число раз в обходе. Задача о китайском почтальоне может быть решена за полиномиальное время, и эта двойственность позволяет задачу максимального разреза решать для планарных графов за полиномиальное время^[3]. Известно, однако, что задача максимальной бисекции NP-трудна^[4].

Задача о максимальном разрезе является APX-сложной (Пападимитроу и Яннакакис доказали MaxSNP-полноту данной задачи^[5]), что означает, что не существует аппроксимационной схемы полиномиального времени (PTAS) как угодно близкой к оптимальному решению, если только не P = NP. Таким образом, любой аппроксимационный алгоритм полиномиального времени даёт аппроксимационный коэффициент, строго меньший единицы.

Существует простой вероятностный 0,5-аппроксимационный алгоритм — для любой вершины бросаем монету с целью решить, к какой части разреза отнести данную вершину^[6][7]. Ожидается, что половина рёбер являются разрезающими. Этот алгоритм может быть дерандомизирован с помощью метода условных вероятностей. Таким образом, существует простой детерминированный полиномиального времени алгоритм с 0,5-аппроксимацией^[8][9]. Один такой алгоритм начинает с произвольного разбиения вершин заданного графа ${\displaystyle G=(V,E)}$ и передвигает одну вершину за один шаг из одной части разреза в другую, улучшая решение на каждом шаге до тех пор, пока улучшение возможно. Число итераций алгоритма не превосходит ${\displaystyle |E|}$, поскольку алгоритм улучшает разрез по меньшей мере на одно ребро. Когда алгоритм прекращает работу, по меньшей мере половина рёбер, инцидентных любой вершине, принадлежат разрезу, в противном случае перенос вершины улучшил бы разрез (увеличил бы размер разреза). Таким образом, разрез включает по меньшей мере ${\displaystyle |E|/2}$ рёбер.

Полиномиального времени аппроксимационный алгоритм для задачи о максимальном разрезе с лучшим известным аппроксимационным коэффициентом — это метод Геманса и Вильямсона, использующий полуопределённое программирование и вероятностное округление. Метод даёт аппроксимационный коэффициент ${\displaystyle \alpha \approx 0{,}878}$, где ${\displaystyle \alpha ={\tfrac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\tfrac {\theta }{1-\cos \theta }}}$^[10][11]. Если гипотеза уникальной игры^[англ.] верна, это лучший возможный аппроксимационный коэффициент для максимального разреза^[12]. Если не принимать такие недоказанные допущения, было доказано, что NP-трудно аппроксимировать значение максимального разреза с коэффициентом, лучшим ${\displaystyle {\tfrac {16}{17}}\approx 0{,}941}$^[13][14].

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

• Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. — Springer, 2003.

Задача о максимальном разрезе (оптимизационная версия) — задача ND14 в Приложении B (стр. 399).

• Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. — W. H. Freeman, 1979. — ISBN 0-7167-1045-5.

Задача о максимальном разрезе (задача разрешимости) — задача ND16 в Приложении A2.2.

Максимальный двудольный подграф (задача разрешимости) — задача GT25 в Приложении A1.2.

• Daya Ram Gaur, Ramesh Krishnamurti. LP rounding and extensions // Handbook of Approximation Algorithms and Metaheuristics. — Chapman & Hall/CRC, 2007.
• Michel X. Goemans, David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming // Journal of the ACM. — 1995. — Vol. 42, no. 6. — P. 1115–1145. — doi:10.1145/227683.227684.
• F. Hadlock. Finding a Maximum Cut of a Planar Graph in Polynomial Time // SIAM J. Comput.. — 1975. — Vol. 4, no. 3. — P. 221–225. — doi:10.1137/0204019.
• Johan Håstad. Some optimal inapproximability results // Journal of the ACM. — 2001. — Vol. 48, no. 4. — P. 798–859. — doi:10.1145/502090.502098.
• Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel. Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs // SIAM Journal on Computing. — 2005. — Vol. 35, no. 1. — doi:10.1137/s009753970139567x.
• Richard M. Karp. Reducibility among combinatorial problems // Complexity of Computer Computation / R. E. Miller, J. W. Thacher. — Plenum Press, 1972. — P. 85–103.
• Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? // SIAM Journal on Computing. — 2007. — Vol. 37, no. 1. — P. 319–357. — doi:10.1137/S0097539705447372.
• Samir Khuller, Balaji Raghavachari, Neal E. Young. Greedy methods // Handbook of Approximation Algorithms and Metaheuristics / Teofilo F. Gonzalez. — Chapman & Hall/CRC, 2007.
• Michael Mitzenmacher, Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. — Cambridge, 2005.
• Rajeev Motwani, Prabhakar Raghavan. Randomized Algorithms. — Cambridge, 1995..
• Alantha Newman. Max cut // Encyclopedia of Algorithms / Ming-Yang Kao. — Springer, 2008. — P. 1. — ISBN 978-0-387-30770-1. — doi:10.1007/978-0-387-30162-4_219.
• Christos H. Papadimitriou, Mihalis Yannakakis. Optimization, approximation, and complexity classes // Journal of Computer and System Sciences. — 1991. — Vol. 43, no. 3. — P. 425–440. — doi:10.1016/0022-0000(91)90023-X.
• Luca Trevisan, Gregory Sorkin, Madhu Sudan, David Williamson. Gadgets, Approximation, and Linear Programming // Proceedings of the 37th IEEE Symposium on Foundations of Computer Science. — 2000. — P. 617–626.

• Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt. An application of combinatorial optimization to statistical physics and circuit layout design // Operations Research. — 1988. — Vol. 36, no. 3. — P. 493–513. — doi:10.1287/opre.36.3.493. — JSTOR 170992.

• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems".
• Andrea Casini, Nicola Rebagliati (2012), "A Python library for solving Max Cut"