CODEWITHSUNDEEP
algorithmgraph-theory
Saucy Goat
Saucy Goat

Reputation: 1675

Identify edges that increase maximum flow in a graph

I have to find the maximum flow of a graph and then identify the edges such that if their capacity is increased, the maximum flow of the graph increases.

I have successfully found the maximum flow by applying a Relabel-To-Front algorithm but can't seem to think of a way to find out what edges have the potential to increase the maximum flow.

Thank you in advance.

Upvotes: 1

Views: 2824

Answers (1)

m.raynal
m.raynal

Reputation: 3143

You can find such edges by solving the dual problem of the max-flow problem: the min-cut problem.
A consequence of the max-flow min-cut theorem is that the edges forming a min-cut on your graph are actually the saturated edges in a max-flow.
So if there are edges that may increase the max-flow in a graph, they are part of a min-cut.
But there is no guarantee that there exists an edge in your graph such that increasing the flow of this edge would lead to a greater flow. In some cases, you would need to increase the capacity of all edges of the graph in order to increase the max-flow.

A way to test that is to compute the min-cut, then try and increase the capacity on one or several edges of this min-cut, and recompute the flow to compare to its previous value.

Upvotes: 2

Related Questions