Connected Matchings

• Bruno P. Masquio UERJ
• Paulo E. D. Pinto UERJ
• Jayme L. Szwarcfiter UERJ, UFRJ

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

Abstract

Graph matching problems are well known and studied, in which we want to find sets of pairwise non-adjacent edges. Recently, there has been an interest in the study of matchings in which the induced subgraphs by the vertices of matchings are connected or disconnected. Although these problems are related to connectivity, the two problems are probably quite different, regarding their complexity. While the complexity of finding a maximum disconnected mat- ching is still unknown for a general graph, the one for connected matchings can be solved in polynomial time. Our contribution in this paper is a linear time algorithm to find a maximum connected matching of a general connected graph, given a general maximum matching as input.

Keywords: Matching, Connected, Algorithms

References

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

Masquio, B. P. (2019). Emparelhamentos desconexos. Master’s thesis, Universidade do Estado do Rio de Janeiro. Disponível em https://github.com/BMasquio/papers/raw/master/MastersThesisBrunoMasquio.pdf.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2019). Algoritmos Eficientes Para Emparelhamentos Desconexos em Grafos Cordais e Grafos Bloco. In Anais do Encontro de Teoria da Computação (ETC/CSBC), Natal - RN. SBC.

Micali, S. and Vazirani, V. V. (1980). An O(Sqrt(|V | |E|)) algorithm for finding maximum matching in general graphs. In 21st Ann. Symp. on Foundations of Comp. Sc., pages 17–27.