A Parameterized View on P-matchings

Umang Bhaskar
Tuesday, 12 Sep 2023, 16:00 to 17:00
via Zoom in A201
A matching M is a P-matching if the subgraph induced by the endpoints of the edges of M satisfies property P. For example, if the property P is that of being a graph, being a matching, being acyclic, or being disconnected, then we obtain the usual matching, an induced matching, an acyclic matching, and a disconnected matching, respectively. First, I will survey the latest developments related to P-matchings from the viewpoint of Parameterized Complexity. Then, I will describe some results focusing majorly on acyclic matchings and on three algorithmic paradigms: approximation hardness, kernelization lower bounds, and FPT algorithms with respect to various parameters such as treewidth and some below-guarantee parameters. The second part of the talk is based on the two recent joint works with Meirav Zehavi, which appeared in WG’2023.