מירב זהבי

A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a P-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property P. For example, if the property P is that of being a matching, being acyclic, or being disconnected, then we obtain an induced matching, an acyclic matching, and a disconnected matching, respectively. In this paper, we analyze the problems of the computation of these matchings from the viewpoint of Parameterized Complexity with respect to the parameter treewidth.