Largest set of vertices that is larger than its set of neighbors I am reading a unpublished paper describing an algorithm. In one step of the algorithm, there is a bipartite graph $G(X,Y,E)$, where $X=\{1,...,n\}$.

For every subset $X' \subseteq X$, they define

$$f(X')=\bigcup_{i \in X'} \{j \in Y| (i,j)\in E\}.$$

In other words, $f(X')$ is the set of neighbors of vertices in $X'$.

Then they define:

$$ X^+ = \arg \max_{X' \subseteq \{2,3,...,n\}\ s.t.\ |X'|\geq|f(X')|}\{|X'|\}$$

i.e., $X^+$ is a largest subset of $\{2,3,...,n\}$ such that $X^+$ is at least as large as the set of its neighbors in $Y$ (i.e., the largest subset such that $|X^+| \ge |f(X^+)|$).

And then they do some stuff with this $X^+$.

MY QUESTION IS: Can this $X^+$ be found in polynomial time? 

The authors do not prove that it can, but this is implied by the paper (otherwise the algorithm itself cannot be polynomial). Maybe it is so obvious that only I haven't seen this?

EDIT: The following similar problem can be solved easily:

Find the largest set of vertices in X with less than |Y| neighbours.


Solution: find a $y \in Y$ with a minimal number of neighbours in $X$. Return the set that includes all vertices in $X$ except $y$'s neighbours.

What about the following similar problem?

Find the largest set of vertices in X with less than |Y|/2 neighbours.
Consider the following problem. 


  Find $X''$ such that $|X''| = k$ and $|f(X'')| = m$


If it was P then so would set cover: fix $m = |Y|$ and iterate over all $k \in \{1, \dots, |X|\}$ to find a minimum.



Let's call this problem $\text{exact}(G, k, m)$ and let's call your problem $\text{largest}(G)$.

Let $G(X, Y, E)$ be any bipartite graph. Let $G^1$ be a graph with one additional vertex in $X$, not connected to anything. Let ${_1}G$ be a graph where for every vertex of $X$, a new vertex is added to $Y$ and the two are connected. Let ${^1}G$ be a graph where for every vertex of $Y$, a new vertex is added to $X$ and the two are connected. Let ${_k^l}G^i = ({_k}({^l}G))^i$ be these transformations applied repeatedly. Note the order.

$G^i$ will be used to artificially raise $|X^+|$ and therefore $|f(X^+)|$. ${_k}G$ will be used to weight down vertices $v$, so we can control whether $v \in X^+$ even if $f(v) \subset f(X^+)$ in $G$. ${^l}G$ will be used to prioritize larger $|f(X^+)|$.

Say $X^+ = \text{largest}(G^i)$. This implies that $\text{exact}(G, |X^+|-i, |f(X^+)|)$, because you know that the $i$ new vertices in $X$ will be used and thus $|X^+|$ old vertices have a neighborhood of $|f(X^+)|$ old vertices. Similarly $X^+ = \text{largest}({_k}G)$ implies $\text{exact}(G, |X^+|, |f(X^+)|-k|X^+|)$.



To find $\text{exact}(G, k, m)$, let $X^+_i = \text{largest}({_M^i}G^{(mi+k)M+(m-k)})$ for sufficiently large $M$ (say, $M = |X|+|Y|$).


If $|X^+_0| &lt; kM + (m-k) + k$ then $\text{exact}(G, k, m)$ is false.
If $|f(X^+_i)| = (mi+k)M+m$ then $\text{exact}(G, k, m)$ is true. Note that if $\text{exact}(G, k+ix, m-x)$, then $|f(X^+_i)|$ could also have the value $(mi+k)M+m-x$.
Raise $i$ until $\forall x&gt;0, \neg \text{exact}(G, k+ix, m-x)$ (you can jump directly to $i=|X|$). Then $|f(X^+_i)| = (mi+k)M+m$ if and only if $\text{exact}(G, k, m)$.