For a flow network G = (V, E) with specified s, t 2 V and capacities c_e > 0 for e E, you are given a flow f (you are given f_efor every e E).

Note: For both parts, faster and correct is worth more credit. And if youre algorithm takes the same time as computing a max-flow from scratch then youll get 0 points.

Part (a): Explain an algorithm to verify/check whether or not f is a valid flow. Be sure to state and explain the running time of your algorithm.

Part (b): It is claimed that f is a maximum flow. Explain an algorithm to verify/check whether or not f is a maximum flow. Be sure to state and explain the running time of your algorithm.