Maximise the number of nodes with degree zero in a bipartite graph

86 Views Asked by At

Let $G = (V \cup W, E)$ be a bipartite graph where $V \cap W = \emptyset$ and $E$ consists of edges between nodes in $V$ and $W$. All nodes in $W$ must have degree at least one whereas nodes in $V$ are allowed to have any degree (including zero). I want to assign/dedicate each node in $W$ to a specific node in $V$; i.e prune the edges such that $deg(w) = 1$ for all nodes in $W$. However, I want to do it in such a way, that as many nodes in $V$ ends up having degree zero.

As I see it, it is somewhat the "reverse problem" to that of a maximal matching problem. I haven't been able to find any similar questions nor can I figure out if it is a NP hard problem. The closest I have been to track down a similar problem is

https://stackoverflow.com/questions/20051303/optimization-of-bipartite-graph

which is not exactly what is my case.