1. (a) Suppose that after solving a maximum flow problem you realize that you have underestimated the capacity of an arc (p, q) by k units. Show that the labeling algorithm can reoptimize the problem in O(km) time.
(b) Suppose that instead of underestimating the capacity of the arc (p, q), you had overestimated its capacity by k units. Can you reoptimize the problem in O(km) time? .
2. (a) Construct a family of networks with the number of s-t cuts growing exponentially with n.
(b) Construct a family of networks with the number of minimum cuts growing exponentially with n.