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


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

  • $\begingroup$ 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? $\endgroup$
    – zdm
    Commented Nov 14, 2019 at 6:34
  • $\begingroup$ 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. $\endgroup$ Commented Nov 14, 2019 at 12:03
  • $\begingroup$ 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. $\endgroup$
    – zdm
    Commented Nov 14, 2019 at 16:34
  • $\begingroup$ 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. $\endgroup$ Commented Nov 15, 2019 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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