Disconnected Matching is NP-complete

• 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

Abstract

A subsetset M ⊆ E of edges of a graph G = (V,E) is a matching if no two edges of M share a common vertex. Recently, subgraph-restricted matchings have been proposed, which require some properties from the subgraph induced by M-saturated vertices of G. We treat the disconnected matching problem, whose property is that the referred induced subgraph is disconnected. Although some efficient algorithms have already been shown for some classes, the complexity of the general problem remained opened. We present a proof that the disconnected matching is NP-complete, even for bipartite graphs with limited diameter.

Keywords: Matching, Restricted, Disconnected, NP-complete

References

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.