While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem. The algorithm states:
For graph G
- create an edge from target to source with infinite capacity
- create two new source S' and target T'
- for every demand d of an edge E we create two edges, one leading from the new source S' to the target node of the edge E and one to the new target T' from the source node of the edge E, both with capacity d. We subtract the capacity d from the capacity of the edge E.
- find a saturating max flow from S' to T' (so all new edges are saturated)
- transform graph back
The problem is, that we can find a saturating flow, even when there is no feasible solution. Let's see the following graph.
It can be transformed to the following graph, then a max flow can be found.
So the result is the cycle saturated with flow 2.
But it is not feasible because of the edges with capacity 1. Why doesn't it work? What to do to repair the algorithm so it would work? I did not see any mentions of this problem in the papers.
