  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 $W[1]$-hard when parameterized by solution size
$k$ even when restricted to split graphs and bipartite graphs. We observe that
PMS is FPT when parameterized by clique-width, and give FPT algorithms with
respect to the parameters distance to cluster, distance to co-cluster and
treewidth. Complementing FPT results, we show that PMS does not admit a
polynomial kernel when parameterized by vertex cover number unless $NP\subseteq
coNP/poly$. We also provide an exact exponential algorithm running in time
$O^*(1.966^n)$. Finally, considering graphs with structural assumptions, we
show that PMS remains $NP$-hard on planar graphs.
