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

Пример максимального среза

Для графа , А максимальный разрез является разрезом , размер которого , по меньшей мере размера любого другого разреза. То есть это разделение вершин графа на два дополнительных множества S и T , так что количество ребер между множеством S и множеством T является как можно большим. Проблема поиска максимального разреза в графе известна как проблема максимального разреза .

Проблема может быть сформулирована просто следующим образом. Требуется такое подмножество S набора вершин, чтобы количество ребер между S и дополнительным подмножеством было как можно большим. Эквивалентно, нужно иметь двудольный подграф графа с как можно большим количеством ребер.

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

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

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

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

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

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

Для графа G найдите максимальный разрез.

Вариант оптимизации известен как NP-Hard. Противоположная проблема, задача поиска минимального разреза, как известно, эффективно решается с помощью алгоритма Форда – Фулкерсона .

Алгоритмы [ править ]

Алгоритмы с полиномиальным временем [ править ]

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

Планарные графики [ править ]

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

Алгоритмы аппроксимации [ править ]

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

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

Алгоритм аппроксимации полиномиальное время для Max-Cut с лучшим известным отношением аппроксимации является метод , с помощью Goemans и Williamson с использованием полуопределенного программирования и вероятностного округления , что позволяет достичь коэффициента аппроксимации где $\alpha \approx 0.878,$

\alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.

^[10]^[11]

Если гипотеза об уникальных играх верна, это наилучший возможный коэффициент приближения для максимального сокращения. ^[12] Без таких недоказанных предположений было доказано, что NP-трудно аппроксимировать значение максимального отсечения с коэффициентом аппроксимации лучше, чем . ^[13]^[14] ${\tfrac {16}{17}}\approx 0.941$

В ^[15] представлен расширенный анализ 10 эвристик для этой проблемы, включая реализацию с открытым исходным кодом.

Приложения [ править ]

Теоретическая физика [ править ]

В статистической физике и неупорядоченных системах проблема Макса Креста эквивалентна минимизации гамильтониана модели спинового стекла , проще говоря, модели Изинга . ^[16] Для модели Изинга на графе G и только взаимодействий ближайших соседей гамильтониан имеет вид

H[s]=-\sum _{ij\in E(G)}J_{ij}s_{i}s_{j}

Здесь каждая вершина i графа представляет собой узел вращения, который может принимать значение спина. Конфигурация спина разбивается на два набора: со вращением вверх и со спином вниз. Мы обозначаем набор ребер, которые соединяют два набора. Тогда мы можем переписать гамильтониан как $s_{i}=\pm 1.$ $V(G)$ $V^{+}$ $V^{-}.$ $\delta (V^{+})$

{\begin{aligned}H[s]&=-\sum _{ij\in E(V^{+})}J_{ij}-\sum _{ij\in E(V^{-})}J_{ij}+\sum _{ij\in \delta (V^{+})}J_{ij}\\&=-\sum _{ij\in E(G)}J_{ij}+2\sum _{ij\in \delta (V^{+})}J_{ij}\\&=C+2\sum _{ij\in \delta (V^{+})}J_{ij}\end{aligned}}

Минимизация этой энергии эквивалентна задаче минимального разреза или установке весов графа как задаче максимального разреза. ^[16] $w_{ij}=-J_{ij},$

Схемотехника [ править ]

Проблема максимального разреза находит применение в проектировании СБИС . ^[16]

См. Также [ править ]

Минимальный срез
Минимальный k-разрез
Трансверсаль по нечетному циклу , эквивалентна запросу наибольшего двудольного индуцированного подграфа

Заметки [ править ]

^ Garey & Johnson (1979) .
^ Карп (1972) .
^ Хэдлок (1975) .
^ Jansen et al. (2005) .
^ Papadimitriou & Yannakakis (1991) доказывают полноту MaxSNP .
^ Mitzenmacher & Upfal (2005) , п. 6.2.
^ Motwani & Raghavan (1995) , п. 5.1.
^ Mitzenmacher & Upfal (2005) , п. 6.3.
^ Khuller, Raghavachari & Young (2007) .
^ Гаур и Кришнамурти (2007) .
^ Ausiello et al. (2003)
^ Хот и др. (2007) .
^ Håstad (2001)
^ Trevisan et al. (2000)
^ Даннинг, Гупта и Зильберхольц (2018)
^ a b c Бараона, Франсиско; Грёчель, Мартин; Юнгер, Михаэль; Райнельт, Герхард (1988). «Применение комбинаторной оптимизации к статистической физике и проектированию схем». Исследование операций . 36 (3): 493–513. DOI : 10.1287 / opre.36.3.493 . ISSN 0030-364X . JSTOR 170992 .

Ссылки [ править ]

Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и приближение: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer.

Максимальный разрез (оптимизационная версия) - это проблема ND14 в Приложении B (стр. 399).

Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 CS1 maint: discouraged parameter (link).

Максимальный отсек (вариант решения) - это проблема ND16 в Приложении A2.2.

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

Гаур, Дайя Рам; Кришнамурти, Рамеш (2007), «LP округление и расширения», в Gonzalez, Teofilo F. (ed.), Handbook of Approximation Algorithms and Metaheuristics , Chapman & Hall / CRC.
Goemans, Michel X .; Уильямсон, Дэвид П. (1995), "Улучшенные алгоритмы аппроксимации для задач максимальной срезанных и выполнимости с использованием полуопределенного программирования", Журнал ACM , 42 (6): 1115-1145, DOI : 10,1145 / 227683,227684 , S2CID 15794408.
Хэдлок, Ф. (1975), "Нахождение максимального разреза плоского графа за полиномиальное время", SIAM J. Comput. , 4 (3): 221-225, DOI : 10,1137 / 0204019.
Håstad, Йохан (2001), "Некоторые результаты оптимальной inapproximability", Журнал ACM , 48 (4): 798-859, DOI : 10,1145 / 502090,502098 , S2CID 5120748 CS1 maint: discouraged parameter (link).
Янсен, Клаус; Карпинский, Марек ; Лингас, Анджей; Зайдель, Эйке (2005), «Схемы аппроксимации полиномиального времени для MAX-BISECTION на плоских и геометрических графах», SIAM Journal on Computing , 35 (1): 110–119, CiteSeerX 10.1.1.62.5082 , doi : 10.1137 / s009753970139567x CS1 maint: discouraged parameter (link).
Карп, Ричард М. (1972), « Сводимость комбинаторных задач », Миллер, RE; Тэчер, Дж. У. (ред.), Сложность компьютерных вычислений , Plenum Press, стр. 85–103. CS1 maint: discouraged parameter (link).
Хот, Субхаш ; Киндлер, Гай; Моссель, Эльханан; О'Доннелл, Райан (2007), "Оптимальные результаты несовместимости для MAX-CUT и других CSP с двумя переменными?" , SIAM Journal on Computing , 37 (1): 319–357, DOI : 10.1137 / S0097539705447372 CS1 maint: discouraged parameter (link).
Хуллер, Самир; Рагхавачари, Баладжи; Янг, Нил Э. (2007), «Жадные методы», в Гонсалес, Теофило Ф. (ред.), Справочник по аппроксимационным алгоритмам и метаэвристике , Chapman & Hall / CRC.
Митценмахер, Майкл ; Упфаль, Эли (2005), Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ , Кембридж CS1 maint: discouraged parameter (link).
Мотвани, Раджив ; Рагхаван, Прабхакар (1995), рандомизированные алгоритмы , Кембридж CS1 maint: discouraged parameter (link).
Newman, Alantha (2008), "Макс вырезать", в Као, Мин-Ян (ред . ), Энциклопедия алгоритмов ., Springer, С. 489-492, DOI : 10.1007 / 978-0-387-30162-4_219 , ISBN 978-0-387-30770-1.
Пападимитриу, Христос Х .; Yannakakis, Михалис (1991), "Оптимизация, приближение и классы сложности", журнал компьютерных и системных наук , 43 (3): 425-440, DOI : 10,1016 / 0022-0000 (91) 90023-X CS1 maint: discouraged parameter (link).
Тревизан, Лука ; Соркин Григорий; Судан, Мадху; Уильямсон, Дэвид (2000), «Гаджеты, приближение и линейное программирование», Труды 37-го симпозиума IEEE по основам компьютерных наук : 617–626 CS1 maint: discouraged parameter (link).
Даннинг, Иэн ; Гупта, Свати; Зильберхольц, Джон (2018), «Что лучше всего работает, когда? Систематическая оценка эвристики для Max-Cut и QUBO», INFORMS Journal on Computing , 30 (3): 608–624, doi : 10.1287 / ijoc.2017.0798 CS1 maint: discouraged parameter (link).

Внешние ссылки [ править ]

Пьерлуиджи Крещенци, Вигго Канн, Магнус Халльдорссон, Марек Карпински, Герхард Вегингер (2000), «Максимальный разрез» , в «Сборнике задач оптимизации NP» .
Андреа Казини, Никола Ребальати (2012), «Библиотека Python для решения Max Cut»

[1] Garey & Johnson (1979) .

[2] Карп (1972) .

[3] Хэдлок (1975) .

[4] Jansen et al. (2005) .

[5] Papadimitriou & Yannakakis (1991) доказывают полноту MaxSNP .

[6] Mitzenmacher & Upfal (2005) , п. 6.2.

[7] Motwani & Raghavan (1995) , п. 5.1.

[8] Mitzenmacher & Upfal (2005) , п. 6.3.

[9] Khuller, Raghavachari & Young (2007) .

[10] Гаур и Кришнамурти (2007) .

[11] Ausiello et al. (2003)

[12] Хот и др. (2007) .

[13] Håstad (2001)

[14] Trevisan et al. (2000)

[15] Даннинг, Гупта и Зильберхольц (2018)

[:0-16] Бараона, Франсиско; Грёчель, Мартин; Юнгер, Михаэль; Райнельт, Герхард (1988). «Применение комбинаторной оптимизации к статистической физике и проектированию схем». Исследование операций . 36 (3): 493–513. DOI : 10.1287 / opre.36.3.493 . ISSN 0030-364X . JSTOR 170992 .

[1]