Hardness of Forcing Unique Perfect Matchings in Bipartite Graphs of Maximum Degree 3
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.18617
curl -X POST /api/v1/records/arxiv/2608.18617/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.18617/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'