𝒫-matchings Parameterized by Treewidth
share
A matching is a subset of edges in a graph G that do not share an endpoint. A matching M is a 𝒫-matching if the subgraph of G induced by the endpoints of the edges of M satisfies property 𝒫. For example, if the property 𝒫 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.
READ FULL TEXT