Let G = (V, E) be an undirected graph. For any subset A, BCV, let C(A, B) denote the set of edges between A and B, i.e., C(A, B) = {e EE e connects some vertex in A and some vertex in B}. Note that, C(A, B) is also called the cut edges between A and B. In the cardinality maximum cut problem, the goal is to compute a partition of V into two sets S and S such that the cardinality of C(A, B) is maximized. . (10%) Consider the following randomized algorithm for max-cut. 1. For each v V, pick x, {0, 1} independently and uniformly at random. Let S = {v V: x = 0} and S := V - So. 2. Output (S0, S1). Prove that, for any e E, Pr[e C(S0, S)] = 1/2 and establish that C(S0, S) is a randomized (1/2)-approximation for the max-cut problem, i.e., the expected number of edges in C(S0, S) is at least one-half of the number in any optimal cut. Activate Windo Settings to