MAC0499: Algoritmo algébrico para emparelhamentos máximos.

Aluno: Antonio Marcos Shiro Arnauts Hachisuca

Orientador: Marcel K. de Carli Silva

Em 2009, Nicholas J. A. Harvey propôs um algoritmo probabilístico para resolver o problema do emparelhamento máximo em grafos em tempo O(\(n^\omega\)), onde \(n\) é o número de vértices e \(\omega\) é o menor expoente para o qual existe um algoritmo em tempo O(\(n^\omega\)) para a multiplicação de matrizes. Atualmente, é conhecido que \(\omega < 2.38\). O algoritmo se fundamenta em conceitos da teoria algébrica de grafos para resolver o problema. Sua implementação utiliza atualizações "lazy" e um algoritmo de multiplicação de matrizes em caixa preta. Sua importância é destacada pela resolução de uma pergunta em aberto proposta por Mucha e Sankowski, além de refutar a conjectura da inexistência de algoritmos que empregam estratégias "lazy" para resolver esse problema.

Este trabalho tem como objetivo o estudo e a implementação do algoritmo proposto por Harvey. Vale ressaltar que não será realizada a implementação da multiplicação de matrizes em complexidade sub-cúbica, uma vez que isso foge do escopo deste trabalho.

Planeja-se realizar as seguintes etapas:

1. Introdução à teoria algébrica de grafos e aos conceitos de álgebra linear relevantes ao tema.
2. Estudo e implementação da versão \( O(n^{\omega+2}) \) do algoritmo: algoritmo probabilístico que utiliza a propriedade de que uma matriz de Tutte é não-singular se e somente se o grafo possui um emparelhamento perfeito.
3. Estudo e implementação da versão \( O(n^{\omega+1}) \) do algoritmo: algoritmo probabilístico proposto por Rabin e Vazirani [2] que otimiza a versão anterior.
4. Estudo e implementação da versão \( O(n^{\omega}) \) do algoritmo: algoritmo probabilístico proposto pelo artigo [1] que utiliza a abordagem de divisão e conquista e atualizações "lazy".

Monografia

Repositório

Referências: