Maximum Independent Set of a Bipartite Graph

Question Detail: 

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) =(\{s\},\{t,A,B,C,D,E,F\})$ with a capacity of 3.

Using this cut leads to an incorrect solution of:

$$ U' = U \cap S = \{\}$$ $$ V' = V \cap T = \{B,D,F\}$$ $$ U' \cup V' = \{B,D,F\}$$

Whereas we expected $U' \cup V' = \{A,C,D,F\}$? Can anyone spot where I have gone wrong in my reasoning/working?

Asked By : Andrew Tomazos

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/3027

Answered By : Jukka Suomela

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.