Максимальное паросочетание
Постановка задачи
Пусть [math]\displaystyle{ G = (V, E) }[/math] – неориентированный граф, [math]\displaystyle{ n = |V| }[/math] и [math]\displaystyle{ m = |E| }[/math]. Паросочетание в графе [math]\displaystyle{ G }[/math] представляет собой подмножество [math]\displaystyle{ M \subseteq E }[/math], такое, что никакие два ребра в [math]\displaystyle{ M }[/math] не имеют общей конечной точки. Совершенное паросочетание представляет собой паросочетание кардинальности [math]\displaystyle{ n/2 }[/math]. Наиболее базовыми задачами, связанными с паросочетанием, являются поиск максимального паросочетания (т. е. паросочетания максимального размера) и, как частный случай, поиск совершенного паросочетания, если таковое существует. Можно также рассмотреть случай, когда задана весовая функция [math]\displaystyle{ w: E \to \mathbb{R} }[/math], и задача заключается в поиске паросочетания с максимальным весом.
Максимальное паросочетание и паросочетание с максимальным весом – две задачи, входящие в число самых фундаментальных алгоритмических задач на графах. Они также сыграли важную роль в развитии комбинаторной оптимизации и алгоритмики. Отличное описание приводится в классической монографии [10] Ловаса и Пламмера, полностью посвященной задачам о паросочетании. Более современное и более техническое обсуждение этой темы можно найти в работе [18].
Классический подход
Поиск максимального паросочетания за время, полиномиальное относительно [math]\displaystyle{ n }[/math], является весьма нетривиальной задачей. Первое такое решение было дано Эдмондсом [3] в 1965 году; его временная сложность составляет [math]\displaystyle{ O(n^3) }[/math]. Изобретательный алгоритм Эдмондса использует комбинаторный подход, основанный на аугментальных цепях и цветках. Затем последовало несколько усовершенствований, кульминацией которых стал алгоритм со сложностью [math]\displaystyle{ O(m \sqrt{n}) }[/math], предложенный Микали и Вазирани [11] в 1980 году (полное доказательство корректности этого алгоритма было дано Вазирани гораздо позже в [19]; достойное изложение алгоритма и его обобщение на взвешенный случай можно найти в работе Габова и Тарьяна [4]). Превзойти этот предел оказалось очень сложно; нескольким авторам удалось достичь лишь логарифмического ускорения для определенных значений [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math]. Все эти алгоритмы в основном следуют комбинаторному подходу, предложенному Эдмондсом.
В случае двудольных графов решить задачу поиска максимального паросочетания гораздо проще. Сложность [math]\displaystyle{ O(m \sqrt{n}) }[/math] для этого случая была достигнута уже в 1971 году Хопкрофтом и Карпом [6], а ключевые идеи первых полиномиальных алгоритмов восходят к 1920-м годам и работам Кёнига и Эгервари (см. [10] и [18]).
Алгебраический подход
Примерно в то же время, когда Микали и Вазирани представили свой алгоритм для нахождения паросочетания, Ловас предложил рандомизированную (на основе метода Монте-Карло) редукцию задачи проверки наличия совершенного паросочетания в заданном графе с [math]\displaystyle{ n }[/math] вершинами к задаче вычисления определенного детерминанта матрицы [math]\displaystyle{ n \times n }[/math]. Используя быстрый алгоритм гауссова исключения Хопкрофта-Банча [1], этот детерминант можно вычислить за [math]\displaystyle{ MM(n) = O(n^{\omega}) }[/math] – время, необходимое для умножения двух матриц [math]\displaystyle{ n \times n }[/math]. Поскольку [math]\displaystyle{ \omega \lt 2,38 }[/math] (см. [2]), для плотных графов этот алгоритм асимптотически быстрее алгоритма Микали и Вазирани.
Однако алгоритм Ловаса только проверяет наличие совершенного паросочетания, но не находит его. Использование его для прямолинейного поиска совершенных или максимальных паросочетаний дает алгоритм со сложностью [math]\displaystyle{ O(mn^{\omega}) = O(n^{4,38}) }[/math]. Таким образом, основная проблема в этой области заключалась в том, можно ли на самом деле найти максимальные паросочетания за время [math]\displaystyle{ O(n^{\omega}) }[/math].
Первый шаг в этом направлении был сделан в 1989 году Рэбином и Вазирани [15]. Они показали, что максимальные паросочетания можно найти за время [math]\displaystyle{ O(n^{\omega + 1}) = O(n^{3,38}) }[/math].
Основные результаты
В следующих теоремах сведены основные результаты работы [12].
Теорема 1. Максимальное паросочетание в графе [math]\displaystyle{ G }[/math] с [math]\displaystyle{ n }[/math] вершинами можно найти за время [math]\displaystyle{ O(n^3) }[/math] (Лас-Вегас), выполнив гауссово исключение над определенной матрицей, связанной с [math]\displaystyle{ G }[/math].
Теорема 2. Максимальное паросочетание в двудольном графе [math]\displaystyle{ G }[/math] с [math]\displaystyle{ n }[/math] вершинами можно найти за время [math]\displaystyle{ \tilde{O}(n^{\omega}) }[/math] (Лас-Вегас), выполнив быстрое гауссово исключение Хопкрофта-Банча над определенной матрицей, связанной с [math]\displaystyle{ G }[/math].
Теорема 3. Максимальное паросочетание в графе с [math]\displaystyle{ n }[/math] вершинами можно найти за время [math]\displaystyle{ \tilde{O}(n^{\omega}) }[/math] (Лас-Вегас).
Примечание. [math]\displaystyle{ \tilde{O} }[/math]-нотация подавляет полилогарифмические коэффициенты, поэтому [math]\displaystyle{ \tilde{O}(f(n)) }[/math] означает [math]\displaystyle{ O(f(n)log^k(n)) }[/math] для некоторого [math]\displaystyle{ k }[/math].
Вкратце обсудим эти результаты. Теорема 1 показывает, что эффективные алгоритмы нахождения паросочетания могут быть простыми. Это сильно контрастирует с алгоритмами, основанными на аугментальных цепях и цветках, которые обычно считаются довольно сложными.
Две другие теоремы показывают, что для плотных графов алгебраический подход асимптотически быстрее комбинаторного.
Алгоритм для двудольного случая очень прост. Единственной неэлементарной его частью является алгоритм быстрого умножения матриц, используемый в качестве «черного ящика» в алгоритме Хопкрофта-Банча. Однако алгоритм для общего случая сложен и использует сильные структурные результаты из теории паросочетаний. Естественный вопрос заключается в том, возможно ли предложить более простой и/или чисто алгебраический алгоритм. Положительный ответ на этот вопрос дал Харви [5].
За этим последовало несколько других связанных результатов. Муча и Санковски [13] показали, что максимальные паросочетания в плоских графах можно найти за время [math]\displaystyle{ \tilde{O}(n^{\omega/2}) = \tilde{O}(n^{1,19}) }[/math], что в настоящее время является самым быстрым из известных способов. Юстер и Цвик [20] распространили это на любой класс исключенных миноров графов. Санковски [16] предложил эффективный алгоритм класса RNC для поиска паросочетаний (см. также у Малмули и др. [14] и Карпа и др. [8] более ранние и менее эффективные RNC-алгоритмы поиска паросочетаний, а также у Карлоффа [7] – описание общей техники создания такого алгоритма Лас-Вегас). Он также обобщил теорему 2 на случай взвешенных двудольных графов с целочисленными весами из интервала [math]\displaystyle{ [0, ..., W] }[/math], показав, что в этом случае паросочетания с максимальным весом могут быть найдены за время [math]\displaystyle{ \tilde{O}(Wn^{\omega}) }[/math] (см. [17]).
Применение
Задача поиска максимальных паросочетаний имеет множество вариантов применения, как на практике, так и в качестве подпрограммы в других алгоритмах. Детальное обсуждение практических способов применения можно найти в монографии Ловаса и Пламмера [10]. Однако следует отметить, что алгоритмы, основанные на быстром умножении матриц, совершенно непрактичны, поэтому обсуждаемые здесь результаты не очень полезны для этих вариантов применения.
С теоретической точки зрения более быстрые алгоритмы поиска максимальных паросочетаний (паросочетаний с максимальным весом) позволяют получить более быстрые алгоритмы для связанных задач: задачи о непересекающихся [math]\displaystyle{ s-t }[/math] путях, о минимальном реберном покрытии (покрытии с минимальным весом), задачи о [math]\displaystyle{ b }[/math]-паросочетаниях (с максимальным весом), задачи о [math]\displaystyle{ b }[/math]-коэффициенте(с максимальным весом), задачи о T-соединении (с максимальным весом) или задачи китайского почтальона. Подробное обсуждение всех этих вариантов применения см. в [10] и [18].
Алгебраический алгоритм теоремы 1 также имеет значительную образовательную ценность. Комбинаторные алгоритмы для общей задачи поиска максимального паросочетания обычно считаются слишком сложными для курса бакалавриата. Это определенно не относится к алгебраическому алгоритму стоимостью [math]\displaystyle{ O(n^3) }[/math].
Открытые вопросы
Одной из наиболее важных нерешенных задач в этой области является обобщение приведенных результатов на взвешенные графы. Санковски [17] предлагает алгоритм [math]\displaystyle{ \tilde{O}(Wn^{\Omega}) }[/math] для двудольных графов с целыми весами из интервала [math]\displaystyle{ [0, ..., W] }[/math]. Сложность этого алгоритма плоха с точки зрения W. Неизвестно ни одного эффективного алгебраического алгоритма для взвешенных графов общего вида.
Еще одной интересной, но, скорее всего, очень сложной задачей является дерандомизация обсуждаемых алгоритмов.
См. также
Литература
1. Bunch, J., Hopcroft, J.: Triangular Factorization and Inversion by Fast Matrix Multiplication. Math. Comput. 125, 231-236 (1974)
2. Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. In: Proceedings of the 19th Annual ACM Conference on Theory of Computing (STOC), 1987, pp. 1-6
3. Edmonds, J.: Paths,Trees,and Flowers.Canad.J. Math. 17,449-467(1965)
4. Gabow, H.N., Tarjan, R.E.: Faster scaling algorithms for general graph matching problems. J. ACM 38(4), 815-853 (1991)
5. Harvey, N.: Algebraic Structures and Algorithms for Matching and Matroid Problems. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006
6. Hopcroft, J.E., Karp, R.M.: An O(n5/2) Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2, 225-231 (1973)
7. Karloff, H.: A Las Vegas RNC algorithm for maximum matching. Combinatorica 6,387-391 (1986)
8. Karp, R., Upfal, E., Widgerson, A.: Constructing a perfect matching is in Random NC. Combinatorica 6,35-48 (1986)
9. Lovasz, L.: On Determinants, Matchings and Random Algorithms. In: Budach, L. (ed.) Fundamentals of Computation Theory, FCT'79, pp. 565-574. Akademie-Verlag, Berlin (1979)
10. Lovasz, L., Plummer, M.D.: Matching Theory. Akademiai Kiado - North Holland, Budapest (1986)
11. Micali, S.,Vazirani,V.V.: An O(pVE) Algorithm for Finding Maximum Matching in General Graphs. In: Proceedings of the 21 st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1980, pp. 17-27
12. Mucha, M., Sankowski, P.: Maximum Matchings via Gaussian Elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2004 pp.248-255
13. Mucha, M., Sankowski, P.: Maximum Matchings in Planar Graphs via Gaussian Elimination. Algorithmica 45,3-20 (2006)
14. Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. In: Proceedings of the 19th Annual ACM Conference on Theory of Computing, pp. 345-354. ACM Press, New York (1987)
15. Rabin, M.O., Vazirani, V.V.: Maximum Matchings in General Graphs Through Randomization. J. Algorithms 10, 557-567 (1989)
16. Sankowski, P.: Processor Efficient Parallel Matching. In: Proceeding of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2005, pp. 165-170
17. Sankowski, P.: Weighted Bipartite Matching in Matrix Multiplication Time. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, 2006, pp.274-285
18. Schrijver, A.: Combinatorial optimization: polyhedra and efficiency. Springer, Berlin Heidelberg (2003)
19. Vazirani, V.V.: A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(pVE) Maximum Matching Algorithm. Combinatorica 14(1), 71-109 (1994)
20. Yuster, R., Zwick, U.: Maximum Matching in Graphs with an Excluded Minor. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007