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 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.
Um vértice que não é uma extremidade de uma aresta em algum acoplamento parcial M {\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 M {\displaystyle M} é um acoplamento, e P {\displaystyle P} é um caminho extensor relativo a M {\displaystyle M} , então a diferença simétrica dos dois conjuntos de arestas, M ⊕ P {\displaystyle M\oplus P} , formaria um acoplamento de tamanho | M | + 1 {\displaystyle |M|+1} . Assim, encontrando caminhos extensores, um algoritmo pode aumentar o tamanho do acoplamento.
Sejam U {\displaystyle U} e V {\displaystyle V} dois conjuntos da bipartição de G {\displaystyle G} , e considere o acoplamento de U {\displaystyle U} para V {\displaystyle V} a qualquer tempo sendo representado como um conjunto M {\displaystyle M} . O algoritmo é executado em fases. Cada fase consiste nos seguintes passos. O algoritmo termina quando não há mais caminhos extensores a serem encontrados em uma das fases da busca em largura.
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 | V | {\displaystyle {\sqrt {|V|}}} fases, em um grafo com | V | {\displaystyle |V|} vértices e | E | {\displaystyle |E|} arestas, levam um tempo O ( | E | | V | ) {\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 | V | {\displaystyle {\sqrt {|V|}}} fases iniciais do algoritmo estejam completas, o caminho extensor mais curto restante tem no mínimo | V | {\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 | V | {\displaystyle {\sqrt {|V|}}} , pode haver no máximo | V | {\displaystyle {\sqrt {|V|}}} caminhos no conjunto, e o tamanho do acoplamento ótimo pode diferir do tamanho de M {\displaystyle M} por no máximo | V | {\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 | V | {\displaystyle {\sqrt {|V|}}} fases adicionais antes do algoritmo terminar.
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 ( n 1.5 m log n ) {\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.
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 ( | V | ) {\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. Em 2012, Vazirani ofereceu uma nova prova simplificada do algoritmo de Micali-Vazirani.
Explicação
Considere que o nosso grafo tenha duas partições U , V {\displaystyle U,V} . A ideia chave é adicionar dois vértices postiços em cada lado no grafo: u D u m m y {\displaystyle uDummy} se conecta a todos os vértices não marcados em U {\displaystyle U} e v D u m m y {\displaystyle vDummy} se conecta a todos os vértices não marcados em V {\displaystyle V} . Agora se executarmos uma busca em largura a partir de u D u m m y {\displaystyle uDummy} para v D u m m y {\displaystyle vDummy} então podemos obter o caminho mais curto entre um vértice não acoplado em U {\displaystyle U} para um vértice não acoplado em V {\displaystyle V} . Devido à natureza do grafo bipartido, este caminho seria um zig zag de U {\displaystyle U} para V {\displaystyle V} . No entanto, precisamos ter certeza de que quando se passa de V {\displaystyle V} para U {\displaystyle U} , nós sempre selecionamos uma aresta correspondida. Se não houver nenhuma aresta acoplada então finalizamos em v D u m m y {\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.
