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

Question

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

Answer 1

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.