Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).

Given $G(m,n)$ and $k \in \mathbb Z+$:

Does $\mathit S\subset \mathit m$ where |$\mathit S$| $=$ $\mathit k$ exist so that none of $\mathit S$'s nodes are adjacent to nodes of type1, but all type2 nodes in $n$ are adjacent to nodes in $S$? ($S$ is a subset of the $m$ partition).

I can see a solution is easily verified by checking that each type2 in $n$ has a neighbor in $S$ and that |$S$| $=$ $k$. This means the problem is in NP.

To reduce the problem of Set Packing to the above, I am thinking to consider the of all of $m$ nodes's neighborhoods as subsets. But from here I am not sure how to proceed with the problem mapping.

  • $\begingroup$ What does $G(m,n)$ mean? Please define all notation before first use. What is meant by $S \subset m$? Is $m$ a set? An integer? $\endgroup$
    – D.W.
    Apr 8 '20 at 18:40
  • $\begingroup$ Fixed. If there are any other questions I will clarify more. Still learning the formatting standards. $\endgroup$ Apr 8 '20 at 20:08

You cannot reduce set-packing to your problem, unless P=NP.

There is a linear-time algorithm for your problem.

Remove all vertices of type 1 and all their neighbors. Let $m'$ (resp. $n'$) be the set of remaining vertices in $m$ (resp. $n$). If $|m'| \ge k$ and the neighborhood of $m$ contains all the vertices in $n'$, the answer is yes.

If any of the above two conditions is not satisfied then the answer is no:

  • If $|m'| < k$ then any set $S \subseteq m$ with $|S| \ge k$ contains a vertex that is adjacent to some vertex of type 1 in $n$.
  • If there is a vertex $v \in n$ of type 2 that is not in the neighborhood of $m'$, then every vertex $u \in m$ that is adjacent to $v$ is also adjacent to a vertex of type 1 in $n$.
  • $\begingroup$ Hey thanks for the response. I actually misunderstood the problem. The set k must exactly equal partition m, while managing to have covered all the different type2 vertices in n. Is the problem still set packing or is it now vertex cover? Sorry for the confusion!! $\endgroup$ Apr 9 '20 at 0:21
  • $\begingroup$ Your edited problem is a generalization of the decision version of set cover (and hence of vertex-cover). This immediately shows that it is NP-hard. To obtain set cover simply consider instances with no vertices of type 1. $\endgroup$
    – Steven
    Apr 9 '20 at 0:27
  • $\begingroup$ Doh, yes I see it now. Much obliged. $\endgroup$ Apr 9 '20 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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