Emparelhamentos em grafos possuem diversas aplicações na teoria e na prática. Encontramos exemplos em química e biologia, na estrutura de moléculas e de reações bioquímicas. Também pode ser usado em problemas de alocação de trabalhadores a tarefas, de alunos a classes, pacotes de dados a switches. Do ponto de vista teórico, tem relações com outras áreas, como coloração de arestas em grafos.

O estudo de emparelhamentos teve sua origem no interesse de encontrar e caracterizar emparelhamentos perfeitos ou de cardinalidade máxima. Contudo, ao decorrer do tempo, variantes foram propostas, como a de emparelhamentos ponderados, emparelhamentos maximais mínimos, emparelhamentos estáveis, p-emparelhamentos, contagem de emparelhamentos, dentre outros.

Nesta apresentação, vamos mostrar diversos resultados obtidos ao longo da história no estudo de emparelhamentos, com o estado da arte. Além disso, abordamos com mais detalhes uma prova de NP-completude para o problema Emparelhamento Desconexo, e o algoritmo Hopcroft–Karp, o qual é atualmente o mais eficiente para emparelhamentos máximos em grafos bipartidos.

Bruno Porto Masquio é bacharel em Ciência da Computação(2016) e mestre em Ciências Computacionais(2018) na UERJ. Atualmente trabalha como desenvolvedor e coordenador, com 5 anos de experiência, e cursa doutorado em Ciências Computacionais na UERJ desde 2019. Como pesquisador, estuda complexidade de algoritmos e teoria de grafos. Suas produções geraram diversos artigos aceitos, e eventualmente premiados, em conferências nacionais e internacionais, com destaque para COCOON 2021 e LATIN 2022. Alguns desses trabalhos estão no processo de publicação em periódicos. Também trabalhou como revisor do renomado periódico Theoretical Computer Science.