Соответствие максимальной мощности

Задача теории графов: найти паросочетание, содержащее наибольшее количество ребер

Сопоставление максимальной мощности является фундаментальной проблемой теории графов . ^[1] Нам дан граф G , и цель состоит в том, чтобы найти паросочетание , содержащее как можно больше ребер; то есть подмножество ребер максимальной мощности , такое, что каждая вершина примыкает не более чем к одному ребру подмножества. Поскольку каждое ребро будет охватывать ровно две вершины, эта проблема эквивалентна задаче поиска паросочетания, охватывающего как можно больше вершин.

Важный частный случай проблемы сопоставления максимальной мощности — это случай, когда G — двудольный граф , вершины которого V разделены между левыми вершинами в X и правыми вершинами в Y , а ребра в E всегда соединяют левую вершину с правой вершиной. В этом случае задачу можно эффективно решить с помощью более простых алгоритмов, чем в общем случае.

Алгоритмы для двудольных графов

Потоковый алгоритм

Самый простой способ вычислить сопоставление максимальной мощности — следовать алгоритму Форда–Фалкерсона . Этот алгоритм решает более общую задачу вычисления максимального потока . Двудольный граф ( X + Y , E ) можно преобразовать в потоковую сеть следующим образом.

• Добавьте исходную вершину s ; добавьте ребро из s в каждую вершину в X .
• Добавьте вершину стока t ; добавьте ребро из каждой вершины в Y в t .
• Назначьте емкость 1 каждому ребру.

Поскольку каждое ребро в сети имеет целую пропускную способность, существует максимальный поток, в котором все потоки являются целыми числами; эти целые числа должны быть либо 0, либо 1, поскольку все пропускные способности равны 1. Каждый целочисленный поток определяет паросочетание, в котором ребро входит в паросочетание тогда и только тогда, когда его поток равен 1. Это паросочетание, потому что:

• Входящий поток в каждую вершину в X не превышает 1, поэтому исходящий поток также не превышает 1, поэтому присутствует не более одного ребра, смежного с каждой вершиной в X.
• Исходящий поток из каждой вершины в Y не превышает 1, поэтому входящий поток также не превышает 1, поэтому присутствует не более одного ребра, смежного с каждой вершиной в Y.

Алгоритм Форда – Фулкерсона многократно находит увеличивающий путь от некоторого x ∈ X к некоторому y ∈ Y и обновляет сопоставление M , беря симметричную разность этого пути с M (при условии, что такой путь существует). Поскольку каждый путь может быть найден за время O ( E ) , время выполнения равно O ( VE ) , а максимальное совпадение состоит из ребер E , которые переносят поток от X к Y.

Расширенные алгоритмы

Улучшением этого алгоритма является более сложный алгоритм Хопкрофта-Карпа , который ищет несколько путей увеличения одновременно. Этот алгоритм работает во времени. ${\displaystyle O({\sqrt {V}}E)}$

Алгоритм Чандрана и Хохбаума ^[2] для двудольных графов работает за время, которое зависит от размера максимального паросочетания k , которое для | Х | < | Ю | является

${\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}$

Используя логические операции над словами большого размера, сложность дополнительно повышается до ^[2] ${\displaystyle \lambda }$

${\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).}$

Существуют более эффективные алгоритмы для особых видов двудольных графов:

• Для разреженных двудольных графов задача максимального соответствия может быть решена с помощью алгоритма Мэдри, основанного на электрических потоках. ^[3] ${\displaystyle {\tilde {O}}(E^{10/7})}$
• Для плоских двудольных графов проблему можно решить за время O ( n log ³ n ) , где n — количество вершин, путем сведения задачи к максимальному потоку с несколькими источниками и стоками. ^[4]

Алгоритмы для произвольных графов

Алгоритм цветения находит совпадение максимальной мощности в общих (не обязательно двудольных) графах. Оно протекает во времени . Лучшая производительность O ( √ VE ) для общих графов, соответствующая производительности алгоритма Хопкрофта – Карпа на двудольных графах , может быть достигнута с помощью гораздо более сложного алгоритма Микали и Вазирани. ^[5] Такая же граница была достигнута с помощью алгоритма Блюма (де) ^[6] и алгоритма Габоу и Тарьяна . ^[7] ${\displaystyle O(|V|^{2}\cdot |E|)}$

Альтернативный подход использует рандомизацию и основан на алгоритме быстрого умножения матриц . Это дает рандомизированный алгоритм для общих графов со сложностью . ^[8] Теоретически это лучше для достаточно плотных графов , но на практике алгоритм работает медленнее. ^[2] ${\displaystyle O(V^{2.376})}$

Другие алгоритмы решения этой задачи рассмотрены Дуаном и Петти ^[9] (см. Таблицу I). Что касается алгоритмов аппроксимации , они также отмечают, что алгоритм Цветения и алгоритмы Микали и Вазирани можно рассматривать как алгоритмы аппроксимации , работающие за линейное время для любой фиксированной границы ошибки.

Приложения и обобщения

• Найдя паросочетание максимальной мощности, можно решить, существует ли идеальное паросочетание .
• Задача нахождения паросочетания максимального веса во взвешенном графе называется задачей паросочетания максимального веса , а ее ограничение на двудольные графы называется задачей назначения . Если каждой вершине можно сопоставить сразу несколько вершин, то это обобщенная задача о назначениях .
• Сопоставление приоритетов — это особое сопоставление максимальной мощности, при котором вершины с приоритетом сопоставляются первыми.
• Задача нахождения паросочетания максимальной мощности в гиперграфах NP-полна даже для 3-однородных гиперграфов. ^[10]

Рекомендации

1. Уэст, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Прентис Холл, Глава 3, ISBN 0-13-014400-2
2. Чандран, Бала Г.; Хохбаум, Дорит С. (2011), Практические и теоретические улучшения двустороннего сопоставления с использованием алгоритма псевдопотока , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C, перечисленные выше теоретически эффективные алгоритмы, как правило, плохо работают на практике..
3. Мэдри, А. (2013), «Навигация по центральному пути с электрическими потоками: от потоков к сопоставлениям и обратно», Основы компьютерных наук (FOCS), 54-й ежегодный симпозиум IEEE 2013 г. , стр. 253–262, arXiv : 1307.2205 , Бибкод : 2013arXiv1307.2205M
4. Боррадайл, Гленкора; Кляйн, Филип Н.; Мозес, Шей; Нуссбаум, Яхав; Вульф – Нильсен, Кристиан (2017), «Максимальный поток с несколькими источниками и несколькими стоками в направленных плоских графах в почти линейном времени», SIAM Journal on Computing , 46 (4): 1280–1303, arXiv : 1105.2228 , doi : 10.1137 /15M1042929, MR  3681377, S2CID  207071917
5. Микали, С .; Вазирани В.В. (1980), " Алгоритм поиска максимального паросочетания в общих графах", Учеб. 21-й симпозиум IEEE. Основы информатики , стр. 17–27, номер документа : 10.1109/SFCS.1980.12, S2CID  27467816. ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}$.
6. Блюм, Норберт (1990). Патерсон, Майкл С. (ред.). «Новый подход к максимальному совпадению в общих графах» (PDF) . Автоматы, языки и программирование . Конспекты лекций по информатике. Берлин, Гейдельберг: Springer. 443 : 586–597. дои : 10.1007/BFb0032060. ISBN 978-3-540-47159-2.
7. Габоу, Гарольд Н ; Тарьян, Роберт Э (1 октября 1991 г.). «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов» (PDF) . Журнал АКМ . 38 (4): 815–853. дои : 10.1145/115234.115366. S2CID  18350108.
8. Муха, М.; Санковски, П. (2004), «Максимальные совпадения посредством исключения Гаусса» (PDF) , Proc. 45-й симпозиум IEEE. Основы информатики , стр. 248–255.
9. Дуань, Ран; Петти, Сет (01 января 2014 г.). «Приближение линейного времени для согласования максимального веса» (PDF) . Журнал АКМ . 61 : 1–23. дои : 10.1145/2529989. S2CID  207208641.
10. Карп, Ричард М. (1972), Миллер, Раймонд Э.; Тэтчер, Джеймс В.; Болингер, Джин Д. (ред.), «Сводимость комбинаторных задач», Сложность компьютерных вычислений: материалы симпозиума по сложности компьютерных вычислений, состоявшегося 20–22 марта 1972 г. в Исследовательском центре IBM Томаса Дж. Уотсона. , Йорктаун-Хайтс, Нью-Йорк, и спонсируется Управлением военно-морских исследований, математической программой, Всемирной торговой корпорацией IBM и Отделом математических наук IBM , серия исследовательских симпозиумов IBM, Бостон, Массачусетс: Springer US, стр. 85–103. , doi : 10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2