5
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ This problem is a resticted version of Maximum $P_3$-matching problem, that is known to be NP-hard even for cubic bipartite planar $2$-connected graphs (theorem 4.2). $\endgroup$ – Smylic May 8 '17 at 0:32
  • $\begingroup$ @Smylic Interesting, but it does not seem clear that the proof can be adapted to the restricted version. And there's some evidence that it can't: the reduction is to 3-dimensional matching, which is NP-hard even when we're looking for a perfect 3D matching. But as shown above, the perfect matching version of my problem is in P. $\endgroup$ – Misha Lavrov May 8 '17 at 1:23
3
+100
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Does this really cover all possible ways of failing to have a 2-to-1 matching? What about if some $a\in A$ is connected to only one $b\in B$? Then it seems like you can never (for any $k$) get a perfect matching in the modified graph, no matter how many new totally-connected nodes you add to $A$. $\endgroup$ – user326210 Apr 11 '18 at 22:04
  • 1
    $\begingroup$ Clever! The edges between each pair of cloned vertices in $A$ ensure that neither or both of them are matched to $B$, and the $k$ extra vertices use up $k$ vertices in $B$ left unmatched to $A$. $\endgroup$ – Misha Lavrov Apr 11 '18 at 22:08
  • $\begingroup$ @user326210 If some $a \in A$ is connected to only one $b \in B$, then it will always be matched to its clone for any value of $k$. $\endgroup$ – Misha Lavrov Apr 11 '18 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.