# What Is the Complexity of This Two-to-One Matching Problem?

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

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\}$$.

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.

• 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 Nov 14 '19 at 6:34
• 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ö Nov 14 '19 at 12:03
• 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 Nov 14 '19 at 16:34
• 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ö Nov 15 '19 at 13:37