Choosing well-connected set in directed bipartite graph

Question

Consider a directed bipartite graph $G=(V,E)$. Can we always choose some set of vertices $V'\subseteq V$ such that no two vertices in $V'$ are connected by an edge, but any vertex in $V\backslash V'$ has an edge pointing to a vertex in $V'$?

Answer 1

You can find such a set, and I will prove it by providing an algorithm which does so (i.e. constructs such a set).

First, let's paint any vertex of out-degree zero red; then, paint all its predecessors (neighbors that have an edge pointing to it) blue. Observe that for any unpainted vertex it has no red neighbors:

• no successors, because otherwise it would be painted blue,
• no predecessors, because the red one would not be of out-degree zero.

The latter is also the reason for red vertices having no edges between them. Now take all the vertices of unpainted-out-degree zero and again paint them red, and once more, paint all the predecessors of the red vertices blue. Repeat until there is no more vertices of unpainted out-degree zero.

Now there might be some more vertices left, but they

• all belong to some strongly connected components,
• they are disjoint from any vertices from the first part.

For those reasons, it is enough to paint one side of the bipartition red and the other side blue. Note that before there were no vertices of unpainted out-degree zero, so now either they are blue and have a red predecessor or are red themselves. As the whole graph has been painted, set $V'$ to be the vertices painted red and you are done.

I hope this helps $\ddot\smile$

Edit: Significant correction.