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 $O(|E|{\sqrt {|V|}})$ no pior caso, onde $E$ é o conjunto de arestas do grafo, e $V$ é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se $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 $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 editar

Um vértice que não é uma extremidade de uma aresta em algum acoplamento parcial $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 $M$ é um acoplamento, e $P$ é um caminho extensor relativo a $M$ , então a diferença simétrica dos dois conjuntos de arestas, $M\oplus P$ , formaria um acoplamento de tamanho $|M|+1$ . Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.

Por outro lado, suponha que um acoplamento $M$ não é ótimo, e seja $P$ a diferença simétrica $M\oplus M^{*}$ onde $M^{*}$ é um acoplamento ótimo. Pelo fato de $M$ e $M^{*}$ serem ambos acoplamentos, cada vértice tem grau no máximo 2 em $P$ . Então $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 $M$ e $M^{*}$ é o número de caminhos extensores em $P$ . Assim, se nenhum caminho extensor for encontrado, um algoritmo pode terminar com segurança, já que neste caso $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

G(U\cup V,E)

Saída: Acoplamento

M\subseteq E

M\leftarrow \emptyset

repita

{\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}

conjunto máximo de vértices disjuntos de caminhos extensores mais curtos

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

até

{\mathcal {P}}=\emptyset

Algoritmo editar

Sejam $U$ e $V$ dois conjuntos da bipartição de $G$ , e considere o acoplamento de $U$ para $V$ a qualquer tempo sendo representado como um conjunto $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 $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 $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 $U$ , somente arestas não acopladas podem ser cruzadas, enquanto a partir de um vértice em $V$ somente arestas acopladas podem ser cruzadas. A busca termina na primeira camada $k$ onde um ou mais vértices livres em $V$ são alcançados.
Todos os vértices livres em $V$ na camada $k$ são reunidas em um conjunto $F$ . Ou seja, um vértice $v$ é colocado em $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 $k$ . Este conjunto pode ser computado por uma busca em profundidade de $F$ para os vértices livres em $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 $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 $M$ .

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

Análise editar

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 ${\sqrt {|V|}}$ fases, em um grafo com $|V|$ vértices e $|E|$ arestas, levam um tempo $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 ${\sqrt {|V|}}$ fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo ${\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 ${\sqrt {|V|}}$ , pode haver no máximo ${\sqrt {|V|}}$ caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de $M$ por no máximo ${\sqrt {|V|}}$ arestas. Uma vez que cada fase do algoritmo aumenta o tamanho do acoplamento por pelo menos um, pode haver no máximo ${\sqrt {|V|}}$ fases adicionais antes do algoritmo terminar.

Uma vez que o algoritmo executa um total de, no máximo $2{\sqrt {|V|}}$ fases, é preciso um tempo total de $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 $O(\log |V|)$ fases e um tempo total de $O(|E|\log |V|)$ .

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

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 , $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 editar

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 $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 editar

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

Considere que o nosso grafo tenha duas partições $U,V$ . A ideia chave é adicionar dois vértices postiços em cada lado no grafo: $uDummy$ se conecta a todos os vértices não marcados em $U$ e $vDummy$ se conecta a todos os vértices não marcados em $V$ . Agora se executarmos uma busca em largura a partir de $uDummy$ para $vDummy$ então podemos obter o caminho mais curto entre um vértice não acoplado em $U$ para um vértice não acoplado em $V$ . Devido à natureza do grafo bipartido, este caminho seria um zig zag de $U$ para $V$ . No entanto, precisamos ter certeza de que quando se passa de $V$ para $U$ , nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em $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 $U$ , seguir o caminho percorrendo os nós incrementando a distância por 1. Quando finalmente chegarmos ao destino $vDummy$ , se a sua distância é maior em 1 do que o último nó em $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 $U$ e $V$ . Note que cada vértice em $V$ sobre um caminho, exceto pelo último, não é um vértice livre. Então, atualizando os pares destes vértices em $V$ para diferentes vértices em $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 $uDummy$ pois ele está lá apenas para colocar todos os vértices não acoplados de $U$ em uma fila quando a busca em largura começa. Que podemos fazer apenas como uma inicialização. O $vDummy$ pode ser anexado em $U$ por conveniência em muitas implementações e inicializar o acoplamento padrão para todo $V$ apontar para $vDummy$ . Dessa forma, se o vértice final em $V$ não tem qualquer vértice correspondente em $U$ , em seguida, finalmente terminamos em $vDummy$ que é o final do nosso caminho extensor. No pseudocódigo acima $vDummy$ é denotado como sendo Nil.

Veja também editar

Acoplamento (teoria dos grafos)
Hungarian algorithm
Assignment problem

Notas editar

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

Referências editar

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, 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 $\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 .

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

[1]

[2]

[3]

[4]