On the maximum 2-1 matching (Q1095813)

Given a simple bipartite graph \(G=(X,Y,E)\), \(M\subseteq E\) is called a 2- 1 matching of G if: 1) for all \(x\in X\), either two edges or none in M is incident to x and 2) for all \(y\in Y\), at most one edge in M is incident to y. We describe an efficient algorithm for finding a maximum 2-1 matching in a given bipartite graph. We also formulate and prove a duality theorem for 2-1 matching.