Perfectly Matched Sets in Graphs: Hardness, Kernelization Lower Bound, and FPT and Exact Algorithms

In an undirected graph $G=(V,E)$, we say $(A,B)$ is a pair of perfectly matched sets if $A$ and $B$ are disjoint subsets of $V$ and every vertex in $A$ (resp. $B$) has exactly one neighbor in $B$ (resp. $A$). The size of a pair of perfectly matched sets $(A,B)$ is $|A|=|B|$. The PERFECTLY MATCHED SETS problem is to decide whether a given graph $G$ has a pair of perfectly matched sets of size $k$. We show that PMS is $NP$-hard on planar graphs and $W[1]$-hard when parameterized by solution size $k$ even when restricted to split graphs and bipartite graphs. We show that PMS parameterized by vertex cover number does not admit a polynomial kernel unless $NP\subseteq coNP/poly$. We give FPT algorithms with respect to the parameters distance to cluster, distance to co-cluster and treewidth. We also provide an exact exponential algorithm running in time $O^*(1.964^n)$.