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
