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

Задача нахождения максимального разреза в графе

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

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

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

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

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

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

(а) ${\displaystyle \left\lceil {\frac {m}{2}}+{\sqrt {{\frac {m}{8}}+{\frac {1}{64}}}}-{\frac {1}{8}}\right\rceil }$

(б) ${\displaystyle {\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 являются различными подмножествами. BSP направлена ​​на нахождение разбиения с максимальным числом b ( G ) сбалансированных ребер в G. Эдвардс-Эрдёш дает нижнюю границу для b ( G ) для каждого связного знакового графа G. Граница (a) была улучшена для специальных классов графов: графов без треугольников, графов заданной максимальной степени, графов без H и т. д., см., например, ^{[5] [6] [7]}

Поляк и Турзик ^[8] расширили связь Эдвардса-Эрдёша до взвешенного Max-Cut:

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

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

Сложность вычислений

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

${\displaystyle \alpha ={\frac {2}{\pi }}\min _{0\leq \theta \leq \pi }{\frac {\theta }{1-\cos \theta }}.}$^{[19] [20]}

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

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

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

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

Приложения

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

Проектирование схем

Задача максимального разреза имеет применение в проектировании СБИС . ^[28]

Смотрите также

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

Примечания

1. Эдвардс (1973).
2. Эдвардс (1975).
3. Былка, Идзик и Туза (1999).
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. Хот и др. (2007).
22. Хастад (2001)
23. Тревизан и др. (2000)
24. Даннинг, Гупта и Зильберхольц (2018)
25. Кроустон, Джонс и Мних (2015).
26. Этшайд и Мних (2018).
27. Бойков, YY; Джолли, M.-P. (2001). "Интерактивные графические разрезы для оптимальной сегментации границ и областей объектов в ND-изображениях". Труды Восьмой международной конференции IEEE по компьютерному зрению. ICCV 2001. Том 1. IEEE Comput. Soc. стр. 105–112. doi :10.1109/iccv.2001.937505. ISBN 0-7695-1143-0. S2CID  2245438.
28. Барахона, Франциско; Грётшель, Мартин; Юнгер, Михаэль; Райнельт, Герхард (1988). «Применение комбинаторной оптимизации в статистической физике и проектировании схем». Operations Research . 36 (3): 493–513. doi :10.1287/opre.36.3.493. ISSN  0030-364X. JSTOR  170992.

Ссылки

• Алон, Н.; Кривелевич, М.; Судаков, Б. (2005), "Maxcut in H -free graphs", Combin. Probab. Comput. , 14 : 629–647, doi :10.1017/S0963548305007017 (неактивен 1 ноября 2024 г.), S2CID  123485000{{citation}}: CS1 maint: DOI inactive as of November 2024 (link).
• Аусиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости , Springer.

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

• Былка, С.; Идзик, А.; Туза, И. (1999), «Максимальные разрезы: улучшения и локальные алгоритмические аналоги неравенства Эдвардса-Эрдёша», Дискретная математика , 194 (1–3): 39–58, doi : 10.1016/S0012-365X(98)00115-0.
• Crowston, R.; Fellows, M.; Gutin, G.; Jones, M.; Kim, EJ; Rosamond, F.; Ruzsa, IZ; Thomassé, S.; Yeo, A. (2014), "Удовлетворение более чем половины системы линейных уравнений над GF(2): многомерный подход", J. Comput. Syst. Sci. , 80 (4): 687–696, doi : 10.1016/j.jcss.2013.10.002.
• Crowston, R.; Gutin, G.; Jones, M.; Muciaccia, G. (2013), "Проблема максимального сбалансированного подграфа, параметризованная выше нижней границы", Theor. Comput. Sci. , 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 Journal on Computing , 30 (3): 608–624, doi :10.1287/ijoc.2017.0798, S2CID  485706.
• Эдвардс, К. С. (1973), «Некоторые экстремальные свойства двудольных подграфов», Can. J. Math. , 25 (3): 475–485, doi : 10.4153/CJM-1973-048-x , S2CID  121925638.
• Эдвардс, К.С. (1975), «Улучшенная нижняя граница для числа ребер в наибольшем двудольном подграфе», Recent Advances in Graph Theory , стр. 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.
• Goemans, Michel X .; Williamson, David P. (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), «Некоторые оптимальные результаты неаппроксимируемости», Журнал 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; Thacher, JW (ред.), Complexity of Computer Computing , Plenum Press, стр. 85–103.
• Хот, Субхаш ; Киндлер, Гай; Моссел, Элханан; О'Доннелл, Райан (2007), «Оптимальные результаты неаппроксимируемости для MAX-CUT и других 2-переменных 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, doi : 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.
• Poljak, S.; Turzik, Z. (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. Aust. Math. Soc. , 30 (3): 1–13, doi :10.1017/S0004972716001295.

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

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