Suppose that we are given a bipartite graph $G$ with bipartition $V(G) = A \mathbin{\dot{\cup}} B$. A $2$-to-$1$ matching in $G$ is a subgraph $M$ such that:
- For all vertices $v \in A$, $\deg_{M} v$ is either $0$ or $2$.
- For all vertices $w \in B$, $\deg_{M} w$ is either $0$ or $1$.
In other words, we assign some vertices in $A$ two of their neighbors in $B$ so that no vertex in $B$ is assigned to more than vertex in $A$. The subgraph $M$ will consist of disjoint $\vee$ shapes with the "corner" in $A$ and the two "prongs" in $B$.
Can we efficiently find a $2$-to-$1$ matching in $G$ of maximum size?
If $|B| = 2|A|$ and we are looking for a perfect $2$-to-$1$ matching (one that uses every vertex of $G$) then this is easily reduced to an ordinary bipartite matching problem. Simply replace each vertex $v \in A$ by two copies which have the same neighbors in $B$. The $2$-to-$1$ perfect matchings in $G$ correspond exactly to the perfect matchings in this modified graph $G'$. Hall's theorem tells us exactly when such a perfect matching exists, and a maximum-flow algorithm can find one.
But if a perfect $2$-to-$1$ matching does not exist, then a maximum matching in $G'$ does not necessarily correspond to a maximum $2$-to-$1$ matching in $G$. It doesn't give us a $2$-to-$1$ matching at all: sometimes the matching in $G'$ might use only one of two copies of a vertex $v \in A$, which doesn't give us anything useful in $G$.
(And if we're going to throw these away, then sometimes a smaller matching in $G'$ would have given us a larger $2$-to-$1$ matching in $G$, because we'd have to throw away fewer edges.)
The closest NP-complete problem I've found to this one is rainbow matching: in an edge-colored graph, a rainbow matching is a matching all of whose edges have different colors.
The $2$-to-$1$ matching problem is a special case of rainbow matching: we can define a graph $H$ whose vertex set is $B$, and for every vertex $a \in A$, we put an edge between every two neighbors of $a$ that receives a color $c_a$. Then a rainbow matching in $H$ gives us a $2$-to-$1$ matching in $G$.
But the edge-coloring of $H$ is a very special one, in which each color class is a clique. So I'm not sure that we should expect such a special case to still be NP-complete. The same issue pops up with every other similar problem I consider...