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

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

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

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

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

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

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

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

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

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

Учитывая график г, найдите максимальный разрез.

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

Алгоритмы

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

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

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

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

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

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

Есть простой рандомизированный 0.5-алгоритм аппроксимации: для каждой вершины подбросьте монетку, чтобы решить, какой половине раздела ее назначить.[6][7] В ожидании половина кромок - это обрезанные кромки. Этот алгоритм может быть дерандомизированный с метод условных вероятностей; следовательно, существует также простой детерминированный алгоритм 0,5-аппроксимации с полиномиальным временем.[8][9] Один такой алгоритм начинается с произвольного разбиения вершин данного графа и многократно перемещает одну вершину за раз с одной стороны раздела на другую, улучшая решение на каждом шаге, пока больше нельзя будет сделать никаких улучшений этого типа. Количество итераций не более потому что алгоритм улучшает разрез по крайней мере на одно ребро на каждом шаге. Когда алгоритм завершается, по крайней мере половина ребер, инцидентных каждой вершине, принадлежит разрезу, иначе перемещение вершины улучшит разрез. Следовательно, в разрез входит не менее края.

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

[10][11]

Если догадка уникальных игр верно, это наилучший возможный коэффициент приближения для максимального разреза.[12] Было доказано, что без таких недоказанных предположений NP-трудно аппроксимировать максимальное значение отсечки с коэффициентом аппроксимации лучше, чем .[13][14]

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

Приложения

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

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

Здесь каждая вершина я на графике - это сайт вращения, который может принимать значение вращения Разделы конфигурации спина на два набора, те, у которых есть раскрутка и те, у кого есть замедление Обозначим через набор ребер, соединяющих два набора. Тогда мы можем переписать гамильтониан как

Минимизация этой энергии эквивалентна задаче min-cut или установке весов графов как проблема максимального сокращения.[16]

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

Проблема максимального сокращения имеет приложения в Конструкция СБИС.[16]

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

Заметки

  1. ^ Гэри и Джонсон (1979).
  2. ^ Карп (1972).
  3. ^ Хэдлок (1975).
  4. ^ Jansen et al. (2005).
  5. ^ Пападимитриу и Яннакакис (1991) доказать MaxSNP -полнота.
  6. ^ Митценмахер и Упфаль (2005), Разд. 6.2.
  7. ^ Мотвани и Рагхаван (1995), Разд. 5.1.
  8. ^ Митценмахер и Упфаль (2005), Разд. 6.3.
  9. ^ Хуллер, Рагхавачари и Янг (2007).
  10. ^ Гаур и Кришнамурти (2007).
  11. ^ Ausiello et al. (2003)
  12. ^ Khot et al. (2007).
  13. ^ Хостад (2001)
  14. ^ Trevisan et al. (2000)
  15. ^ Даннинг, Гупта и Зильберхольц (2018)
  16. ^ а б c Бараона, Франсиско; Грёчель, Мартин; Юнгер, Михаэль; Райнельт, Герхард (1988). «Применение комбинаторной оптимизации в статистической физике и проектировании схем». Исследование операций. 36 (3): 493–513. Дои:10.1287 / opre.36.3.493. ISSN  0030-364X. JSTOR  170992.

использованная литература

  • Аузиелло, Джорджио; Крещенци, Пьерлуиджи; Гамбози, Джорджио; Канн, Вигго; Маркетти-Спаккамела, Альберто; Протаси, Марко (2003), Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимируемости, Springer.
Максимальный вырез (оптимизационная версия) - это проблема ND14 в Приложении B (стр. 399).
Максимальный отсек (вариант решения) - это проблема ND16 в Приложении A2.2.
Максимальный двудольный подграф (вариант решения) - это задача GT25 в Приложении A1.2.

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