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 no pior caso, onde é o conjunto de arestas do grafo, e é o conjunto de vértices do grafo. No caso de grafos densos o tempo limite torna-se e para grafos aleatórios ele é executado em tempo quase linear.
O algoritmo foi encontrado por . Como nos métodos anteriores para acoplamento, tais como o algoritmo húngaro e o trabalho de , 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 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 é 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 é um acoplamento, e é um caminho extensor relativo a , então a diferença simétrica dos dois conjuntos de arestas, , formaria um acoplamento de tamanho . Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.
Por outro lado, suponha que um acoplamento não é ótimo, e seja a diferença simétrica onde é um acoplamento ótimo. Pelo fato de e serem ambos acoplamentos, cada vértice tem grau no máximo 2 em . Então 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 e é o número de caminhos extensores em . Assim, se nenhum caminho extensor for encontrado, um algoritmo pode terminar com segurança, já que neste caso 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., section 12.3, bipartite cardinality matching problem, pp. 469–470. 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 Saída: Acoplamento
repita conjunto máximo de vértices disjuntos de caminhos extensores mais curtos
até
Algoritmo Sejam e dois conjuntos da bipartição de , e considere o acoplamento de para a qualquer tempo sendo representado como um conjunto .
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 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 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 , somente arestas não acopladas podem ser cruzadas, enquanto a partir de um vértice em somente arestas acopladas podem ser cruzadas. A busca termina na primeira camada onde um ou mais vértices livres em são alcançados. Todos os vértices livres em na camada são reunidas em um conjunto . Ou seja, um vértice é colocado em 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 . Este conjunto pode ser computado por uma busca em profundidade de para os vértices livres em , 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 , 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 . 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 fases, em um grafo com vértices e arestas, levam um tempo .
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 fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo 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 , pode haver no máximo caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de por no máximo arestas. Uma vez que cada fase do algoritmo aumenta o tamanho do acoplamento por pelo menos um, pode haver no máximo fases adicionais antes do algoritmo terminar.
Uma vez que o algoritmo executa um total de, no máximo fases, é preciso um tempo total de 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 , (melhorando o resultado anterior de ) 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 fases e um tempo total de .
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 alcança um limitante de tempo um pouco melhor , . 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.; ; ; .
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 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, 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 e métodos alternativos foram descritos por outros autores. and . Em 2012, Vazirani ofereceu uma nova prova simplificada do algoritmo de Micali-Vazirani.
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 miniaturadaimagem|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 . A ideia chave é adicionar dois vértices postiços em cada lado no grafo: se conecta a todos os vértices não marcados em e se conecta a todos os vértices não marcados em . Agora se executarmos uma busca em largura a partir de para então podemos obter o caminho mais curto entre um vértice não acoplado em para um vértice não acoplado em . Devido à natureza do grafo bipartido, este caminho seria um zig zag de para . No entanto, precisamos ter certeza de que quando se passa de para , nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em . 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 , seguir o caminho percorrendo os nós incrementando a distância por 1. Quando finalmente chegarmos ao destino , se a sua distância é maior em 1 do que o último nó em 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 e . Note que cada vértice em sobre um caminho, exceto pelo último, não é um vértice livre. Então, atualizando os pares destes vértices em para diferentes vértices em é 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).