Connected and Disconnected Matchings

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

DOI: https://doi.org/10.5753/ctd.2023.229529

Resumo

Matching problems in graphs have been studied for a long time, achieving important results in both theoretical and practical aspects. Over the decades, many variations of matching problems and results were studied. Some of them can be solved in polynomial time, while others apparently cannot, unless P = NP. In this thesis, we briefly present the history of matching problems and their complexities, along with a survey of some of their variations, and their state-of-the-art. We also give new results on one of these variations: P-matchings. A matching M is a P-matching if the subgraph induced by the endpoints of the edges of M satisfies property P . As examples, for appropriate choices of P , the problems INDUCED MATCHING, UNIQUELY RESTRICTED MATCHING, ACYCLIC MATCHING, CONNECTED MATCHING and DISCONNECTED MATCHING arise. In this thesis, we focus our study on three: DISCONNECTED MATCHING, CONNECTED MATCHING and its weighted version, WEIGHTED CONNECTED MATCHING. To this end, we developed NPcompleteness proofs, classical and parameterized complexity analysis, as well as exact polynomial algorithms, considering these problems in general and subject to some constraints.

Referências

Duan, R., Pettie, S., and Su, H.-H. (2018). Scaling algorithms for weighted matching in general graphs. ACM Trans. Algorithms, 14(1).

Edmonds, J. (1965). Maximum matching and a polyhedron with 0, 1-vertices. Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 69B(1 and 2):125.

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., Masquio, B., Pinto, P., Santos, V., and Szwarcfiter, J. (2021a). Emparelhamento desconexo é np-completo. In Anais do VI Encontro de Teoria da Computação, pages 26–29, Porto Alegre, RS, Brasil. SBC.

Gomes, G., Masquio, B., Pinto, P., Santos, V., and Szwarcfiter, J. (2022a). Emparelhamento conexo ponderado é np-completo. In Anais do VII Encontro de Teoria da Computação, pages 33–36, Porto Alegre, RS, Brasil. SBC.

Gomes, G., Masquio, B., Pinto, P., Santos, V., and Szwarcfiter, J. (2022b). Weighted connected matchings. In Annals of the LAWCG 22 Workshop on Cliques in Graphs, Curitiba, PR, Brazil.

Gomes, G., Masquio, B., Pinto, P., Santos, V., and Szwarcfiter, J. (2022c). Weighted connected matchings. In Abstract book of XXI Latin Ibero-American Conference on Operations Research, Buenos Aires, Argentina.

Gomes, G. C., Masquio, B. P., Pinto, P. E., dos Santos, V. F., and Szwarcfiter, J. L. (2023). Disconnected matchings. Theoretical Computer Science, page 113821.

Gomes, G. C. M., Masquio, B. P., Pinto, P. E. D., dos Santos, V. F., and Szwarcfiter, J. L. (2021b). 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., Santos, V. F. d., and Szwarcfiter, J. L. (2022d). Weighted connected matchings.

Gomes, G. C. M., Masquio, B. P., Pinto, P. E. D., Santos, V. F. d., and Szwarcfiter, J. L. (2022e). Weighted connected matchings. In Castañeda, A. and Rodríguez-Henríquez, F., editors, LATIN 2022: Theoretical Informatics, pages 54–70, Cham. Springer International Publishing.

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

Masquio, B., Pinto, P., and Szwarcfiter, J. (2020a). Emparelhamentos conexos. In Anais do V Encontro de Teoria da Computação, pages 1–4, Porto Alegre, RS, Brasil. SBC.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2020b). Algoritmos lineares para emparelhamentos conexos. In Anais Do LII Simpósio Brasileiro de Pesquisa Operacional, João Pessoa, PB, Brazil.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2020c). Connected matchings. Poster presented at 9th Latin American Workshop on Cliques in Graphs.

Masquio, B. P., Pinto, P. E. D., and Szwarcfiter, J. L. (2021). Algoritmos lineares para emparelhamentos conexos máximos ponderados e não ponderados. In Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. SBMAC.

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.

Shen, H. and Liang, W. (1997). Efficient enumeration of all minimal separators in a graph. Theoretical Computer Science, 180(1):169 – 180.

Stockmeyer, L. J. and Vazirani, V. V. (1982). Np-completeness of some generalizations of the maximum matching problem. Information Processing Letters, 15(1):14–19.