Maximum Independent Set of a Bipartite Graph

Question

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?

Answer 1

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.

Answer 2

The solution given is clearly incorrect, as you demonstrate with the counterexample. Note that the graph U+V is a connected component by the infinite-capacity edges. Therefore every valid cut will have to contain all of A, B, C, D, E, F on the same side.

Trying to trace back where the solution came from: http://www.cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf cites Network Flows, by Ahuja, Magnanti, and Orlin for some of the problems. This book is out of copyright and downloadable from http://archive.org/details/networkflows00ahuj but it doesn't seem to contain this problem and solution (searching for every occurrence of "bipartite").

Note that the explanation paragraph of the solution does not show that the smallest cut of the graph it constructs corresponds to the maximum independent set. It only shows a way to get an independent set.

And yet, you can see what the algorithm is trying to do. Here is what the actual maximum independent set corresponds to in terms of its s,t cut:

The infinite-capacity edge that breaks the algorithm is emphasised.

I'm not sure how to fix the algorithm to what was intended. Maybe the cost of an infinite edge should be zero if it goes backwards (i.e. where it goes from S to T, but crosses from t-side to s-side)? But is it still easy to find the min-cut/max-flow with this nonlinearity? Also, thinking of a way to bridge from @Jukka Suomela's solution to the algorithm from the question, there is a difficulty where we go from the maximum matching to the minimum vertex cover: while finding the maximum matching can be done by a max-flow-like algorithm, how do you recover the minimum vertex cover from it using a flow-like algorithm? As described here, after the maximum matching is found, the edges between U and V become directed to find the minimum vertex cover. So, again, this doesn't show that a simple application of min-cut/max-flow is all it takes to solve this problem.

Answer 3

The given algorithm is correct. The flow network constructed need to be directed, and the value of a $S$-$T$ cut only considers edges going out of the vertex set $S$.

Answer 4

The cut should be on the actual flow, not on the capacities. Since the flow from s is finite, any {S,T} cut will be finite. The rest is a explained above.