I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is incident to exactly two or exactly zero selected edges, and each right-hand vertex is incident to at most one selected edge?

Obviously if replace "two" with one we have the matching problem, which can be solved in polynomial time. I've tried in vain to solve my problem using network flow or matching, and am also stumped when I try to reduce from NP-complete problems.

  • 1
    @Marzio Thanks a lot for the idea. I don't think this method always works though. For example, suppose $|L|=1$, $|R|=100$, and there is an edge from the unique vertex in $L$ to each vertex in $R$. If I'm not mistaken, the maximum matching in $G'$ has 50 edges. – James Trimble Feb 19 '16 at 19:53
  • You're right, it's trickier; I delete the comment and think a little bit more about it ... – Marzio De Biasi Feb 19 '16 at 19:56
  • Perhaps this variation works; let $G= (L \cup R, E)$ be the given bipartite graph ($L, R$ are the Left and Right sets). Build a flow graph $G' = (V',E')$ in this way: for each pair $v_i, v_j \in R$ add a node $v'_{i,j}$; for each $u_h \in L$ add a node $u'_h$ and if $ (u_h,v_1)...(u_h,v_s) \in E$ add edges $e'_{h,i,j} = (u'_h,v'_{i,j}) \in E'\; 1 \leq i < j \leq s$. Finally add a source $s'$ connected to the $u'_h$ and connect each $v'_{i,j}$ to a common sink $t'$. Every edge of $E'$ has capacity $1$; calculate the max-flow from $s'$ to $t'$. – Marzio De Biasi Feb 19 '16 at 20:56
  • 2
  • @MarzioDeBiasi Thanks for the suggestion. I think this doesn't work if $|L|=|R|$ and there is an edge from each vertex in $L$ to each vertex in $R$. In this case, there are enough $v'_{i,j}$ vertices that we can have a flow of $k$ from $s'$ to $t'$. – James Trimble Feb 20 '16 at 10:50
up vote 10 down vote accepted

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.

Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$.

  1. Add vertices in $R$ to $V'$.
  2. For each vertex $v \in L$, add vertices $v_1,v_2$ to $V'$.
  3. Add vertices $t_1,\ldots,t_{n-k}$ to $V'$.
  4. Add edge $v_1v_2$ to $E'$ for each $v\in L$. It has weight $0$.
  5. Add edge $v_iu$ to $E'$ for each $vu\in E$,$u\in R,v\in L,i\in \{1,2\}$. It has weight $1$.
  6. Add edge $ut_i$ for each $u\in R$ and $1\leq i\leq n-k$. It has weight $0$.

Claim: The maximum weight perfect matching in $G'$ has value $k$ iff the "two or zero" matching has a solution of at least $k$ edges.

  • 1
    Perfect! Thanks very much. Even better, this looks like it will work if we want to find a maximum weighted "two or zero" matching. – James Trimble Feb 20 '16 at 10:52
  • 2
    @JamesTrimble no problem. I'm curious about how this problem come up. – Chao Xu Feb 20 '16 at 17:51
  • 2
    It's related to a project for a client that, unfortunately, I can't write in detail about here. The theoretical problem is just for fun. I was discussing it with friends and we worked out that "one or zero" matching is in P (since it's just matching) and "three or zero" matching is NP-complete (by a simple reduction from 3D matching, with an element in $R$ created for each vertex in the 3D matching problem, and an element in $L$ created for each hyperedge). We got stuck at "two or zero"! – James Trimble Feb 22 '16 at 17:55

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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