CODEWITHSUNDEEP
algorithmmax-flownetwork-flowford-fulkerson
Hope Karpov
Hope Karpov

Reputation: 1

Decreasing the capacity of an edge in a flow graph

Let G = (V, E) be a flow network with integer capacities. Let e be an edge in E, and let G′ be a flow network that is the same as G except that the capacity of edge e is one lower in G′ than in G. Design and analyze an O(|E| + |V |)-time algorithm that takes as input an integer maximum flow f in G, and computes an integer maximum flow f′ in G′.

My general idea for tackling this problem is that in the residual graph of G, if e is being underutilized, then decreasing its capacity will have no impact on the new maximum flow of G'. However, if it is, then we can perform a DFS/BFS from the sink t to the source s, where the capacity and reverse edge of e is one less than in the original residual graph of G, and if we find an augmenting path, then the maximum flow stays the same at f. Otherwise, if no augmenting path is found, then this means our current state is at maximum flow, hence the maximum flow will be f - 1 since we decreased the flow in the residual graph by 1.

Upvotes: 0

Views: 98

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59368

Your approach is in the right direction, but you should first construct a valid flow in G' by propagating the effect of the reduced edge capacity. This flow will have output at least |f|-1. Then you can search for an augmenting path. If you find one, it's then guaranteed to produce the same output as f.

Upvotes: 0

Mikhail Wong
Mikhail Wong

Reputation: 1

Your approach overlooks the complexity of flow networks; we can have much lower than f - 1 capacity if we decrease the capacity by one on one of the edges

Upvotes: -2

Related Questions