Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph.

I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":


Problem:


Given a bipartite graph $G = (U,V,E)$, find an independent set $U' \cup V'$ which is as large as possible, where $U' \subseteq U$ and $V' \subseteq V$. A set is independent if there are no edges of $E$ between
elements of the set.


Solution:


Construct a flow graph on the vertices $U \cup V \cup \{s,t\}$. For
each edge $(u,v) \in E$ there is an infinite capacity edge from $u$ to
$v$. For each $u \in U$, there is a unit capacity edge from $s$ to $u$,
and for each $v \in V$, there is a unit capacity edge from $v$ to
$t$.


Find a finite capacity cut $(S,T)$, with $s \in S$ and $t \in T$. Let
$U' = U \cap S$ and $V' = V \cap T$. The set $U' \cup V'$ is
independent since there are no infinite capacity edges crossing the
cut. The size of the cut is $|U - U'| + |V - V'| = |U| + |V| - |U' \cup V'|$. This, in order to make the independent set as large as
possible, we make the cut as small as possible.

So lets take this as the graph:

A - B - C
    |
D - E - F

We can split this into a bipartite graph as follows
$(U,V)=(\{A,C,E\},\{B,D,F\})$

We can see by brute force search that the sole Maximum Independent Set is $A,C,D,F$. Lets try and work through the solution above:

So the constructed flow network adjacency matrix would be:

$$\begin{matrix}
& s & t & A & B & C & D & E & F \\
s & 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
t & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\
A & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
B & 0 & 1 & \infty & 0 & \infty & 0 & \infty & 0 \\
C & 1 & 0 & 0 & \infty & 0 & 0 & 0 & 0 \\
D & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
E & 1 & 0 & 0 & \infty & 0 & \infty & 0 & \infty \\
F & 0 & 1 & 0 & 0 & 0 & 0 & \infty & 0 \\
\end{matrix}$$

Here is where I am stuck, the smallest finite capacity cut I see is a trivial one: $(S,T) =

The complement of a maximum independent set is a minimum vertex cover.

To find a minimum vertex cover in a bipartite graph, see König's theorem.

StackExchange Computer Science Q#3027, answer score: 15