19
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ (S,T) = ( {s,A,B,C}, {t,D,E,F} ) has capacity 2 $\endgroup$ – user2424 Aug 9 '12 at 0:58
  • 1
    $\begingroup$ @Brian there is an infinite capacity edge from B to E across your cut, so it is infinite capacity. $\endgroup$ – Andrew Tomazos Aug 9 '12 at 4:26
  • $\begingroup$ if i understand this correctly, based on the brute force solution, you need a cut where S contains A and C and T contains D and F, which makes your cut be {s, A, C}, {t, D, F}. Now, how do you construct the cut ? $\endgroup$ – njzk2 Jan 9 '13 at 17:27
  • $\begingroup$ also, this looks like the Ford-Fulkerson, in which edges have a capacity of one. $\endgroup$ – njzk2 Jan 9 '13 at 20:18
  • $\begingroup$ Look up the Hungarian algorithm. $\endgroup$ – Patrik Vörös Dec 4 '17 at 16:48
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This (maybe) solves the problem but does not answer the question. $\endgroup$ – Raphael Aug 4 '12 at 9:45
  • 2
    $\begingroup$ @Raphael: I agree if you remove the word "maybe". :) $\endgroup$ – Jukka Suomela Aug 4 '12 at 10:52
  • 1
    $\begingroup$ Oh, I am sure it solves the problem, but I am not sure whether it helps Andrew solve his problem. $\endgroup$ – Raphael Aug 4 '12 at 11:35
  • 3
    $\begingroup$ I solved it as you suggest: HopcroftKarp -> maximal matching -> Konigs Thereom -> Minimum Vertex Cover -> Complement -> Maximum Independent Set. I'd still like to know why the flow method described in my question doesn't seem to work. $\endgroup$ – Andrew Tomazos Aug 8 '12 at 1:58
5
$\begingroup$

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:

Graph

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I agree with you, but could you please add more details, for example, a complete correctness proof of the flow algorithm, and how the algorithm applies on the OP's example? $\endgroup$ – xskxzr Jun 10 at 17:48
  • $\begingroup$ The note in this does have a short proof of correctness. cs.washington.edu/education/courses/cse521/01sp/flownotes.pdf For the example, if you look at the figure by Evgeni Sergeev above, the edges should all be directed downwards. Then the only two edges out of S is (s,e) and (b,t), the bolded red edge is going into S and should not be counted in the cut value. $\endgroup$ – yu25x Jun 15 at 18:03
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Are you sure? Cuts are usually on capacities and, in any case, we already know that the minimum cut is finite so cuts being infinite doesn't seem to be the problem. $\endgroup$ – David Richerby Apr 26 '16 at 15:23
0
$\begingroup$

I think that you don't need to connect the edges both ways even if the original graph was undirected. Because for the flow network, you need a directed graph, you could consider only the edges from $U$ to $V$.

Then in this new graph $G'$, you will have a min-cut of 2, which gives you the answer $\{A,C,D,F\}$.

New contributor
Ajit Kumar is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.