26-4 Updating maximum flow

Let \(G = (V, E)\) be a flow network with source \(s\), sink \(t\), and integer capacities. Suppose that we are given a maximum flow in \(G\).

a. Suppose that we increase the capacity of a single edge \((u, v) \in E\) by \(1\). Give an \(O(V + E)\)-time algorithm to update the maximum flow.

b. Suppose that we decrease the capacity of a single edge \((u, v) \in E\) by \(1\). Give an \(O(V + E)\)-time algorithm to update the maximum flow.

a. If there exists a minimum cut on which \((u, v)\) doesn't lie then the maximum flow can't be increased, so there will exist no augmenting path in the residual network. Otherwise it does cross a minimum cut, and we can possibly increase the flow by \(1\). Perform one iteration of Ford-Fulkerson. If there exists an augmenting path, it will be found and increased on this iteration. Since the edge capacities are integers, the flow values are all integral. Since flow strictly increases, and by an integral amount each time, a single iteration of the while loop of line 3 of Ford-Fulkerson will increase the flow by \(1\), which we know to be maximal. To find an augmenting path we use a BFS, which runs in \(O(V + E') = O(V + E)\).

b. If the edge's flow was already at least \(1\) below capacity then nothing changes. Otherwise, find a path from \(s\) to \(t\) which contains \((u, v)\) using BFS in \(O(V + E)\). Decrease the flow of every edge on that path by \(1\). This decreases total flow by \(1\). Then run one iteration of the while loop of Ford-Fulkerson in \(O(V + E)\). By the argument given in part a, everything is integer valued and flow strictly increases, so we will either find no augmenting path, or will increase the flow by \(1\) and then terminate. "

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用