6
$\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$
2
  • $\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, 2017 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$ May 8, 2017 at 1:23

1 Answer 1

5
+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$
3
  • 1
    $\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, 2018 at 22:04
  • 2
    $\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$ Apr 11, 2018 at 22:08
  • 1
    $\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$ Apr 11, 2018 at 22:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .