Correspondência de cardinalidade máxima - Maximum cardinality matching

A correspondência de cardinalidade máxima é um problema fundamental na teoria dos grafos . Recebemos um gráfico e o objetivo é encontrar uma correspondência contendo tantas arestas quanto possível, ou seja, um subconjunto de cardinalidade máxima das arestas de modo que cada vértice seja adjacente a no máximo uma aresta do subconjunto. Como cada aresta cobrirá exatamente dois vértices, este problema é equivalente à tarefa de encontrar uma correspondência que cubra o maior número possível de vértices. ${\ displaystyle G}$

Um caso especial importante do problema de correspondência de cardinalidade máxima é quando G é um grafo bipartido , cujos vértices V são particionados entre vértices esquerdos em X e vértices direitos em Y , e arestas em E sempre conectam um vértice esquerdo a um vértice direito. Nesse caso, o problema pode ser resolvido de forma eficiente com algoritmos mais simples do que no caso geral.

Algoritmos para grafos bipartidos

A maneira mais simples de calcular uma correspondência de cardinalidade máxima é seguir o algoritmo Ford-Fulkerson . Este algoritmo resolve o problema mais geral de calcular o fluxo máximo , mas pode ser facilmente adaptado: nós simplesmente transformamos o gráfico em uma rede de fluxo adicionando um vértice de origem ao gráfico com uma aresta para todos os vértices esquerdos em X , adicionando um vértice coletor tendo uma aresta de todos os vértices direitos em Y , mantendo todas as arestas entre X e Y , e dando uma capacidade de 1 para cada aresta. O algoritmo Ford-Fulkerson irá então prosseguir encontrando repetidamente um caminho crescente de algum x ∈ X para algum y ∈ Y e atualizando o M correspondente tomando a diferença simétrica desse caminho com M (assumindo que tal caminho exista). À medida que cada caminho pode ser encontrado em tempo, o tempo de execução é , e o emparelhamento máximo consiste nas arestas de E que transportam o fluxo de X para Y . ${\ displaystyle \ O (E)}$${\ displaystyle \ O (VE)}$

Uma melhoria neste algoritmo é dada pelo algoritmo Hopcroft-Karp mais elaborado , que procura vários caminhos aumentantes simultaneamente. Este algoritmo é executado no tempo. ${\ displaystyle O ({\ sqrt {V}} E)}$

O algoritmo de Chandran e Hochbaum para grafos bipartidos é executado no tempo que depende do tamanho do emparelhamento máximo , que para é . Usando operações booleanas em palavras de tamanho, a complexidade é aprimorada ainda mais . ${\ displaystyle k}$${\ displaystyle | X | <| Y |}$${\ displaystyle O \ left (\ min \ {| X | k, E \} + {\ sqrt {k}} \ min \ {k ^ {2}, E \} \ right)}$${\ displaystyle \ lambda}$${\ displaystyle O \ left (\ min \ left \ {| X | k, {\ frac {| X || Y |} {\ lambda}}, E \ right \} + k ^ {2} + {\ frac {k ^ {2.5}} {\ lambda}} \ right)}$

Existem algoritmos mais eficientes para tipos especiais de grafos bipartidos:

• Para grafos bipartidos esparsos , o problema de correspondência máxima pode ser resolvido com o algoritmo de Madry baseado em fluxos elétricos.${\ displaystyle {\ tilde {O}} (E ^ {10/7})}$
• Para planares grafos bipartidos, o problema pode ser resolvido no tempo , onde N é o número de vértices, através da redução do problema de fluxo máximo com múltiplas fontes e destinos.${\ displaystyle O (n \ log ^ {3} n)}$

Algoritmos para gráficos arbitrários

O algoritmo de flor encontra uma correspondência de cardinalidade máxima em gráficos gerais (não necessariamente bipartidos). Corre no tempo . Um melhor desempenho de O ( √ V E ) para gráficos gerais, correspondendo ao desempenho do algoritmo Hopcroft-Karp em gráficos bipartidos, pode ser alcançado com o algoritmo muito mais complicado de Micali e Vazirani. O mesmo limite foi alcançado por um algoritmo de Blum ( de ) e um algoritmo de Gabow e Tarjan . ${\ displaystyle O (| V | ^ {2} \ cdot | E |)}$

Uma abordagem alternativa usa a randomização e é baseada no algoritmo de multiplicação de matrizes rápidas . Isso fornece um algoritmo aleatório para gráficos gerais com complexidade . Em teoria, isso é melhor para gráficos suficientemente densos , mas na prática o algoritmo é mais lento. ${\ displaystyle O (V ^ {2.376})}$

Outros algoritmos para a tarefa são revisados ​​por Duan e Pettie (consulte a Tabela I). Em termos de algoritmos de aproximação , eles também apontam que o algoritmo de flor e os algoritmos de Micali e Vazirani podem ser vistos como algoritmos de aproximação rodando em tempo linear para qualquer limite de erro fixo.

Aplicações e generalizações

• Ao encontrar uma correspondência de cardinalidade máxima, é possível decidir se existe uma correspondência perfeita .
• O problema de encontrar uma correspondência com peso máximo em um grafo ponderado é chamado de problema de correspondência de peso máximo , e sua restrição a grafos bipartidos é chamado de problema de atribuição . Se cada vértice pode ser correspondido a vários vértices de uma vez, então este é um problema de atribuição generalizado .
• Uma correspondência de prioridade é uma correspondência de cardinalidade máxima específica em que os vértices priorizados são correspondidos primeiro.
• O problema de encontrar uma correspondência de cardinalidade máxima em um hipergrafo é NP-completo mesmo para hipergrafos de 3 uniformes.

Referências