Edmonds-Karp Algorithm for a graph which has nodes with flow capacities

Question

I am implementing this algorithm for a directed graph. But the interesting thing about this graph nodes have also their own flow capacities. I think, this subtle change of the original problem must be handled in a special way. Because, In original max-flow problem It was okay to find any path from start to finish(actually, in Edmonds-Karp algorithm, we need to do BFS, and choose the first path that reaches the final node) But with this node-capacity extension, we need to be more careful about 'this path selection' job. I know it because, I implemented the original-algorithm and found myself getting smaller flow values than max-flow, I doubt that it has to do with this node-capacity restrictions.

I put a lot effort on this and came up with some ideas like transforming the initial graph into a graph which has no capacity constraint on nodes by adding self loops (adding self loops to each node and finding paths which includes this self-loops for each node on the path) or adding virtual nodes and edges whose weights supersede the initial node-capacity constraints) However, I am not convinced that any of these are nice solution for this problem.

Any idea would be much appreciated.

Thanks in advance.

Decemvir

Answer 1

There's a simple reduction from the max-flow problem with node capacities to a regular max-flow problem:

For every vertex v in your graph, replace with two vertices v_in and v_out. Every incoming edge to v should point to v_in and every outgoing edge from v should point from v_out. Then create one additional edge from v_in to v_out with capacity c_v, the capacity of vertex v.

So you just run Edmunds-Karp on the transformed graph.

So let's say you have the following graph in your problem (vertex v has capacity 2):

s --> v --> t
   1  2  1

This would correspond to this graph in the max-flow problem:

s --> v_in --> v_out --> t
   1        2         1

It should be apparent that the max-flow obtained is the solution (and it's not particularly difficult to prove either).

Executioner

I know it has not much to do with my initial question but I am tempted to know whether there is such a reduction by which we handle cycles in a graph before using Edmonds-Karp algorithm. Because cycles somehow change the max-flow if they are not handled properly. I think, it can be a reduction the one like you mentioned. we can have a vertex-couple, say cycle_in and cycle_out, instead of all vertices in that cycle and we can replace every incoming and outgoing edge from a vertex in cycle with an edge with same capacity from cycle_in and cycle_out correspondingly. Would it be OK? – Decemvir

I forgot to tell about the capacity of (cycle_in, cycle_out) edge. It must be minimum of the all old edge and node capacities. But, I have a feeling in my guts that this is a wrong construction for a max-flow problem for a cyclic graph. – Decemvir