CODEWITHSUNDEEP
algorithmgraphbipartitemax-flow
gautamk
gautamk

Reputation: 15

Error in an approach to Maximum Bipartite matching

A bipartite graph with a source and sink is given as shown below. The capacity of every edge is 1 unit : Source : GeeksforGeeks

I'm trying to find the maximum flow from source to sink. One approach would be using the Ford-Fulkerson Algorithm for Maximum Flow Problem, which is applicable to all the graphs. I found a simple approach to find the maximum flow(too simple to be correct!) and I'm not able to find any error in the approach.

Approach :

c1 = Count the number of vertices having non zero number of edges originating from it ,in the list of vertices having outgoing edges.

c2 = Count the number of vertices having non zero number of edges converging into it ,in the list of vertices having incoming edges.

The max flow would be the minimum of both these numbers,i.e., min(c1,c2).[Since any path needs one vertex from the outgoing vertices list, and other from incoming vertices list.]

Any help would be appreciated.

Upvotes: 0

Views: 212

Answers (2)

David Eisenstat
David Eisenstat

Reputation: 65458

Consider a graph like

*--*
  /
 /
*  *
  /
 /
*--*

(The patch of working by connected component doesn't fix things; connect the lower left to the upper right.)

Upvotes: 1

hjohanns
hjohanns

Reputation: 96

Don't have an exact answer, but I have an iterative algorithm that works. To me you clearly need to equilibrate the flow, so that it is distributed among the left vertices that can send it to the right vertices that can receive it. Suppose you model your situation with a matrix A containing the bipartite links. You can then assume that if your matrix contains exactly the amount of flow (between 0 and 1) you want to pass in an edge, then the total flow given this decision is b=A*a where a is a vector of ones. If you start with the maximum capacity for A, putting all the edges at one and all the others at 0, you might have some elements of b with more than 1, but you can reduce their corresponding elements of A so they pass less flow. Then you can revert the flow and see what is the maximum reception capacity of your bipartite part, and test it with a=A'b. Again you might have elements of a that are more than 1 meaning that an ideal flow would be greater than the possible capacity from source to the element, and reduce these elements in the flow of A. With this ping-pong algorithm and reducing the corrections progressively, you are guaranteed to converge on the optimal matrix. Given a final b=Aa with a vector of ones, your maximal flow will be sum(b). See the octave code below, I use B as the converging matrix, and let me know your comments.

A=[0 1 0 1;1 0 0 1;1 1 0 0;0 0 1 0];
B=A;
repeat
  b=B*ones(4,1);
  B=B.*([.8 .8 .8 1]'*ones(1,4));
  a=B'*ones(4,1)
  B=B.*(ones(4,1)*[.9 .9 1 .9]);
until converge
maxflow=sum(b)

Upvotes: 0

Related Questions