This question is from the textbook Algorithm Design 1st edition by Jon Kleinberg , Chapter 7 Problem 23E

2. (10 marks) Suppose you're looking at a flow network G with source s and sink t, and you want to express the intuition that some nodes are clearly on the source side" of the main bottlenecks; some nodes are clearly on the "sink side" of the main bottlenecks; and some nodes are in the middle However, G can have many minimum cuts, so we have to be careful in how we make this idea precise . We say a node v is upstream if, for all minimum s, t-cuts (A, B), we have v E A-that is, v lies on the source side of every minimum cut. . We say a node v is downstream if, for all minimum s,t-cuts (A, B), we have v E B-that is, v lies on the sink side of every minimum cut. We say a node is central if it is neither upstream nor downstream; i.e., there is at least one minimum s,t-cut (A, B) for which v E A, and at least one minimum cut (A*, B) for which U E B Give an algorithm that takes a flow network G and classifies each of its nodes as either upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow. You should carefully explain why your algorithm works. 2. (10 marks) Suppose you're looking at a flow network G with source s and sink t, and you want to express the intuition that some nodes are clearly on the source side" of the main bottlenecks; some nodes are clearly on the "sink side" of the main bottlenecks; and some nodes are in the middle However, G can have many minimum cuts, so we have to be careful in how we make this idea precise . We say a node v is upstream if, for all minimum s, t-cuts (A, B), we have v E A-that is, v lies on the source side of every minimum cut. . We say a node v is downstream if, for all minimum s,t-cuts (A, B), we have v E B-that is, v lies on the sink side of every minimum cut. We say a node is central if it is neither upstream nor downstream; i.e., there is at least one minimum s,t-cut (A, B) for which v E A, and at least one minimum cut (A*, B) for which U E B Give an algorithm that takes a flow network G and classifies each of its nodes as either upstream, downstream, or central. The running time of your algorithm should be within a constant factor of the time required to compute a single maximum flow. You should carefully explain why your algorithm works