One-in-Two-Matching Problem is NP-complete

Sergio Caracciolo, Davide Fichera, Andrea Sportiello

2-dimensional Matching Problem, which requires to find a matching of left- to right-vertices in a balanced $2n$-vertex bipartite graph, is a well-known polynomial problem, while va…