Maximum Weight Connected Matching is NP-complete
Abstract
A matching M is a P-matching if the subgraph induced by the endpoints of the edges of M satisfies property P. Finding maximum cardinality P-matchings is NP-hard for many properties P, as 1-regular, disconnected and acyclic. On the other hand, determining a maximum cardinality connected matching, where P is connected, can be obtained in polynomial time. In this article, we consider the problem Weighted Connected Matching, where, given an edge-weighted graph and an integer k, we want to find a connected matching whose sum of edge weights is at least k. We prove that this problem is NP-complete even for diameter 4 bipartite graphs.
Keywords:
Computational complexity, Algorithms, Matchings
References
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.
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.
Published
2022-07-31
How to Cite
GOMES, Guilherme de C. M.; MASQUIO, Bruno P.; PINTO, Paulo E. D.; SANTOS, Vinicius F.; SZWARCFITER, Jayme L..
Maximum Weight Connected Matching is NP-complete. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 33-36.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222633.
