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

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.

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.
Publicado
2021-07-18
Como Citar
GOMES, Guilherme de C. M. et al. Emparelhamento Desconexo é NP-Completo. Anais do Encontro de Teoria da Computação (ETC), [S.l.], p. 26-29, jul. 2021. ISSN 2595-6116. Disponível em: <https://sol.sbc.org.br/index.php/etc/article/view/16372>. Acesso em: 18 maio 2024. doi: https://doi.org/10.5753/etc.2021.16372.