# Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

Given:

• A bipartite graph G=(U,V,E)
• Integers n and k.

Decision Problem:

• 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 [1], 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?

[1]: Computers and Intractability: A Guide to the Theory of NP-Completeness

• Since you are also asking about related problems: Some time ago, we showed that the Hall Set problem is W[1]-hard parameterized by k: Given a bipartite graph G=(U,V,E) and an integer k, is there a subset S of U of size at most k such that |N(S)| < |S|? The reduction is similar to David's reduction below and also proves NP-hardness. We needed it as an intermediate problem to prove W[1]-hardness of a Local Search problem. See aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4929 – Serge Gaspers Nov 24 '15 at 22:27

It's NP-complete by a reduction from cliques in graphs. Given an arbitrary graph $G$, construct a bipartite graph from its incidence matrix, by making one side $U$ of the bipartition correspond to the edges of $G$ and the other side correspond to the vertices of $G$. Then $G$ has a clique of size $\omega$ if and only if the constructed bipartite graph has a set of $\binom{\omega}{2}$ vertices in $U$ that has at most $\omega$ neighbors on the other side of the bipartition.