<p><strong>EDIT:</strong> changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity.</p>

<p>The following is a reduction of minimum vertex cover to your problem.</p>

<p>Take the graph <span class="math-container">$(V, E)$</span> we want to solve minimum vertex cover on. Set <span class="math-container">$|V_{1}| = |V|^{2} + |V| + |E|$</span>, <span class="math-container">$|V_{2}| = |E| + |V|$</span>.</p>

<p>To every node <span class="math-container">$x \in V$</span> there correspond <span class="math-container">$|E| + 1$</span> nodes <span class="math-container">$a_{x, i}, b_{x}$</span> in <span class="math-container">$V_{1}$</span>. To the edge with index <span class="math-container">$i$</span> there corresponds node <span class="math-container">$f_{i}$</span> in <span class="math-container">$V_{1}$</span> and <span class="math-container">$e_{i}$</span> in <span class="math-container">$V_{2}$</span>. Additionally, there are <span class="math-container">$|V|$</span> nodes <span class="math-container">$c_{1}, \dots, c_{|V|}$</span> in <span class="math-container">$V_{2}$</span>.</p>

<p>Add the edges <span class="math-container">$(a_{x, i}, b_{x})$</span> for all <span class="math-container">$i, x$</span> and <span class="math-container">$(b_{x}, c_{x})$</span> for all <span class="math-container">$x$</span>. This way we get <span class="math-container">$S$</span> to be one larger if we use no edges starting from some <span class="math-container">$a_{x, i}$</span>.</p>

<p>For every edge <span class="math-container">$(x, y) \in E$</span> with index <span class="math-container">$i$</span>, add the edges <span class="math-container">$(a_{x, i}, e_{i}), (a_{y, i}, e_{i})$</span> and <span class="math-container">$(f_{i}, e_{i})$</span>. The idea is that the edge <span class="math-container">$(f_{i}, e_{i})$</span> is "free".</p>

<p>We'll now show that there exists a vertex cover of size <span class="math-container">$k$</span> if and only if there exists an answer <span class="math-container">$S$</span> of size <span class="math-container">$|S| \geq 2|E| + |V| - k$</span>.</p>

<p>Take any solution S to our instance, we'll modify it to create a solution <span class="math-container">$S'$</span> with <span class="math-container">$|S'| \geq |S|$</span> we can read a vertex cover of size <span class="math-container">$k \leq 2|E| + |V| - |S'| \leq 2|E| + |V| - |S|$</span> from.</p>

<p>If some edge <span class="math-container">$(f_{i}, e_{i})$</span> is not in <span class="math-container">$S'$</span>, add it to <span class="math-container">$S'$</span>, possibly removing one other edge adjacent to <span class="math-container">$e_{i}$</span>. This can be done in <span class="math-container">$O(E)$</span> and doesn't decrease the size of <span class="math-container">$S'$</span>.</p>

<p>Assume that the degree of <span class="math-container">$e_{i}$</span> corresponding to <span class="math-container">$(x, y)$</span> is not two, meaning that edge is "not covered". Then <span class="math-container">$a_{x, i}$</span> has degree zero, and we can add <span class="math-container">$(a_{x, i}, e_{i})$</span> to <span class="math-container">$S'$</span>, possibly removing <span class="math-container">$(b_{x}, c_{x})$</span>. This can be done in <span class="math-container">$O(E)$</span> and again doesn't decrease the size of <span class="math-container">$S'$</span>.</p>

<p>Now we build a vertex cover: if we do not have the edge <span class="math-container">$(b_{x}, c_{x})$</span>, add node <span class="math-container">$x$</span> to our vertex cover. Since the degree of <span class="math-container">$e_{i}$</span> is two for all <span class="math-container">$i$</span>, <span class="math-container">$|S| \leq |S'| = 2|E| + (|V| - k)$</span> where <span class="math-container">$k$</span> is the size of our vertex cover. Hence we find a vertex cover of size <span class="math-container">$k \leq 2|E| + |V| - |S|$</span>.</p>

<p>Now take any vertex cover of size <span class="math-container">$k$</span>. Add to <span class="math-container">$S$</span> the edges <span class="math-container">$(f_{i}, e_{i})$</span> for all <span class="math-container">$i$</span>. If <span class="math-container">$x$</span> is not in the vertex cover, add the edge <span class="math-container">$(b_{x}, c_{x})$</span>. For every edge <span class="math-container">$i$</span> at least one of its endpoints <span class="math-container">$x$</span> is in the vertex cover, so <span class="math-container">$(b_{x}, c_{x})$</span> is not in our solution, so we can add <span class="math-container">$(a_{x, i}, e_{i})$</span> to <span class="math-container">$S$</span>. Hence <span class="math-container">$|S| = 2|E| + (|V| - k) \implies k \geq 2|E| + |V| - |S|$</span>.</p>

<p>Hence for maximum size set <span class="math-container">$S$</span> and minimum size of a vertex cover <span class="math-container">$k$</span> we have <span class="math-container">$k = 2|E| + |V| - |S|$</span>, so there exists a vertex cover of size <span class="math-container">$k$</span> or less if and only if there exists a <span class="math-container">$S$</span> with size <span class="math-container">$2|E| + |V| - k$</span> or more.</p>

CC BY-SA 4.0
2019-11-14T06:34:27.233Z
Thanks for the answer. In a solution to our problem, why we can't have both $(a_x,e_i)$ and $(a_y,e_i)$? I can see that we can select $a_x,a_y$ and $f$ and still have an indepedent set, no?
zdm
CC BY-SA 4.0
2019-11-14T12:03:27.880Z
We can select both, but notably that still gives us two edges, as does just one of x or y covering edge i. Hence we get two edges to our solution if we have edges starting from at least one of x or y, and one edge otherwise. I did have a mistake in the wanted size of the answer, now fixed it to 2E over E.
Antti Röyskö
CC BY-SA 4.0
2019-11-14T16:34:28.890Z
I have forgotten to mention one additional constraint: for each $s_1\in S_1$, degree($s_1$) is at most $1$. I will edit my post accordingly.
zdm
CC BY-SA 4.0
2019-11-15T13:37:43.303Z
I have now fixed the solution to work with this additional constraint. The fix was pretty easy, we just make $|E|$ copies of every node $a_{x}$ t get around the degree constraint.
Antti Röyskö
CC BY-SA 4.0
2019-11-14T05:28:17.220Z
2019-11-15T13:36:10.883Z
2019-11-15T13:36:10.883Z
Antti Röyskö
<p>Given a graph <span class="math-container">$G=(V,E)$</span> and a function <span class="math-container">$c:V\mapsto\{1,2\}$</span>. The function <span class="math-container">$c(\cdot)$</span> divides the vertices into two disjoint sets <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span>, where for all <span class="math-container">$v_1\in V_1$</span>, we have <span class="math-container">$c(v_1)=1$</span> and for all <span class="math-container">$v_2\in V_2$</span>, we have <span class="math-container">$c(v_2)=2$</span>. There is no edge between <span class="math-container">$v_2\in V_2$</span> and <span class="math-container">$v_2'\in V_2$</span>. There are edges between <span class="math-container">$v_1\in V_1$</span> and <span class="math-container">$v_2\in V_2$</span> and between <span class="math-container">$v_1\in V_1$</span> and <span class="math-container">$v_1'\in V_1$</span> (for <span class="math-container">$v_1\ne v_1'$</span>). Find a two-to-one matching between <span class="math-container">$V_1$</span> and <span class="math-container">$V_2$</span> of maximum cardinality. That is, a set <span class="math-container">$S:=S_1\times S_2\subset V_1\times V_2$</span> such that:</p>

<ul>
<li>cardinality(<span class="math-container">$S$</span>) is maximum;</li>
<li>for each <span class="math-container">$(s_1,s_2)\in S$</span>, <span class="math-container">$\{s_1,s_2\}\in E$</span> ;</li>
<li><span class="math-container">$S_1$</span> is an independent set;</li>
<li>for each <span class="math-container">$s_2\in S_2$</span>, degree(<span class="math-container">$s_2$</span>) is at most <span class="math-container">$2$</span>; and</li>
<li>for each <span class="math-container">$s_1\in S_1$</span>, degree(<span class="math-container">$s_1$</span>) is at most <span class="math-container">$1$</span>. <span class="math-container">$\leftarrow$</span> <strong>EDIT</strong></li>
</ul>

<p>Is this problem NP-hard?</p>

<p>I was trying to prove that this problem is NP-hard by reduction from <a href="https://webhome.cs.uvic.ca/~thomo/papers/cikm2016group.pdf" rel="nofollow noreferrer">Conflict-Aware Weighted Bipartite B-Matching Problem (CA-WBM)</a>. </p>

<p>The authors proved that CA-WBM is NP-hard by a reduction from weighted independent set problem. Since I do not have weights in my problem, I was able to prove that even the Conflict-Aware Unweighted Bipartite B-Matching Problem (CA-UBM) is NP-hard (since the unweighted independent set is NP-hard). But I could not reduce CA-UBM to my problem. The issue is that in my problem the cost function is restricted to take only two values <span class="math-container">$\{1,2\}$</span>.</p>

<np-hardness><reductions>
What Is the Complexity of This Two-to-One Matching Problem?
zdm
# What Is the Complexity of This Two-to-One Matching Problem?

(Asked by: username_0 on 2019-11-14)

Given a graph $G=(V,E)$ and a function $c:V\mapsto\{1,2\}$. The function $c(\cdot)$ divides the vertices into two disjoint sets $V\_1$ and $V\_2$, where for all $v\_1\in V\_1$, we have $c(v\_1)=1$ and for all $v\_2\in V\_2$, we have $c(v\_2)=2$. There is no edge between $v\_2\in V\_2$ and $v\_2'\in V\_2$. There are edges between $v\_1\in V\_1$ and $v\_2\in V\_2$ and between $v\_1\in V\_1$ and $v\_1'\in V\_1$ (for $v\_1\ne v\_1'$). Find a two-to-one matching between $V\_1$ and $V\_2$ of maximum cardinality. That is, a set $S:=S\_1\times S\_2\subset V\_1\times V\_2$ such that:

* cardinality($S$) is maximum;
* for each $(s\_1,s\_2)\in S$, $\{s\_1,s\_2\}\in E$ ;
* $S\_1$ is an independent set;
* for each $s\_2\in S\_2$, degree($s\_2$) is at most $2$; and
* for each $s\_1\in S\_1$, degree($s\_1$) is at most $1$. $\leftarrow$ **EDIT**

Is this problem NP-hard?

I was trying to prove that this problem is NP-hard by reduction from [Conflict-Aware Weighted Bipartite B-Matching Problem (CA-WBM)](https://webhome.cs.uvic.ca/~thomo/papers/cikm2016group.pdf).

The authors proved that CA-WBM is NP-hard by a reduction from weighted independent set problem. Since I do not have weights in my problem, I was able to prove that even the Conflict-Aware Unweighted Bipartite B-Matching Problem (CA-UBM) is NP-hard (since the unweighted independent set is NP-hard). But I could not reduce CA-UBM to my problem. The issue is that in my problem the cost function is restricted to take only two values $\{1,2\}$.

**Tags:** np-hardness, reductions

---

## 1 answers

### Answer by username_1 on 2019-11-14. Score: 2 | Accepted answer

**EDIT:** changed a few things to make this work with the new constraint, also rewrote the whole proof to add details and clarity.

The following is a reduction of minimum vertex cover to your problem.

Take the graph $(V, E)$ we want to solve minimum vertex cover on. Set $|V\_{1}| = |V|^{2} + |V| + |E|$, $|V\_{2}| = |E| + |V|$.

To every node $x \in V$ there correspond $|E| + 1$ nodes $a\_{x, i}, b\_{x}$ in $V\_{1}$. To the edge with index $i$ there corresponds node $f\_{i}$ in $V\_{1}$ and $e\_{i}$ in $V\_{2}$. Additionally, there are $|V|$ nodes $c\_{1}, \dots, c\_{|V|}$ in $V\_{2}$.

Add the edges $(a\_{x, i}, b\_{x})$ for all $i, x$ and $(b\_{x}, c\_{x})$ for all $x$. This way we get $S$ to be one larger if we use no edges starting from some $a\_{x, i}$.

For every edge $(x, y) \in E$ with index $i$, add the edges $(a\_{x, i}, e\_{i}), (a\_{y, i}, e\_{i})$ and $(f\_{i}, e\_{i})$. The idea is that the edge $(f\_{i}, e\_{i})$ is "free".

We'll now show that there exists a vertex cover of size $k$ if and only if there exists an answer $S$ of size $|S| \geq 2|E| + |V| - k$.

Take any solution S to our instance, we'll modify it to create a solution $S'$ with $|S'| \geq |S|$ we can read a vertex cover of size $k \leq 2|E| + |V| - |S'| \leq 2|E| + |V| - |S|$ from.

If some edge $(f\_{i}, e\_{i})$ is not in $S'$, add it to $S'$, possibly removing one other edge adjacent to $e\_{i}$. This can be done in $O(E)$ and doesn't decrease the size of $S'$.

Assume that the degree of $e\_{i}$ corresponding to $(x, y)$ is not two, meaning that edge is "not covered". Then $a\_{x, i}$ has degree zero, and we can add $(a\_{x, i}, e\_{i})$ to $S'$, possibly removing $(b\_{x}, c\_{x})$. This can be done in $O(E)$ and again doesn't decrease the size of $S'$.

Now we build a vertex cover: if we do not have the edge $(b\_{x}, c\_{x})$, add node $x$ to our vertex cover. Since the degree of $e\_{i}$ is two for all $i$, $|S| \leq |S'| = 2|E| + (|V| - k)$ where $k$ is the size of our vertex cover. Hence we find a vertex cover of size $k \leq 2|E| + |V| - |S|$.

Now take any vertex cover of size $k$. Add to $S$ the edges $(f\_{i}, e\_{i})$ for all $i$. If $x$ is not in the vertex cover, add the edge $(b\_{x}, c\_{x})$. For every edge $i$ at least one of its endpoints $x$ is in the vertex cover, so $(b\_{x}, c\_{x})$ is not in our solution, so we can add $(a\_{x, i}, e\_{i})$ to $S$. Hence $|S| = 2|E| + (|V| - k) \implies k \geq 2|E| + |V| - |S|$.

Hence for maximum size set $S$ and minimum size of a vertex cover $k$ we have $k = 2|E| + |V| - |S|$, so there exists a vertex cover of size $k$ or less if and only if there exists a $S$ with size $2|E| + |V| - k$ or more.

> **Comments:**
> **username_0**: Thanks for the answer. In a solution to our problem, why we can't have both $(a_x,e_i)$ and $(a_y,e_i)$? I can see that we can select $a_x,a_y$ and $f$ and still have an indepedent set, no?  
> **username_1**: We can select both, but notably that still gives us two edges, as does just one of x or y covering edge i. Hence we get two edges to our solution if we have edges starting from at least one of x or y, and one edge otherwise. I did have a mistake in the wanted size of the answer, now fixed it to 2E over E.  
> **username_0**: I have forgotten to mention one additional constraint: for each $s_1\in S_1$, degree($s_1$) is at most $1$. I will edit my post accordingly.  
> **username_1**: I have now fixed the solution to work with this additional constraint. The fix was pretty easy, we just make $|E|$ copies of every node $a_{x}$ t get around the degree constraint.  

---

