Emparelhamento Conexo Ponderado é 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.2022.222633

Resumo

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.

Palavras-chave: Complexidade computacional, Algoritmos, Emparelhamentos

Referências

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

Fürst, M. and Rautenbach, D. (2019). On some hard and some tractable cases of the maximum acyclic matching problem. Annals of Operations Research, 279(1):291–300.

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

Goddard, W., Hedetniemi, S. M., Hedetniemi, S. T., and Laskar, R. (2005). Generalized subgraph-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.

Gomes, G. C. M., Masquio, B. P., Pinto, P. E. D., dos Santos, V. F., and Szwarcfiter, J. L. (2021). Disconnected matchings. In Chen, C.-Y., Hon, W.-K., Hung, L.-J., and Lee, C.-W., editors, Computing and Combinatorics, pages 579–590, Cham. Springer International Publishing.

Gomes, G. C. M., Masquio, B. P., Pinto, P. E. D., dos Santos, V. F., and Szwarcfiter, J. L. (2022). Weighted connected matchings. https://doi.org/10.48550/arxiv.2202.04746.

Klemz, B. and Rote, G. (2022). Linear-time algorithms for maximum-weight induced matchings and minimum chain covers in convex bipartite graphs. Algorithmica.

Panda, B. S., Pandey, A., Chaudhary, J., Dane, P., and Kashyap, M. (2020). Maximum weight induced matching in some subclasses of bipartite graphs. Journal of Combinatorial Optimization, 40(3):713–732.