Алгоритм Хопкрофта — Карпа

Алгоритм Хопкрофта — Карпа — алгоритм, принимающий на вход двудольный граф и возвращающий максимальное по мощности паросочетание, то есть наибольшее множество рёбер, таких что никакие два не имеют общую вершину. Асимптотика времени работы алгоритма составляет $O(|E|{\sqrt {|V|}})$ в худшем случае (здесь $E$ — множество рёбер графа, а $V$ — множество его вершин). В случае плотных графов время работы ограничивается $O(|V|^{2.5})$, а для случайного графа алгоритм работает почти за линейное время.

Алгоритм Хопкрофта — Карпа
Назван в честь	Джон Хопкрофт и Ричард Мэннинг Карп
Автор	Джон Хопкрофт, Ричард Мэннинг Карп и Александр Карзанов
Предназначение	Поиск максимального паросочетания
Структура данных	Граф
Худшее время	$O(E{\sqrt {V}})$
Затраты памяти	$O(V)$

Алгоритм был создан Джоном Хопкрофтом и Ричардом Карпом в 1973 году. Как и ранее созданные алгоритмы (такие как венгерский алгоритм и алгоритм из работы Эдмондса), алгоритм Хопкрофта — Карпа в цикле увеличивает паросочетание, находя увеличивающие пути (цепи, рёбра которых попеременно принадлежат паросочетанию и не принадлежат ему, причём первая и последняя вершина не принадлежат паросочетанию; выполнив чередование паросочетания вдоль цепи, то есть убрав из паросочетания рёбра, бывшие в цепи, и добавив те, которых в нём не было, можно получить большее паросочетание). Вместо того чтобы находить один увеличивающий путь, алгоритм находит максимальное множество кратчайших увеличивающих путей. В результате требуется лишь $O({\sqrt {|V|}})$ итераций. Та же идея используется в более сложных алгоритмах для поиска паросочетаний в недвудольных графах с тем же асимптотическим временем работы, как у алгоритма Хопкрофта — Карпа.

Описание задачи

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

Увеличивающие пути

Вершина, которая не является концом какого-либо ребра паросочетания $M$, называется свободной вершиной (для этого паросочетания). Алгоритм основан на понятии увеличивающего пути — пути, который начинается и заканчивается в свободной вершине, а внутри пути ребра, принадлежащие и не принадлежащие паросочетанию $M$, чередуются. Из определения следует, что все вершины такого пути, кроме первой и последней, обязаны быть несвободными. Увеличивающий путь может состоять из двух свободных вершин и одного ребра между ними (которое не лежит в паросочетании).

Если $M$ — паросочетание и $P$ — увеличивающий путь в $M$, то симметрическая разность двух множеств рёбер $M\oplus P$ является паросочетанием размера $|M|+1$. Таким образом, найдя увеличивающие пути, можно увеличить размер паросочетания.

Наоборот, пусть $M$ не оптимально и пусть $P$ есть симметрическая разность $M\oplus M^{*}$, где $M^{*}$ — оптимальное паросочетание. Поскольку $M$ и $M^{*}$ — паросочетания, каждая вершина в $P$ имеет степень не более двух. Значит, $P$ должно образовывать множество непересекающихся увеличивающих путей и циклов или путей, в которых рёбер из паросочетания столько же, сколько и не из него. Разность размеров $M$ и $M^{*}$ и есть число увеличивающих путей в $P$. Итак, если существует паросочетание $M^{*}$, большее текущего паросочетания $M$, также должен существовать увеличивающий путь. Если увеличивающего пути не существует, можно успешно прервать алгоритм, так как $M$ должно быть оптимальным.

Увеличивающие пути в задачах о паросочетаниях тесно связаны с увеличивающими путями, возникающими в задачах о максимальном потоке, путями, вдоль которых можно увеличить поток между истоком и стоком. Можно свести задачу о поиске наибольшего паросочетания к задаче поиска максимального потока. Технику, используемую в алгоритме Хопкрофта — Карпа, можно обобщить для произвольной транспортной сети, что приведёт к алгоритму Диница.

Алгоритм

Основной источник: Hopcroft & Karp (1973)

Пример работы алгоритма: потребовалось две фазы.

Ниже представлена структура алгоритма:

Вход: Двудольный граф $G(U\cup V,E)$

Выход: Паросочетание $M\subseteq E$

$M\leftarrow \emptyset$

цикл

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ максимальное множество непересекающихся по вершинам кратчайших увеличивающих путей

$M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})$

пока ${\mathcal {P}}\neq \emptyset$

Более подробно, пусть даны $U$ и $V$ — множества вершин двудольного графа $G$, а $E$ — множество его рёбер, соединяющих вершины из $U$ и $V$. Алгоритм, начиная с пустого паросочетания $M$, последовательно его увеличивает. На каждой фазе алгоритм делает следующее:

• Поиск в ширину (BFS) разбивает вершины графа на слои. BFS начинает с множества свободных вершин $U$, которые тем самым образуют первый слой разбиения (таким образом, первый слой содержит только не покрытые паросочетанием рёбра). На последующих уровнях поиска алгоритм добавляет вершины на новый уровень, чередуя рёбра: будет попеременно добавлять вершины, связанные ребром то в паросочетании, то вне его, поэтому в процессе поиска из вершины из $U$ мы всегда будем проходить по рёбрам не из паросочетания, а если вершина из $V$ — то наоборот. Поиск прерывается на уровне $k$, как только впервые будет достигнута хотя бы одна свободная вершина из $V$.
• Все свободные вершины из $V$ на этом слое $k$ обозначим как $F$. Получается, вершина $v$ принадлежит $F$ тогда и только тогда, когда в ней кончается кратчайший удлиняющий путь.
• Алгоритм находит максимальное множество непересекающихся по вершинам путей длины $k$. Это множество может быть найдено поиском в глубину (DFS), который использует найденное ранее разбиение на слои. Поиск может проходить лишь по рёбрам, которые ведут в неиспользованные вершины предыдущего слоя, и путь в дереве поиска в глубину должен чередоваться относительно паросочетания $M$. Как только увеличивающий путь войдёт в одну из вершин $F$, следует начать DFS от следующей вершины.
• Каждый из путей, который будет найден, используется для увеличения $M$.

Алгоритм прерывается, когда на какой-либо фазе BFS не находит ни одного увеличивающего пути (то есть $F$ пусто).

Анализ

Каждая фаза состоит из одного BFS и одного DFS, поэтому одна фаза выполняется за $O(|E|)$. Следовательно, первые ${\sqrt {|V|}}$ фаз в графе с $|V|$ вершинами и $|E|$ рёбрами имеют стоимость $O(|E|{\sqrt {|V|}})$. Можно показать, что каждая фаза увеличивает длину кратчайшего удлиняющего пути, по крайней мере, на 1: фаза находит максимальный набор дополняющих путей данной длины, так что любой оставшийся путь должен быть длиннее. Следовательно, после того как первые ${\sqrt {|V|}}$ фаз алгоритма завершились, кратчайший оставшийся увеличивающий путь имеет длину, по крайней мере, ${\sqrt {|V|}}$. Однако симметрическая разность оптимального паросочетания и текущего паросочетания $M$, найденного в предыдущих фазах, образует множество вершинно непересекающихся увеличивающих путей и чередующихся циклов. Если каждый путь имеет длину, по крайней мере, ${\sqrt {|V|}}$, может быть не более чем ${\sqrt {|V|}}$ путей, и размер оптимального паросочетания может отличаться от размера $M$ не более чем на ${\sqrt {|V|}}$. Так как каждая фаза алгоритма увеличивает размер паросочетания, по крайней мере, на 1, ещё может произойти не более ${\sqrt {|V|}}$ фаз.

Так как в худшем случае алгоритм имеет $2{\sqrt {|V|}}$ фаз, общее время работы составляет $O(|E|{\sqrt {|V|}})$ в худшем случае.

Однако во многих случаях алгоритм может быть гораздо быстрее, чем говорит оценка в худшем случае. Например, в случае разреженного двудольного случайного графа в 2006 году было показано (улучшая предыдущий результат), что с большой вероятностью все неоптимальные паросочетания имеют увеличивающие пути логарифмической длины. Как следствие, для таких графов количество итераций $O(\log |V|)$, а время работы алгоритма составляет $O(|E|\log |V|)$.

Сравнение с другими алгоритмами поиска максимального паросочетания

Для разреженных графов алгоритм Хопкрофта — Карпа имеет наилучшую асимптотику в худшем случае из всех известных алгоритмов, но для плотных графов более новый алгоритм имеет слегка лучшую границу $O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$. Этот алгоритм базируется на алгоритме проталкивания предпотока, а, когда паросочетание становится близко к оптимальному, переключается на метод Хопкрофта — Карпа.

Несколько авторов провели экспериментальное сравнение алгоритмов поиска максимального паросочетания. Их результаты показали, что в общем случае алгоритм Хопкрофта — Карпа на практике не так хорош, как в теории: его превосходят по производительности как простые BFS и DFS-стратегии по поиску увеличивающего пути, так и алгоритмы, основанные на методе проталкивания предпотока.

Недвудольные графы

Та же идея поиска максимального множества кратчайших увеличивающих путей также работает для нахождения паросочетаний максимальной мощности в недвудольных графах, и по тем же причинам алгоритм будет иметь не более $O({\sqrt {|V|}})$ фаз. Однако для недвудольных графов поиск удлиняющих путей в каждой фазе более сложен. Базируясь на более ранних работах, Micali & Vazirani (1980) показали, как выполнять фазу за линейное время, что привело к созданию алгоритма с той же верхней оценкой, что и у алгоритма Хопкрофта — Карпа для двудольных графов. Метод Micali — Vazirani сложен, и авторы не предоставили полных доказательств своих результатов; впоследствии Peterson & Loui (1988) опубликовали полное обоснование алгоритма Micali — Vazirani, а также были опубликованы другие алгоритмы: Gabow & Tarjan (1991) и Blum (2001). В 2012 году Vazirani предложил новое, упрощённое доказательство алгоритма Micali — Vazirani.

Псевдокод

Ниже приведён псевдокод алгоритма, близкий к реализации на Java.

/* 
 G = U ∪ V ∪ {NIL}
 where U and V are partition of graph and NIL is a special null vertex
*/
  
function BFS ()
    for u in U
        if Pair_U[u] == NIL
            Dist[u] = 0
            Enqueue(Q,u)
        else
            Dist[u] = ∞
    Dist[NIL] = ∞
    while Empty(Q) == false
        u = Dequeue(Q)
        if Dist[u] < Dist[NIL] 
            for each v in Adj[u]
                if Dist[ Pair_V[v] ] == ∞
                    Dist[ Pair_V[v] ] = Dist[u] + 1
                    Enqueue(Q,Pair_V[v])
    return Dist[NIL] != ∞

function DFS (u)
    if u != NIL
        for each v in Adj[u]
            if Dist[ Pair_V[v] ] == Dist[u] + 1
                if DFS(Pair_V[v]) == true
                    Pair_V[v] = u
                    Pair_U[u] = v
                    return true
        Dist[u] = ∞
        return false
    return true

function Hopcroft-Karp
    for each u in U
        Pair_U[u] = NIL
    for each v in V
        Pair_V[v] = NIL
    matching = 0
    while BFS() == true
        for each u in U
            if Pair_U[u] == NIL
                if DFS(u) == true
                    matching = matching + 1
    return matching

Пояснения

Пусть граф состоит из долей U и V. Ключевая идея состоит в добавлении двух фиктивных вершин с каждой стороны графа: uDummy, соединённую со всеми непокрытыми вершинами из U, и vDummy, соединённую со всеми непокрытыми вершинами из V. Теперь, если мы запустим BFS из uDummy в vDummy, мы получим кратчайший путь между непокрытой вершиной из U и непокрытой вершиной из V. Из-за двудольности графа путь будет чередоваться между U и V. Однако нужно удостовериться, что, идя из V в U, мы всегда выбираем ребро из паросочетания. Если не осталось вершин из паросочетания, то мы заканчиваем в vDummy. Руководствуясь этим критерием в процессе BFS, в конце получим кратчайший увеличивающий путь.

После того, как кратчайший увеличивающий путь будет найден, надо игнорировать все пути, которые длиннее его. BFS помечает вершины, расстояние от которых до истока 0. После выполнения BFS мы можем, стартуя из каждой вершины из U, не лежащей в паросочетании, идя по пути, в котором расстояние до следующей вершины больше расстояния до предыдущей на 1. Если мы в конце приходим в vDummy, расстояние до которой на 1 больше, чем расстояние до одной из вершин из V, по которой можно дойти по одному из кратчайших путей. В таком случае мы можем пойти дальше и обновить паросочетание для вершин на пути. Заметим, что каждая вершина V на пути, кроме самой последней, уже в паросочетании. Поэтому обновление паросочетания эквивалентно симметрической разности (то есть удалению тех рёбер пути, которые были в паросочетании, и добавлению тех, которых не было.

Как удостовериться, что увеличивающие пути не пересекаются по вершинам? Это уже обеспечено. После выполнения симметрической разности никакая из вершин пути не будет рассмотрена ещё раз, потому что Dist[ Pair_V[v] ] не будет равна Dist[u] + 1 (а будет в точности Dist[u]).

Зачем нужны следующие строчки?

Dist[u] = ∞
return false

Когда мы не можем найти никакой кратчайший увеличивающий путь из вершины u, DFS возвращает False. В этом случае, будет хорошо пометить эти вершины, чтобы не посещать их ещё раз. Чтобы отметить их, мы просто выставляем Dist[u] бесконечным.

Нам не нужен uDummy, потому что он лишь для того, чтобы складывать все вершины не из паросочетания в очередь BFS. Это можно сделать просто инициализацией. vDummy можно добавить в U для удобства во многих реализациях, и инициализировать паросочетание для всех вершин из V указателем на vDummy. Поэтому если в конце концов последняя вершина из U не находится в паросочетании ни с одной вершиной из V, то последней вершиной нашего удлиняющего пути будет vDummy. В псевдокоде выше vDummy обозначается Nil.

См. также

• Паросочетание
• Венгерский алгоритм
• Задача о назначениях

Литература

• Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993), Network Flows: Theory, Algorithms and Applications, Prentice-Hall.
• Alt, H.; Blum, N.; Mehlhorn, K.; Paul, M. (1991), "Computing a maximum cardinality matching in a bipartite graph in time $\scriptstyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)$", Information Processing Letters, 37 (4): 237—240, doi:10.1016/0020-0190(91)90195-N.
• Bast, Holger; Mehlhorn, Kurt; Schafer, Guido; Tamaki, Hisao (2006), "Matching algorithms are fast in sparse random graphs", Theory of Computing Systems, 39 (1): 3—14, doi:10.1007/s00224-005-1254-y.
• Blum, Norbert (2001), A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in General Graphs, Tech. Rep. 85232-CS, Computer Science Department, Univ. of Bonn.
• Chang, S. Frank; McCormick, S. Thomas (1990), A faster implementation of a bipartite cardinality matching algorithm, Tech. Rep. 90-MSC-005, Faculty of Commerce and Business Administration, Univ. of British Columbia. As cited by Setubal (1996).
• Darby-Dowman, Kenneth (1980), The exploitation of sparsity in large scale linear programming problems – Data structures and restructuring algorithms, Ph.D. thesis, Brunel University. As cited by Setubal (1996).
• Edmonds, Jack (1965), "Paths, Trees and Flowers", Canadian J. Math, 17: 449—467, doi:10.4153/CJM-1965-045-4, MR 0177907.
• Gabow, Harold N.; Tarjan, Robert E. (1991), "Faster scaling algorithms for general graph matching problems", Journal of the ACM, 38 (4): 815—853, doi:10.1145/115234.115366.
• Hopcroft, John E.; Karp, Richard M. (1973), "An n^5/2 algorithm for maximum matchings in bipartite graphs", SIAM Journal on Computing, 2 (4): 225—231, doi:10.1137/0202019.
• Micali, S.; Vazirani, V. V. (1980), "An $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17—27, doi:10.1109/SFCS.1980.12.
• Peterson, Paul A.; Loui, Michael C. (1988), "The general maximum matching algorithm of Micali and Vazirani", Algorithmica, 3 (1–4): 511—533, doi:10.1007/BF01762129.
• Motwani, Rajeev (1994), "Average-case analysis of algorithms for matchings and related problems", Journal of the ACM, 41 (6): 1329—1356, doi:10.1145/195613.195663.
• Setubal, João C. (1993), "New experimental results for bipartite matching", Proc. Netflow93, Dept. of Informatics, Univ. of Pisa, pp. 211—216. As cited by Setubal (1996).
• Setubal, João C. (1996), Sequential and parallel experimental results with bipartite matching algorithms, Tech. Rep. IC-96-09, Inst. of Computing, Univ. of Campinas.
• Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm, CoRR abs/1210.4594, arXiv:1210.4594.