<p><a href="https://cstheory.stackexchange.com/questions/31882/assignment-problem-with-multiple-workers-for-each-job">The answer here</a> 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.</p>

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

<ol>
<li>Add vertices in $R$ to $V'$.</li>
<li>For each vertex $v \in L$, add vertices $v_1,v_2$ to $V'$.</li>
<li>Add vertices $t_1,\ldots,t_{n-k}$ to $V'$.</li>
<li>Add edge $v_1v_2$ to $E'$ for each $v\in L$. It has weight $0$.</li>
<li>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$.</li>
<li>Add edge $ut_i$ for each $u\in R$ and $1\leq i\leq n-k$. It has weight $0$.</li>
</ol>

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

CC BY-SA 3.0
2016-02-20T10:52:48.127Z
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
CC BY-SA 3.0
2016-02-20T17:51:59.497Z
@JamesTrimble no problem. I'm curious about how this problem come up.
Chao Xu
CC BY-SA 3.0
2016-02-22T17:55:31.043Z
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
CC BY-SA 3.0
2016-02-20T03:20:18.213Z
2016-02-20T03:20:18.213Z
2017-04-13T12:32:28.077Z
Chao Xu
<p>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?</p>

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

CC BY-SA 3.0
2016-02-19T19:53:57.470Z
@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
CC BY-SA 3.0
2016-02-19T19:56:15.053Z
You're right, it's trickier; I delete the comment and think a little bit more about it ...
Marzio De Biasi
CC BY-SA 3.0
2016-02-19T20:56:10.017Z
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
CC BY-SA 3.0
2016-02-19T22:18:15.200Z
related: http://cstheory.stackexchange.com/q/31882/15637
Thomas Kalinowski
CC BY-SA 3.0
2016-02-20T10:50:50.807Z
@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
<complexity-classes><p-vs-np><bipartite-graphs>
Is "two or zero" matching in a bipartite graph NP complete?
James Trimble
# Is "two or zero" matching in a bipartite graph NP complete?

(Asked by: username_0 on 2016-02-19)

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.

**Tags:** complexity-classes, p-vs-np, bipartite-graphs
> **Comments:**
> **username_0**: @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.  
> **username_1**: You're right, it's trickier; I delete the comment and think a little bit more about it ...  
> **username_1**: 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'$.  
> **username_2**: related: http://cstheory.stackexchange.com/q/31882/15637  
> **username_0**: @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'$.  

---

## 1 answers

### Answer by username_3 on 2016-02-20. Score: 9 | Accepted answer

[The answer here](https://cstheory.stackexchange.com/questions/31882/assignment-problem-with-multiple-workers-for-each-job) 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.

> **Comments:**
> **username_0**: Perfect! Thanks very much. Even better, this looks like it will work if we want to find a maximum _weighted_ "two or zero" matching.  
> **username_3**: @JamesTrimble no problem. I'm curious about how this problem come up.  
> **username_0**: 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"!  

---

