Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3

Abstract

In a graph $G$, a set of edges $F$ is called a \emph{forcing set} if there exists a unique perfect matching $M$ such that $F\subseteq M$. Similarly, a set of edges $A$ is called an \emph{anti-forcing set} if the graph with edge set $E(G)\setminus A$ has a unique perfect matching. It is known that, given a bipartite graph $G$ of maximum degree~$3$ and a perfect matching $M$, the problem of deciding whether there exists a forcing set of size at most $k$ for $M$ is NP-complete. Moreover, given a bipartite graph $G$ of maximum degree~$4$ and a perfect matching $M$, the problem of deciding whether there exists an anti-forcing set of size at most $k$ for $M$ is NP-complete. Furthermore, given a bipartite graph of maximum degree~$5$, the problem of deciding whether there exists a perfect matching $M$ that can be made unique by a forcing set of size at most $k$ is also NP-complete. In contrast, the computational complexity of deciding whether there exists a perfect matching $M$ that can be made unique by an anti-forcing set of size at most $k$ is not known, even for general graphs. In this paper, we show that all of these problems remain NP-complete even when restricted to bipartite graphs of maximum degree~$3$.

9 pages, 5 figures