# 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.
• Does such a set $X^+$ always even exist? Suppose $G$ is a star graph, and $X$ contains only the center of $G$. Now trivially, $X^+$ can't be as large as $Y$. – Juho Dec 30 '13 at 18:42
• In general you are right. So the function should either return $X^+$ or report that it doesn't exist. It is still interesting, whether this function is polynomial. – Erel Segal-Halevi Dec 30 '13 at 19:16
• Could you simply compute a maximum matching of $G$ (König's theorem), and see if its size is more than $|Y|$? – Juho Dec 30 '13 at 19:30
• @Juho I doubt that would suffice, because you could probably have some node $x$ that isn't incident with an edge of some maximum matching $M$, but only adjacent with nodes in $f(M)$, or there could be an overlap of the neighbourhood of $x$ and $f(M)$ that's small enough such that $x$ could be included while maintaining the inequality. – G. Bach Dec 30 '13 at 19:58
• I guess it's already clear the authors should justify their claim... :-) – Juho Jan 1 '14 at 15:41

## 1 Answer

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| < 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>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)$.

• I can't follow your last paragraph. Also, note that you're using the fact that $X^+$ is the largest in a very weak sense: just that it satisfies $|X^+| \geq |f(X^+)|$, and that includes your additional vertices $V$+$;$X^+ = V^+$would satisfy these properties just as well. – Yuval Filmus Dec 31 '13 at 21:07 • I can see that if$\text{largest}$is in P, then so is the following: "given$i$, find$X''$such that$|X''| \ge |f(X'')|-i$" (by running$\text{largest}(G^i)$). It smells like$\text{largest}(G_i)$might let you show that the following problem would also be in P: "given$i$, find$X''$such that$|X''| \ge |f(X'')|+i$". Is that right? If so, how does that help? – D.W. Dec 31 '13 at 22:17 • Ahh, if$\text{exists}(\cdot,\cdot,\cdot)$actually means$\text{exact}(\cdot,\cdot,\cdot)$, then I can follow most of your reasoning, but I run into the same problem as Yuval: I can't follow the last paragraph. I can see how this procedure would let you tell that$\text{exists}(G,k,m)$is true for some pairs of$k,m$, but I can't see how to test it for all pairs of$k,m$(maybe there's a pair$k,m$for which$\text{exists}(G,k,m)$is true but your procedure never happens to find$k,m$; how do you know that cannot happen?). – D.W. Dec 31 '13 at 22:19 • @D.W. you're right, there is some wishful thinking going on. I thought that$G^i$and$G_j$transformations should be enough, but I now see, than even for an "N" shaped graph, deciding$\text{exact}(G, 1, 2)$is not possible. However. I have ideas about fighting it. If I define$\overline{G}$to be a graph, where for every$x \in X$a new$y \in Y$is added with a single edge$(x, y)$. This operation should be only needed once, before all others. That way$\overline{G}^i$and$\overline{G}_j$would give me more reliable control over how many vertices of$X$are allowed to participate in$X^+\$. – Karolis Juodelė Dec 31 '13 at 23:55