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

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

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

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

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

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

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

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

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

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

${\displaystyle M\leftarrow \emptyset }$

цикл

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

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

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

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

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

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

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

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

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

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

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

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

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

/* 
 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

Dist[u] = ∞
return false

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

• 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 ${\displaystyle \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, <http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/2001/85232-CS.ps.gz>.
• 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.
• 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 ${\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}$ algorithm for finding maximum matching in general graphs, Proc. 21st IEEE Symp. Foundations of Computer Science, с. 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, с. 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, <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.3539>.
• Vazirani, Vijay (2012), An Improved Definition of Blossoms and a Simpler Proof of the MV Matching Algorithm, CoRR abs/1210.4594.