3 Max-Flow and Graph Reliability (35 pts] Let G = (V, E) be a directed graph with two specified vertices st EV. Assume that contains at least one s-t path. A subset of edges E' CE is a separating edge set if, after removing E' from G, no s-t path exists. A subset V CV- {s,t} of vertices is a separating vertex set if, after removing V and all edges connected to V from G, no s-t path exists. Note that if (s, t) & E, a separating vertex set always exists. E' is a smallest separating edge set if it contains the smallest number of edges among all separating edge sets. V' is a smallest separating vertex set if it contains the smallest number of vertices among all separating vertex sets. Note that a smallest separating edge set E' might not be unique. A smallest separating vertex set V also might not be unique. In the graph below {(a, f), (d, 9).(en)} is a smallest separating edge set, but there are others as well. {9, f} and {9,a} are the only smallest sepa- rating vertex sets. a S. 69 dhu Smallest separating sets are indicators of failure points in a network and are therefore used in studies of network reliability. In what follows you may use any facts or algorithms taught in class as long as you explicitly reference them (which means including their statement and where in the class or tutorial notes you found them). (a) Give an O(1E12) time algorithm for finding a smallest separating edge set for G. (b) Assume (s, t) & E. Give an O(VIIE) time algorithm for finding a smallest separating vertex set for G. Both (a) and (b) should contain 3 parts. Part (1) should describe your algorithm clearly (code is not necessary). Part() should prove its correctness. Part (iii) should derive its running time. Your proof of correctness must contain a section that EXPLICITLY justifies why your output is a smallest separating edge or vertex set. Hints, Comments and Recommendations. For (a), consider the algorithm for finding the maximum number of edge disjoint s-t paths taught in class. How can you modify that to solve this problem? Hints. Let S T be ANY S-t cut. Then the set of edges crossing between S, T is a separating edge set. (Prove this) Consider the Min-Cut you get when solving the edge disjoint s-t path problem. The statement above implies that the max number of edge disjoint paths is an upper bound on the size of the smallest separating edge set (why?). Can you show that these two values must be equal?. For (b). modify G to create a new graph G' = (V, E'). (1) For every vertex v EV, create two vertices ve, Vr in V. (i) For every vertex ve V- {s, t}, Create edge (ve, vr) in E! (iii) For every edge (u, w) E, create edge (Un, we) in E'(iv) Remove vertices se and t, from V. Note that if P is an s-t path in G that passes through vertex v, the corresponding path P' in G' is an Sp. te path that passes through edge (ve, vr). . The modified graph G' contains two very different type of edges:=--:E ES {ve, vr): VEV - {s,t}}, {(Ur, ve): (u, v) E E}. A separating vertex set in G corresponds to a separating edge set in G' in which all edges are in E and vice-versa. So solving (b) corresponds to finding a smallest separating edge set in which all edges are in E. The idea is to appropriately modify the algorithm for part (a) to find such a set. . Suppose you assign capacity 1 to all edges in E and capacity 2 to all edges in En Prove that the edges crossing a Min-Cut must all be of type E. (Proving this requires understanding the structure of the min-cut in the proof of the correctness of the Ford-Fulkerson algorithm.). Use the observations above and (a modified version of the result of part (a) to solve (b)