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

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

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

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

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

Вычислительная сложностьПравить

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

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

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

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

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

Алгоритмы полиномиального времениПравить

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

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

Аппроксимационные алгоритмыПравить

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

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

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

См. такжеПравить

ПримечанияПравить

ЛитератураПравить

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"

[_867626922de563e0-1] Garey, Johnson, 1979.

[_9e0834b4bef35f12-2] Karp, 1972.

[_aa8ce6a8586137b3-3] Hadlock, 1975.

[_b9c1e1aa799c41b5-4] Jansen, Karpinski, Lingas, Seidel, 2005.

[_cd54892d22f2045b-5] Papadimitriou & Yannakakis, 1991.

[_fa24a2a56e780566-6] Mitzenmacher, Upfal, 2005, с. Sect. 6.2.

[_90ec9e40db0dccd3-7] Motwani, Raghavan, 1995, с. Sect. 5.1.

[_8445c61ab5f12e2b-8] Mitzenmacher, Upfal, 2005, с. Sect. 6.3..

[_ab7ced9fbfa6fa6e-9] Khuller, Raghavachari, Young, 2007.

[_74e8a01ca57b367e-10] Gaur, Krishnamurti, 2007.

[_22b167697a67e0eb-11] Ausiello, Crescenzi и др., 2003.

[_a9283893b8101704-12] Khot, Kindler, Mossel, O'Donnell, 2007.

[_b777f073c6dc5106-13] Håstad, 2001.

[_b851a9843ad771c5-14] Trevisan, Sorkin, Sudan, Williamson, 2000.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]