Emparelhamento Desconexo é NP-Completo

• Guilherme de C. M. Gomes UFMG
• Bruno P. Masquio UERJ
• Paulo E. D. Pinto UERJ
• Vinicius F. Santos UFMG
• Jayme L. Szwarcfiter UERJ / UFRJ

DOI: https://doi.org/10.5753/etc.2021.16372

Resumo

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.

Palavras-chave: Emparelhamento, Restrito, Desconexo, NP-completo

Referências

Baste, J. and Rautenbach, D. (2018). Degenerate matchings and edge colorings.DiscreteApplied Mathematics, 239:38–44.

Cameron, K. (1989). Induced matchings.Discrete Applied Mathematics, 24(1):97–102.

Garey, M. R. and Johnson, D. S. (1979).Computers and Intractability: A Guide to theTheory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA.

Goddard, W., Hedetniemi, S. M., Hedetniemi, S. T., and Laskar, R. (2005). Generalizedsubgraph-restricted matchings in graphs.Discrete Mathematics, 293(1):129–138.

Golumbic, M. C., Hirst, T., and Lewenstein, M. (2001). Uniquely restricted matchings.Algorithmica, 31(2):139–154.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2019). Algoritmos eficientes paraemparelhamentos desconexos em grafos cordais e grafos bloco. InAnais do IV En-contro de Teoria da Computação, Porto Alegre, RS, Brasil. SBC.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2020). Emparelhamentos conexos.InAnais do V Encontro de Teoria da Computação, Cuiabá, MT, Brasil. SBC.