Connected and Disconnected Matchings - Masquio, Bruno P.; Pinto, Paulo E. D.; Szwarcfiter, Jayme L. (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC); 2023: Anais do XXXVI Concurso de Teses e DissertaçõesDO - 10.5753/ctd.2023.229529, 2023)
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.