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…
Best Answer
The problem has a polynomial time algorithm.
As a first step, it obviously reduces to the more modest goal of deciding whether there is a $2$-to-$1$ matching $M$ such that exactly $k$ vertices in $B$ are unmatched (degree $0$ in $M$). Here $k$ is given as input.
Your idea of duplicating each vertex in $A$ can be made to work. Start with the construction you described which has two copies of each $a\in A.$ For each $a\in A$ join its two copies. Add $k$ new vertices each of which is adjacent to every vertex in $B.$ Perfect matchings in this new graph correspond to $2$-to-$1$ matchings in the original graph, together with an "orientation" of each $\vee,$ that have exactly $k$ unmatched vertices in $B.$ The problem of testing for a perfect matching has a polynomial time algorithm.
An alternative to the duplication trick is to appeal to Cornuéjols's General factors of graphs algorithm, or more generally edge CSPs (aka delta matroid intersection).