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

Сопоставление максимальной мощности является фундаментальной проблемой теории графов . ^[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 \in X$ к некоторому $y \in Y$ и обновляет сопоставление $M$ , беря симметричную разность этого пути с $M$ (при условии, что такой путь существует). Поскольку каждый путь может быть найден за $время O (E)$ , время выполнения равно $O (VE)$ , а максимальное совпадение состоит из ребер $E$ которые переносят поток от $X$ к $Y.$ ,

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

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

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

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

Использование логических операций со словами большого размера $\lambda$ сложность дополнительно улучшена до ^[2]

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

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

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

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

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

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

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

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

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

Ссылки

^ Уэст, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Прентис Холл, глава 3, ISBN 0-13-014400-2
^ Jump up to: ^а ^б ^с Чандран, Бала Г.; Хохбаум, Дорит С. (2011), Практические и теоретические улучшения для двустороннего сопоставления с использованием алгоритма псевдопотока , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C , перечисленные выше теоретически эффективные алгоритмы, как правило, плохо работают на практике .
^ Мэдри, А. (2013), «Навигация по центральному пути с электрическими потоками: от потоков к сопоставлениям и обратно», Основы информатики (FOCS), 54-й ежегодный симпозиум IEEE 2013 г. , стр. 253–262, arXiv : 1307.2205 , Bibcode : 2013arXiv1307.2205M
^ Боррадейл, Гленкора; Кляйн, Филип Н.; Мозес, Шей; Нуссбаум, Яхав; Вульф-Нильсен, Кристиан (2017), «Максимальный поток с несколькими источниками и несколькими стоками в направленных плоских графах в почти линейном времени», SIAM Journal on Computing , 46 (4): 1280–1303, arXiv : 1105.2228 , doi : 10.1137 /15М1042929 , МР 3681377 , С2КИД 207071917
^ Микали, С .; Вазирани, В.В. (1980), «Ан $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ Алгоритм поиска максимального соответствия в общих графах», Proc. 21st IEEE Symp. Foundations of Computer Science , стр. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID 27467816 .
^ Блюм, Норберт (1990), «Новый подход к максимальному совпадению в общих графах» (PDF) , в Патерсоне, Майке (редактор), «Автоматы, языки и программирование», 17-й международный коллоквиум, ICALP90, Уорикский университет, Англия, Великобритания, 16–20 июля 1990 г., Труды , конспекты лекций по информатике, том. 443, Springer, стр. 586–597, doi : 10.1007/BFb0032060.
^ Габоу, Гарольд Н ; Тарьян, Роберт Э (1 октября 1991 г.). «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов» (PDF) . Журнал АКМ . 38 (4): 815–853. дои : 10.1145/115234.115366 . S2CID 18350108 .
^ Муха, М.; Санковски, П. (2004), «Максимальные совпадения посредством исключения по Гауссу» (PDF) , Proc. 45-й симпозиум IEEE. Основы информатики , стр. 248–255.
^ Дуан, Ран; Петти, Сет (01 января 2014 г.). «Приближение линейного времени для согласования максимального веса» (PDF) . Журнал АКМ . 61 : 1–23. дои : 10.1145/2529989 . S2CID 207208641 .
^ Карп, Ричард М. (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

[Wes01-1] Уэст, Дуглас Брент (1999), Введение в теорию графов (2-е изд.), Прентис Холл, глава 3, ISBN 0-13-014400-2

[Chandran-2] Jump up to: ^а ^б ^с Чандран, Бала Г.; Хохбаум, Дорит С. (2011), Практические и теоретические улучшения для двустороннего сопоставления с использованием алгоритма псевдопотока , arXiv : 1105.1569 , Bibcode : 2011arXiv1105.1569C , перечисленные выше теоретически эффективные алгоритмы, как правило, плохо работают на практике .

[3] Мэдри, А. (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 /15М1042929 , МР 3681377 , С2КИД 207071917

[5] Микали, С .; Вазирани, В.В. (1980), «Ан $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ Алгоритм поиска максимального соответствия в общих графах», Proc. 21st IEEE Symp. Foundations of Computer Science , стр. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID 27467816 .

[6] Блюм, Норберт (1990), «Новый подход к максимальному совпадению в общих графах» (PDF) , в Патерсоне, Майке (редактор), «Автоматы, языки и программирование», 17-й международный коллоквиум, ICALP90, Уорикский университет, Англия, Великобритания, 16–20 июля 1990 г., Труды , конспекты лекций по информатике, том. 443, Springer, стр. 586–597, doi : 10.1007/BFb0032060.

[7] Габоу, Гарольд Н ; Тарьян, Роберт Э (1 октября 1991 г.). «Алгоритмы более быстрого масштабирования для общих задач сопоставления графов» (PDF) . Журнал АКМ . 38 (4): 815–853. дои : 10.1145/115234.115366 . S2CID 18350108 .

[Mucha-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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]