Efficient algorithms for disconnected matchings on chordal graphs and block graphs

• Bruno Masquio UERJ
• Paulo Pinto UERJ
• Jayme Szwarcfiter UFRJ

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

Abstract

Graph matching problems are well studied and bring great contributions to Graph Theory from both the theoretical and practical points of view. There are numerous studies for unrestricted and weighted/unweighted matchings. More recently, subgraph-restricted matchings have been proposed, which consider properties of the subgraph induced by the vertices of the matching. In this paper, we approach one of these new proposals, disconnected matching, which seeks to study maximum matching, such that the subgraph induced by the matching vertices is disconnected. We have described efficient algorithms to solve the problem for chordal graphs and block graphs based on a theoretical characterization.

Keywords: Chordal graphs, block graphs, algorithms, computational complexity

References

Chandran, L. S. (2001). A linear time algorithm for enumerating all the minimum and minimal separators of a chordal graph. In Wang, J., editor, Computing and Combinatorics, p. 308–317, Berlin, Heidelberg. Springer Berlin Heidelberg.

Fulkerson, D. R. and Gross, O. A. (1965). Incidence matrices and interval graphs. Pacific J. Math., 15(3):835–855.
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.

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 ofComp. Sc., p. 17–27.