For problems that require you to provide an algorithm, you must give the

following:

1. a precise description of the algorithm in English and, if helpful, pseudocode,

2. a proof of correctness,

3. an analysis of running time and space.

2. Let G (V, E) be a directed graph with s, t e V and positive edge capacities. We call an edge a flow-stopper if its deletion would shrink the maximum flow from s to t. (a) Prove or disprove the following statements: i. If e is a flow-stopper, then there is a minimum s-t cut that it crosses ii. If we can find a minimum s-t cut that e crosses, then we know e is a flow-stopper (b) Design an alogrithm that takes in a graph G (with all of the properites above), a max s-t flow f for G, and an edge e', and decides if e' is a flow-stopper. Your algorithm should have a runtime of O(IE ce'), where cef is the capacity of e'. 2. Let G (V, E) be a directed graph with s, t e V and positive edge capacities. We call an edge a flow-stopper if its deletion would shrink the maximum flow from s to t. (a) Prove or disprove the following statements: i. If e is a flow-stopper, then there is a minimum s-t cut that it crosses ii. If we can find a minimum s-t cut that e crosses, then we know e is a flow-stopper (b) Design an alogrithm that takes in a graph G (with all of the properites above), a max s-t flow f for G, and an edge e', and decides if e' is a flow-stopper. Your algorithm should have a runtime of O(IE ce'), where cef is the capacity of e