Algoritmo de Hopcroft–Karp

Em ciência da computação, o algoritmo de Hopcroft–Karp é um algoritmo que recebe como entrada um grafo bipartido e produz como saída um máximo de cardinalidade de acoplamento – um conjunto de quantas arestas forem possíveis com a propriedade de que não há duas bordas compartilhando um ponto na extremidade. Ele roda em tempo ${\displaystyle O(|E|{\sqrt {|V|}})}$ no pior caso, onde ${\displaystyle E}$ é o conjunto de arestas do grafo, e ${\displaystyle V}$ é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se ${\displaystyle O(|V|^{2.5})}$ e para grafos aleatórios ele é executado em tempo quase linear.

O algoritmo foi encontrado por John Hopcroft e Richard Karp (1973). Como nos métodos anteriores para acoplamento, tais como o algoritmo húngaro e o trabalho de Edmonds (1965), o algoritmo de Hopcroft–Karp aumenta várias vezes o tamanho de um acoplamento parcial encontrando caminhos extensores. No entanto, em vez de encontrar apenas um único caminho extensor por iteração, o algoritmo encontra um conjunto máximo de caminhos extensores mais curtos. Como resultado, apenas ${\displaystyle O({\sqrt {n}})}$ iterações são necessárias. O mesmo princípio também foi utilizado para desenvolver algoritmos mais complicados para acoplamentos não-bipartidos com o mesmo tempo de execução assintótica do algoritmo de Hopcroft–Karp.

Caminhos Extensores

Um vértice que não é uma extremidade de uma aresta em algum acoplamento parcial ${\displaystyle M}$ é chamado de vértice livre. O conceito básico do algoritmo baseia-se em que cada caminho extensor, um caminho que começa em um vértice livre, termina em um vértice livre, e alterna entre arestas acopladas e não-acopladas dentro do caminho. Note que, exceto para os pontos da extremidade, todos os outros vértices (se houver) no caminho extensor devem ser vértices não-livres. Um caminho extensor poderia consistir em apenas dois vértices (ambos vértices livres) e uma única aresta não-acoplada entre elas. 

Se ${\displaystyle M}$ é um acoplamento, e ${\displaystyle P}$ é um caminho extensor relativo a ${\displaystyle M}$, então a diferença simétrica dos dois conjuntos de arestas, ${\displaystyle M\oplus P}$, formaria um acoplamento de tamanho ${\displaystyle |M|+1}$. Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.

Por outro lado, suponha que um acoplamento ${\displaystyle M}$ não é ótimo, e seja ${\displaystyle P}$ a diferença simétrica ${\displaystyle M\oplus M^{*}}$ onde ${\displaystyle M^{*}}$ é um acoplamento ótimo. Pelo fato de ${\displaystyle M}$ e ${\displaystyle M^{*}}$ serem ambos acoplamentos, cada vértice tem grau no máximo 2 em ${\displaystyle P}$. Então ${\displaystyle P}$ deve formar uma coleção de caminhos extensores disjuntos e ciclos ou caminhos em que arestas acopladas e não acopladas são de igual número; a diferença de tamanho entre ${\displaystyle M}$ e ${\displaystyle M^{*}}$ é o número de caminhos extensores em ${\displaystyle P}$. Assim, se nenhum caminho extensor for encontrado, um algoritmo pode terminar com segurança, já que neste caso ${\displaystyle M}$ deve ser ótimo.

Um caminho extensor em um problema de acoplamento está intimamente relacionado com o surgimento de problemas do fluxo máximo, caminhos ao longo do qual se pode aumentar a quantidade de fluxo entre os terminais do fluxo. É possível transformar o problema do acoplamento bipartido em uma instância máxima de fluxo, tal que os caminhos alternados do problema do acoplamento se tornam caminhos extensores do problema do fluxo.^[1] De fato, uma generalização da técnica usada pelo algoritmo de Hopcroft–Karp para um fluxo arbitrário de redes é conhecido como algoritmo de Dinic.

Entrada: Grafo bipartido ${\displaystyle G(U\cup V,E)}$

Saída: Acoplamento ${\displaystyle M\subseteq E}$

${\displaystyle M\leftarrow \emptyset }$

repita

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$ conjunto máximo de vértices disjuntos de caminhos extensores mais curtos

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

até ${\displaystyle {\mathcal {P}}=\emptyset }$

Algoritmo

Sejam ${\displaystyle U}$ e ${\displaystyle V}$ dois conjuntos da bipartição de ${\displaystyle G}$, e considere o acoplamento de  ${\displaystyle U}$ para ${\displaystyle V}$ a qualquer tempo sendo representado como um conjunto ${\displaystyle M}$.

O algoritmo é executado em fases. Cada fase consiste nos seguintes passos.

• Uma busca em largura particiona os vértices do grafo em camadas. Os vértices livres em ${\displaystyle U}$ são usados como sendo os vértices iniciais dessa busca e formando a primeira camada dessa partição. No primeiro nível da busca, existem apenas arestas não acopladas, desde que vértices livres em ${\displaystyle U}$ são por definição não adjacentes a nenhuma aresta não acoplada. Em níveis subsequentes da busca, as arestas que cruzam são obrigados a alternar entre acopladas e não acopladas. Ou seja, na busca de sucessores de um vértice em ${\displaystyle U}$, somente arestas não acopladas podem ser cruzadas, enquanto a partir de um vértice em ${\displaystyle V}$ somente arestas acopladas podem ser cruzadas. A busca termina na primeira camada ${\displaystyle k}$ onde um ou mais vértices livres em ${\displaystyle V}$ são alcançados.
• Todos os vértices livres em  ${\displaystyle V}$ na camada ${\displaystyle k}$ são reunidas em um conjunto ${\displaystyle F}$. Ou seja, um vértice ${\displaystyle v}$ é colocado em ${\displaystyle F}$ se e somente se ele termina um caminho extensor mais curto.
• O algoritmo acha um conjunto máximo de vértices disjuntos de caminhos extensores de tamanho ${\displaystyle k}$. Este conjunto pode ser computado por uma busca em profundidade de ${\displaystyle F}$ para os vértices livres em ${\displaystyle U}$, usando a camada da busca em largura para guiar a busca: a profundidade da busca somente é permitida para seguir as arestas que levam para um vértice não utilizado na camada anterior, e os caminhos da árvore da busca em profundidade devem alternar entre arestas acopladas e não acopladas. Uma vez que um caminho extensor que envolva um dos vértices em ${\displaystyle F}$, a busca em profundidade é continuada a partir do próximo vértice de início.
• Cada um dos caminhos encontrados desta forma é utilizado para ampliar ${\displaystyle M}$.

O algoritmo termina quando não há mais caminhos extensores a serem encontrados em uma das fases da busca em largura.

Análise

Cada fase consiste em uma única busca em largura e uma única busca em profundidade. Assim, uma única fase pode ser implementada em tempo linear. No entanto, as primeiras ${\displaystyle {\sqrt {|V|}}}$ fases, em um grafo com ${\displaystyle |V|}$ vértices e ${\displaystyle |E|}$ arestas, levam um tempo ${\displaystyle O(|E|{\sqrt {|V|}})}$.

Pode ser demonstrado que cada fase aumenta o tamanho do caminho extensor mais curto no mínimo em um: a fase encontra um conjunto máximo de caminhos extensores dado um comprimento, portanto, qualquer caminho extensor restante deve ser maior. Assim, uma vez que ${\displaystyle {\sqrt {|V|}}}$ fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo ${\displaystyle {\sqrt {|V|}}}$ arestas. No entanto, a diferença simétrica de um eventual acoplamento ótimo e de um acoplamento parcial M encontrado pelas fases iniciais formam uma coleção de vértices disjuntos de caminhos extensores e ciclos alternados. Se cada um dos caminhos nesta coleção tem comprimento de pelo menos ${\displaystyle {\sqrt {|V|}}}$, pode haver no máximo ${\displaystyle {\sqrt {|V|}}}$ caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de ${\displaystyle M}$ por no máximo ${\displaystyle {\sqrt {|V|}}}$ arestas. Uma vez que cada fase do algoritmo aumenta o tamanho do acoplamento por pelo menos um, pode haver no máximo ${\displaystyle {\sqrt {|V|}}}$ fases adicionais antes do algoritmo terminar.

Uma vez que o algoritmo executa um total de, no máximo ${\displaystyle 2{\sqrt {|V|}}}$ fases, é preciso um tempo total de ${\displaystyle O(|E|{\sqrt {|V|}})}$ no pior caso.

Em muitos casos, no entanto, o tempo gasto pelo algoritmo pode ser ainda mais rápido do que a análise de pior caso indica. Por exemplo, no caso médio para grafos esparsos aleatórios , Bast et al. (2006) (melhorando o resultado anterior de Motwani 1994) mostrou com grande probabilidade que todos os acoplamentos não ótimos possuem caminhos extensores de tamanho logaritmo. Como consequência, para esses grafos, o algoritmo de Hopcroft–Karp leva ${\displaystyle O(\log |V|)}$ fases e um tempo total de ${\displaystyle O(|E|\log |V|)}$.

Comparação com outros algoritmos de correspondência bipartida

Para grafos esparsos o algoritmo de Hopcroft–Karp continua a ter a melhor performance conhecida no pior caso, no entanto para grafos densos um algoritmo mais recente por Alt et al. (1991) alcança um limitante de tempo um pouco melhor , ${\displaystyle O\left(n^{1.5}{\sqrt {\frac {m}{\log n}}}\right)}$. Este algoritmo é baseado no uso de um algoritmo de fluxo máximo de push-relabel e, em seguida, quando um acoplamento for criado por este algoritmo, este torna-se perto de ótimo, alternando para o método de Hopcroft–Karp.

Vários autores têm realizado comparações experimentais em algoritmos de acoplamento bipartido. Esses resultados em geral tendem a mostrar que o método de Hopcroft–Karp não é tão bom na prática quanto na teoria: ele é superado por uma simples busca em largura e estratégias de busca em profundidade para encontrar caminhos extensores, e pelas técnicas de push-relabel.^[2]

Grafos não bipartidos

A mesma ideia de achar um conjunto máximo de caminhos extensores mais curtos funciona também para achar acoplamentos de cardinalidade máxima em grafos não bipartidos, e pelas mesmas razões dos algoritmos baseados nessa mesma ideia levam ${\displaystyle O({\sqrt {|V|}})}$ fases. No entanto, para grafos não bipartidos, a tarefa de achar um caminho extensor em cada fase é mais difícil. Com base no trabalho de vários predecessores mais lentos, Micali & Vazirani (1980) mostraram como implementar uma fase em tempo linear, resultado em um algoritmo de acoplamento não bipartido com o mesmo limitante de tempo do que o algoritmo de Hopcroft–Karp para grafos bipartidos. A técnica de Micali–Vazirani é complexa, e seus autores não forneceram provas completas de seus resultados; posteriormente, a "explicação clara" foi publicado por Peterson & Loui (1988) e métodos alternativos foram descritos por outros autores.^[3] Em 2012, Vazirani ofereceu uma nova prova simplificada do algoritmo de Micali-Vazirani.^[4]

Pseudocódigo

/* 
 G = U ∪ V ∪ {NIL}
 onde U e V são partições do grafo e NIL é um vértice especial nulo
*/
  
função BFS ()
    para u em U
        se Pair_U[u] == NIL
            Dist[u] = 0
            Enqueue(Q,u)
        senão
            Dist[u] = ∞
    Dist[NIL] = ∞
    enquanto Empty(Q) == falso
        u = Dequeue(Q)
        se Dist[u] < Dist[NIL] 
            para cada v em Adj[u]
                se Dist[ Pair_V[v] ] == ∞
                    Dist[ Pair_V[v] ] = Dist[u] + 1
                    Enqueue(Q,Pair_V[v])
    retorne Dist[NIL] != ∞

função DFS (u)
    se u != NIL
        para cada v em Adj[u]
            se Dist[ Pair_V[v] ] == Dist[u] + 1
                se DFS(Pair_V[v]) == verdadeiro
                    Pair_V[v] = u
                    Pair_U[u] = v
                    retorne verdadeiro
        Dist[u] = ∞
        retorne falso
    retorne verdadeiro

função Hopcroft-Karp
    para cada u em U
        Pair_U[u] = NIL
    para cada v em V
        Pair_V[v] = NIL
    matching = 0
    enquanto BFS() == verdadeiro
        para cada u em U
            se Pair_U[u] == NIL
                se DFS(u) == verdadeiro
                    matching = matching + 1
    retorne matching

Execução em um exemplo gráfico que mostra o grafo de entrada e a correspondência após a iteração intermediária 1 e a iteração final 2.

Explicação

Considere que o nosso grafo tenha duas partições ${\displaystyle U,V}$. A ideia chave é adicionar dois vértices postiços em cada lado no grafo: ${\displaystyle uDummy}$ se conecta a todos os vértices não marcados em ${\displaystyle U}$ e ${\displaystyle vDummy}$ se conecta a todos os vértices não marcados em ${\displaystyle V}$. Agora se executarmos uma busca em largura a partir de ${\displaystyle uDummy}$ para ${\displaystyle vDummy}$ então podemos obter o caminho mais curto entre um vértice não acoplado em ${\displaystyle U}$ para um vértice não acoplado em ${\displaystyle V}$. Devido à natureza do grafo bipartido, este caminho seria um zig zag de ${\displaystyle U}$ para ${\displaystyle V}$. No entanto, precisamos ter certeza de que quando se passa de ${\displaystyle V}$ para ${\displaystyle U}$, nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em  ${\displaystyle vDummy}$. Se nós temos certeza destes critérios durante uma busca em largura então o caminho gerado irá reunir os requisitos para ser um caminho extensor mais curto.

Uma vez que tenhamos encontrado o caminho extensor mais curto, queremos ter certeza de que ignorar quaisquer outros caminhos que são maiores do que caminhos mais curtos. O algoritmo de busca em largura marca os nós em um caminho com a distância da fonte como sendo 0. Assim, depois de realizar uma busca em largura, podemos começar a partir de cada vértice não acoplado em ${\displaystyle U}$, seguir o caminho percorrendo os nós incrementando a distância por 1. Quando finalmente chegarmos ao destino ${\displaystyle vDummy}$, se a sua distância é maior em 1 do que o último nó em ${\displaystyle V}$ então sabemos que o caminho que percorremos (uma dentre várias possibilidades)  é o caminho mais curto. Nesse caso, podemos ir em frente e atualizar os pares de vértices nos caminhos de ${\displaystyle U}$ e ${\displaystyle V}$. Note que cada vértice em ${\displaystyle V}$ sobre um caminho, exceto pelo último, não é um vértice livre. Então, atualizando os pares destes vértices em ${\displaystyle V}$ para diferentes vértices em ${\displaystyle U}$ é equivalente a remover previamente uma aresta correspondente e adicionar uma nova aresta não acoplada em uma acoplada. Isto é o mesmo que fazer a diferença simétrica (i.e. remover arestas em comum a acoplamentos anteriores e adicionar arestas que não estão em comum no caminho extensor em novo acoplamento).

Como podemos ter certeza de que caminhos extensores são vértices disjuntos? Isto já é garantido: Depois de fazer a diferença simétrica para um caminho, nenhum dos seus vértices poderia ser considerado novamente apenas porque o Dist[ Pair_V[v] ] não vai ser igual a Dist[u] + 1 (seria exatamente Dist[u]).

Então, qual é a missão destas duas linhas em pseudocódigo?:

Dist[u] = ∞ retorne falso

Quando não formos capazes de encontrar qualquer caminho extensor menor a partir de um vértice, a busca em profundidade retorna falso. Neste caso, seria bom para marcar esses vértices para não visitá-los novamente. Essa marcação é simplesmente feita configurando Dist[u] como sendo igual a infinito.

Finalmente, nós realmente não precisamos de ${\displaystyle uDummy}$ pois ele está lá apenas para colocar todos os vértices não acoplados de ${\displaystyle U}$ em uma fila quando a busca em largura começa. Que podemos fazer apenas como uma inicialização. O ${\displaystyle vDummy}$ pode ser anexado em ${\displaystyle U}$ por conveniência em muitas implementações e inicializar o acoplamento padrão para todo ${\displaystyle V}$ apontar para ${\displaystyle vDummy}$. Dessa forma, se o vértice final em ${\displaystyle V}$ não tem qualquer vértice correspondente em ${\displaystyle U}$, em seguida, finalmente terminamos em ${\displaystyle vDummy}$ que é o final do nosso caminho extensor. No pseudocódigo acima ${\displaystyle vDummy}$ é denotado como sendo Nil.

Veja também

• Acoplamento (teoria dos grafos)
• Hungarian algorithm
• Assignment problem

Notas

1. Ahuja, Magnanti & Orlin (1993), section 12.3, bipartite cardinality matching problem, pp. 469–470.
2. Chang & McCormick (1990); Darby-Dowman (1980); Setubal (1993); Setubal (1996).
3. Gabow & Tarjan (1991) and Blum (2001).
4. Vazirani (2012)

Referências

• 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 .
• 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, MR 0177907, 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, 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 .