{"id":"arxiv/2608.18617","url":"https://arxiv.org/abs/2608.18617","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3","domain":"cs.CC","source":"arxiv","authors":["Ryoma Aoshima","Takashi Horiyama","Atsuki Nagao","Fumiya Sakamoto","Hibiki Sato","Kazuhisa Seto","Karin Umebayashi"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}