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

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

Сопоставление максимальной мощности является фундаментальной проблемой в теории графов . ^[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 , которое для | X | < | Y | равно

${\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]

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

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

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

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

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

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

Ссылки

1. Уэст, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Prentice Hall, Глава 3, ISBN 0-13-014400-2
2. Чандран, Бала Г.; Хохбаум, Дорит С. (2011), Практические и теоретические улучшения для двудольного сопоставления с использованием алгоритма псевдопотока , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C, теоретически эффективные алгоритмы, перечисленные выше, как правило, плохо работают на практике.
3. Madry, A (2013), «Навигация по центральному пути с помощью электрических потоков: от потоков к согласованиям и обратно», Основы компьютерной науки (FOCS), 54-й ежегодный симпозиум IEEE 2013 г. , стр. 253–262, arXiv : 1307.2205 , Bibcode : 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, doi :10.1109/SFCS.1980.12, S2CID  27467816 ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}$.
6. Блум, Норберт (1990), «Новый подход к максимальному паросочетанию в общих графах» (PDF) , в Патерсон, Майк (ред.), Автоматы, языки и программирование, 17-й международный коллоквиум, ICALP90, Уорикский университет, Англия, Великобритания, 16–20 июля 1990 г., Труды , Заметки лекций по информатике, т. 443, Springer, стр. 586–597, doi :10.1007/BFb0032060
7. Габов, Гарольд Н .; Тарьян, Роберт Э. (1991-10-01). "Быстрые алгоритмы масштабирования для общих задач сопоставления графов" (PDF) . Журнал ACM . 38 (4): 815–853. doi :10.1145/115234.115366. S2CID  18350108.
8. Муха, М.; Санковски, П. (2004), «Максимальные соответствия с помощью метода исключения Гаусса» (PDF) , Труды 45-го симпозиума IEEE. Основы компьютерной науки , стр. 248–255
9. Дуань, Ран; Петти, Сет (2014-01-01). "Линейное приближение по времени для максимального соответствия весов" (PDF) . Журнал ACM . 61 : 1–23. doi :10.1145/2529989. S2CID  207208641.
10. Карп, Ричард М. (1972), Миллер, Рэймонд Э.; Тэтчер, Джеймс У.; Болингер, Джин Д. (ред.), «Сводимость среди комбинаторных проблем», Сложность компьютерных вычислений: Труды симпозиума по сложности компьютерных вычислений, состоявшегося 20–22 марта 1972 г. в исследовательском центре IBM Thomas J. Watson, Йорктаун-Хайтс, Нью-Йорк, и спонсируемого Управлением военно-морских исследований, Математической программой, IBM World Trade Corporation и Отделом математических наук IBM Research , Серия исследовательских симпозиумов IBM, Бостон, Массачусетс: Springer US, стр. 85–103, doi :10.1007/978-1-4684-2001-2_9, ISBN 978-1-4684-2001-2