<p>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.</p>

CC BY-SA 3.0
2015-11-21T11:22:03.120Z
Thanks a lot, that looks elegant! Will credit you should this go any further.
Simon Razniewski
CC BY-SA 3.0
2015-11-21T06:55:34.477Z
2015-11-21T06:55:34.477Z
David Eppstein
<p><strong>Given</strong>: </p>

<ul>
<li>A bipartite graph <em>G=(U,V,E)</em> </li>
<li>Integers <em>n</em> and <em>k</em>.</li>
</ul>

<p><strong>Decision Problem</strong>: </p>

<ul>
<li>Is there a subset of <em>U</em> of size <em>k</em> that has at most
<em>n</em> neighbours?</li>
</ul>

<p>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 <a href="http://everything.explained.today/Bipartite_graph/" rel="noreferrer">railway schedule optimization</a>. It seems somewhat like an inverse of set cover, but is also different from set packing (which appears called as inverse of set cover).</p>

<p>Does anyone have ideas which problems could be related?</p>

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

CC BY-SA 3.0
2015-11-24T22:27:41.703Z
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 http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4929
Serge Gaspers
<np-hardness><set-cover><bipartite-graphs>
Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?
Simon Razniewski
# Bipartite Graphs - Maximum subset of one partition with at most n neighbours - NP-hard?

(Asked by: username_0 on 2015-11-21)

**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](http://everything.explained.today/Bipartite_graph/). 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

**Tags:** np-hardness, set-cover, bipartite-graphs
> **Comments:**
> **username_1**: 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 http://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/view/4929  

---

## 1 answers

### Answer by username_2 on 2015-11-21. Score: 10 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks a lot, that looks elegant! Will credit you should this go any further.  

---

