Emparelhamento Conexo Ponderado é 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); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.222633, 2022)
Um emparelhamento M também é chamado de P-emparelhamento se o subgrafo induzido pelos vértices incidentes por arestas de M satisfaz à propriedade P. Encontrar emparelhamentos de cardinalidade máxima para muitas propriedades P, tais como o subgrafo induzido ser 1-regular, desconexo ou acíclico, é NP-difícil. Por outro lado, um emparelhamento conexo de cardinalidade máxima, em que a propriedade é que o grafo seja conexo, pode ser obtido em tempo polinomial. Nesse artigo, consideramos o problema Emparelhamento Conexo Ponderado, onde, dado um grafo ponderado em arestas e um inteiro k, deseja-se obter um emparelhamento conexo cuja soma dos pesos das arestas seja pelo menos k. Provamos que esse problema é NP-completo mesmo para grafos bipartidos de diâmetro 4.