Emparelhamento Desconexo é NP-Completo - Gomes, Guilherme de C. M.; Masquio, Bruno P.; Pinto, Paulo E. D.; Santos, Vinicius F.; Szwarcfiter, Jayme L. (Anais do Encontro de Teoria da Computação (ETC), 2021)
Um subconjunto M ⊆ E de arestas de um grafo G = (V, E) é um emparelhamento se nenhum par de arestas de M compartilha um vértice comum. Recentemente, P-emparelhamentos foram propostos, os quais requerem algumas propriedades dos subgrafos induzidos pelos vértices M-saturados de G. Tratamos um deles, o problema do emparelhamento desconexo, cuja propriedade é que o referido subgrafo induzido seja desconexo. Embora alguns algoritmos eficientes já tenham sido mostrados para algumas classes, a complexidade do problema geral permanecia em aberto. Apresentamos uma prova de que o emparelhamento desconexo é NP-completo, mesmo para grafos bipartidos e grafos com diâmetro limitado.