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

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

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

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

Нижние границы

Эдвардс ^[1]^[2] получили следующие две нижние оценки для Max-Cut на графе $G$ с $n$ вершинами и $m$ ребрами (в (a) $G$ произвольный, но в (b) он связный):

(а)

\left\lceil {\frac {m}{2}}+{\sqrt {{\frac {m}{8}}+{\frac {1}{64}}}}-{\frac {1}{8}}\right\rceil

(б)

{\frac {m}{2}}+{\frac {n-1}{4}}.

Границу (b) часто называют границей Эдвардса-Эрдёша. ^[3] как предположил Эрдеш. Эдвардс доказал границу Эдвардса-Эрдёша, используя вероятностный метод; Кроустон и др. ^[4] доказал оценку с помощью линейной алгебры и анализа псевдобулевых функций.

Доказательство Кроустона и др. позволяет нам расширить связь Эдвардса-Эрдёша до задачи сбалансированного подграфа ( BSP ). ^[4] на графах со знаком $G = (V, E, s)$ , т.е. графах, где каждому ребру присвоен + или –. Для разделения $V$ на подмножества $U$ и $W$ ребро $xy$ является сбалансированным, если либо $s (xy) = +$ и $x$ и $y$ находятся в одном и том же подмножестве, либо $s (xy) = -$ и $x$ и $y$ — разные подмножества. найти разбиение с максимальным числом $b (G)$ сбалансированных ребер в $G.$ BSP стремится Эдвардс-Эрдёш дает нижнюю оценку $b (G)$ для каждого связного графа со $G.$ знаком Оценка (а) была улучшена для специальных классов графов: графов без треугольников, графов заданной максимальной степени, $графов без H$ и т. д., см., например, ^[5]^[6]^[7]

Польский и турецкий ^[8] расширил схему Эдвардса-Эрдёша, привязанную к утяжеленному Max-Cut:

{\frac {w(G)}{2}}+{\frac {w(T_{min})}{4}},

где $w (G)$ и $w (Tmin) —$ веса $G$ и его минимального веса остовного $Tmin .$ дерева Недавно Гутин и Йео ^[9] получил ряд нижних оценок для взвешенного Max-Cut, расширяя границу Поляка-Турзика для произвольных взвешенных графов и оценки для специальных классов взвешенных графов.

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

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

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

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

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

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

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

Алгоритмы

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

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

Планарные графы

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

Алгоритмы аппроксимации

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

Существует простой алгоритм рандомизированной 0,5 аппроксимации : для каждой вершины подбрасывайте монету, чтобы решить, какой половине раздела ее приписать. ^[15]^[16] Ожидается, что половина кромок — это обрезанные кромки. Этот алгоритм можно дерандомизировать с помощью метода условных вероятностей ; поэтому существует также простой детерминированный алгоритм аппроксимации 0,5 с полиномиальным временем. ^[17]^[18] Один из таких алгоритмов начинается с произвольного разбиения вершин заданного графа. $G=(V,E)$ и многократно перемещает одну вершину за раз с одной стороны разбиения на другую, улучшая решение на каждом шаге, пока улучшения этого типа больше не будут сделаны. Число итераций не более $|E|$ потому что алгоритм улучшает разрез хотя бы на одно ребро на каждом шаге. Когда алгоритм завершает работу, по крайней мере половина ребер, инцидентных каждой вершине, принадлежит разрезу, иначе перемещение вершины улучшит разрез. Следовательно, разрез включает в себя как минимум $|E|/2$ края.

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

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

^[19]^[20]

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

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

Параметризованные алгоритмы и кернеризация

Хотя доказать, что проблема нахождения разреза размером не менее (параметр) k является тривиальной , гораздо труднее продемонстрировать разрешимость с фиксированными параметрами для проблемы решения, является ли граф G имеет размер сокращения не ниже нижней границы Эдвардса-Эрдёша (см. Нижние границы выше) плюс (параметр) k . Кроустон и др. ^[25] доказал, что проблему можно решить вовремя $8^{k}O(n^{4})$ и допускает ядро размера $O(k^{5})$ . Кроустон и др. ^[25] расширил результат управляемости с фиксированными параметрами до задачи сбалансированного подграфа (BSP, см. Нижние границы выше) и улучшил размер ядра до $O(k^{3})$ (справедливо и для BSP). Этшайд и Мних ^[26] улучшил результат управляемости с фиксированными параметрами для BSP, чтобы $8^{k}O(m)$ и результат размера ядра $O(k)$ вершины.

Приложения

Машинное обучение

Рассматривая узлы как объекты , а ребра как расстояния, алгоритм максимального разреза делит граф на два хорошо разделенных подмножества. Другими словами, его естественным образом можно применить для выполнения двоичной классификации . По сравнению с более распространенными алгоритмами классификации, он не требует пространства признаков, а требует только расстояний между элементами внутри. ^[27]

Теоретическая физика

В статистической физике и неупорядоченных системах проблема Макса Каты эквивалентна минимизации гамильтониана модели спинового стекла , проще всего модели Изинга . ^[28] Для модели Изинга на графе 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}}

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

Схемотехника

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

См. также

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

Примечания

^ Эдвардс (1973) .
^ Эдвардс (1975) .
^ Bylka, Idzik & Tuza (1999) .
^ Перейти обратно: ^а ^б Кроустон и др. (2014) .
^ Алон, Кривелевич и Судаков (2005) .
^ Скотт (2005) .
^ Цзэн и Хоу (2017) .
^ Поляк и Турзик (1986) .
^ Гутин и Йео (2021) .
^ Гари и Джонсон (1979) .
^ Карп (1972) .
^ Хэдлок (1975) .
^ Янсен и др. (2005) .
^ Пападимитриу и Яннакакис (1991) доказывают MaxSNP -полноту.
^ Митценмахер и Упфаль (2005) , разд. 6.2.
^ Мотвани и Рагхаван (1995) , разд. 5.1.
^ Митценмахер и Упфаль (2005) , разд. 6.3.
^ Хуллер, Рагхавачари и Янг (2007) .
^ Гаур и Кришнамурти (2007) .
^ Аузиелло и др. (2003)
^ Khot et al. (2007) .
^ Хостад (2001)
^ Тревизан и др. (2000)
^ Даннинг, Гупта и Зильберхольц (2018)
^ Перейти обратно: ^а ^б Кроустон, Джонс и Мних (2015) .
^ Этшайд и Мних (2018) .
^ Бойков Ю.Ю.; Джолли, М.-П. (2001). «Интерактивные разрезы графов для оптимальной сегментации границ и областей объектов на изображениях ND» . Материалы восьмой международной конференции IEEE по компьютерному зрению. ИККВ 2001 . Том. 1. Компьютеры IEEE. Соц. стр. 105–112. дои : 10.1109/iccv.2001.937505 . ISBN 0-7695-1143-0 . S2CID 2245438 .
^ Перейти обратно: ^а ^б ^с Бараона, Франциско; Гретшель, Мартин; Юнгер, Майкл; Рейнельт, Герхард (1988). «Применение комбинаторной оптимизации к статистической физике и проектированию схем». Исследование операций . 36 (3): 493–513. дои : 10.1287/опре.36.3.493 . ISSN 0030-364X . JSTOR 170992 .

Ссылки

Алон, Н.; Кривелевич, М.; Судаков Б. (2005), "Maxcut в H -свободных графах", Combin. Вероятно. Вычислить. , 14 : 629–647, doi : 10.1017/S0963548305007017 , S2CID 123485000 .
Аузиелло, Джорджо; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации , Springer .

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

Былка, С.; Иджик, А.; Туза, И. (1999), «Максимальные сокращения: улучшения и локальные алгоритмические аналоги неравенства Эдвардса-Эрдса», Discrete Math. , 194 : 39–58, doi : 10.1016/S0012-365X(98)00115-0 .
Кроустон, Р.; Товарищи, М.; Гутин Г.; Джонс, М.; Ким, Э.Дж.; Розамонд, Ф.; Ружа, ИЗ; Томассе, С.; Йео, А. (2014), «Удовлетворение более половины системы линейных уравнений над GF (2): многомерный подход», J. Comput. Сист. наук. , 80 (4): 687–696, doi : 10.1016/j.jcss.2013.10.002 .
Кроустон, Р.; Гутин Г.; Джонс, М.; Мучачча, Г. (2013), «Задача о максимально сбалансированном подграфе, параметризованная выше нижней границы», Theor. Вычислить. наук. , 513 : 53–64, arXiv : 1212.6848 , doi : 10.1016/j.tcs.2013.10.026 .
Кроустон, Р.; Джонс, М.; Мнич, М. (2015), «Максимальный разрез, параметризованный выше границы Эдвардса – Эрдеша», Algorithmica , 72 (3): 734–757, doi : 10.1007/s00453-014-9870-z , S2CID 14973734 .
Даннинг, Иэн; Гупта, Свати; Зильберхольц, Джон (2018), «Что и когда работает лучше всего? Систематическая оценка эвристик для Max-Cut и QUBO», Журнал INFORMS on Computing , 30 (3): 608–624, doi : 10.1287/ijoc.2017.0798 , S2CID 485706 .
Эдвардс, CS (1973), «Некоторые экстремальные свойства двудольных подграфов», Can. Дж. Математика. , 25 (3): 475–485, doi : 10.4153/CJM-1973-048-x , S2CID 121925638 .
Эдвардс, К.С. (1975), «Улучшенная нижняя оценка числа ребер в наибольшем двудольном подграфе», « Последние достижения в теории графов» , стр. 167–181 .
Этшайд, М.; Мнич, М. (2018), «Линейные ядра и алгоритмы линейного времени для поиска больших разрезов», Algorithmica , 80 (9): 2574–2615, doi : 10.1007/s00453-017-0388-z , hdl : 11420/4693 , S2CID 16301072 .
Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5 .

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

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

Гаур, Дайя Рам; Кришнамурти, Рамеш (2007), «LP-округление и расширения», в Гонсалесе, Теофило Ф. (редактор), Справочник по алгоритмам аппроксимации и метаэвристике , Chapman & Hall/CRC .
Гоеманс, Мишель X .; Уильямсон, Дэвид П. (1995), «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования», Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 , S2CID 15794408 .
Гутин Г. ; Йео, А. (2021), «Нижние границы максимально взвешенного сокращения», arXiv : 2104.05536 [ math.CO ] .
Хэдлок, Ф. (1975), «Нахождение максимального разреза плоского графа за полиномиальное время», SIAM J. Comput. , 4 (3): 221–225, doi : 10.1137/0204019 .
Хостад, Йохан (2001), «Некоторые оптимальные результаты неаппроксимируемости», Journal of the ACM , 48 (4): 798–859, doi : 10.1145/502090.502098 , S2CID 5120748 .
Янсен, Клаус; Карпински, Марек ; Лингас, Анджей; Зайдель, Эйке (2005), «Схемы полиномиальной аппроксимации времени для MAX-BISECTION на планарных и геометрических графах», SIAM Journal on Computing , 35 (1): 110–119, CiteSeerX 10.1.1.62.5082 , doi : 10.1137/s009753970139567x .
Карп, Ричард М. (1972), « Сводимость комбинаторных задач », в Miller, RE; Тэчер, Дж.В. (ред.), Сложность компьютерных вычислений , Plenum Press, стр. 85–103 .
Хот, Субхаш ; Киндлер, Гай; Моссель, Эльханан; О'Доннелл, Райан (2007), «Оптимальные результаты неаппроксимируемости для MAX-CUT и других CSP с двумя переменными?» , SIAM Journal on Computing , 37 (1): 319–357, doi : 10.1137/S0097539705447372 , S2CID 2090495 .
Хуллер, Самир; Рагхавачари, Баладжи; Янг, Нил Э. (2007), «Жадные методы», в книге Гонсалеса, Теофило Ф. (редактор), Справочник по алгоритмам аппроксимации и метаэвристике , Chapman & Hall/CRC .
Митценмахер, Михаэль ; Упфал, Эли (2005), Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ , Кембридж .
Мотвани, Раджив ; Рагхаван, Прабхакар (1995), Рандомизированные алгоритмы , Кембридж .
Ньюман, Аланта (2008), «Максимальное сокращение», в Као, Минг-Янг (редактор), Энциклопедия алгоритмов , Springer, стр. 489–492, номер домена : 10.1007/978-0-387-30162-4_219 , ISBN. 978-0-387-30770-1 .
Пападимитриу, Христос Х .; Яннакакис, Михалис (1991), «Классы оптимизации, аппроксимации и сложности», Журнал компьютерных и системных наук , 43 (3): 425–440, doi : 10.1016/0022-0000(91)90023-X .
Поляк, С.; Турзик, З. (1986), «Эвристика полиномиального времени для некоторых задач оптимизации подграфа с гарантированной границей наихудшего случая», Discrete Math. , 58 (1): 99–104, doi : 10.1016/0012-365X(86)90192-5 .
Скотт, А. (2005), «Разумные разбиения и связанные с ними проблемы», Обзоры по комбинаторике, Серия лекций Лондонского математического общества , 327 : 95–117 .
Тревизан, Лука ; Соркин, Грегори; Судан, Мадху; Уильямсон, Дэвид (2000), «Гаджеты, аппроксимация и линейное программирование», Труды 37-го симпозиума IEEE по основам информатики : 617–626 .
Цзэн, К.; Хоу, Дж. (2017), «Двудольные подграфы H -свободных графов», Bull. Ауст. Математика. Соц. , 30 (3): 1–13, doi : 10.1017/S0004972716001295 .

Внешние ссылки

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

[1] Эдвардс (1973) .

[2] Эдвардс (1975) .

[3] Bylka, Idzik & Tuza (1999) .

[Crowston_2014-4] Перейти обратно: ^а ^б Кроустон и др. (2014) .

[5] Алон, Кривелевич и Судаков (2005) .

[6] Скотт (2005) .

[7] Цзэн и Хоу (2017) .

[8] Поляк и Турзик (1986) .

[9] Гутин и Йео (2021) .

[10] Гари и Джонсон (1979) .

[11] Карп (1972) .

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

[13] Янсен и др. (2005) .

[14] Пападимитриу и Яннакакис (1991) доказывают MaxSNP -полноту.

[15] Митценмахер и Упфаль (2005) , разд. 6.2.

[16] Мотвани и Рагхаван (1995) , разд. 5.1.

[17] Митценмахер и Упфаль (2005) , разд. 6.3.

[18] Хуллер, Рагхавачари и Янг (2007) .

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

[20] Аузиелло и др. (2003)

[21] Khot et al. (2007) .

[22] Хостад (2001)

[23] Тревизан и др. (2000)

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

[Crowston_2015-25] Перейти обратно: ^а ^б Кроустон, Джонс и Мних (2015) .

[26] Этшайд и Мних (2018) .

[27] Бойков Ю.Ю.; Джолли, М.-П. (2001). «Интерактивные разрезы графов для оптимальной сегментации границ и областей объектов на изображениях ND» . Материалы восьмой международной конференции IEEE по компьютерному зрению. ИККВ 2001 . Том. 1. Компьютеры IEEE. Соц. стр. 105–112. дои : 10.1109/iccv.2001.937505 . ISBN 0-7695-1143-0 . S2CID 2245438 .

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]