- A bipartite graph G=(U,V,E)
- Integers n and k.
- Is there a subset of U of size k that has at most n neighbours?
I am trying to figure out whether this problem is NP-hard (I suspect so), but couldn't find any reduction so far. The only well-known NP-hard problems for bipartite graphs seem to be finding bipartite subgraphs in graphs , and railway schedule optimization. It seems somewhat like an inverse of set cover, but is also different from set packing (which appears called as inverse of set cover).
Does anyone have ideas which problems could be related?
: Computers and Intractability: A Guide to the Theory of NP-Completeness