Question

1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1. Initialize S to be the empty set 2. For every vertex v in V: 3. Put v into S with probability 1/2 4. Let T = V\S be the complement of S 5. Output (S,T) Recall that E(S, T) CE is the set of edges that have one endpoint in S and the other endpoint in T, ie., E(S, T) = {(u, u) : x S, u E T). The size of the cut is | E(S, T)1. (a) Show that the above algorithm is a 1/2-approximation in expectation for MAX-CUT That is, the expected size of the output cut is at least half the size of a maximum cut. Hint: use linearity of expectation to show that in expectation, half of the edges in the entire graph are in E(S, T).) (b) Argue that, for any graph G-(V, E), there exists a cut of size at least E1/2.

Answer 1

Answer:
(disjoint) sets A and B (i.e. AUB-V and AnB-Ø)such that the number of edges with one endpoint in A and the other in B is maximized. In other words, we are looking for the maximum cut (A, B) of the graph Consider the following algorithm. We start with an arbitrary partition (A, B). If there exists a vertex v E V such that moving it to the other set in the partition increases the number of edges in the cut, do so. Proceed until there is no such vertex (a) Show that the algorithm stops (b) Show that when the algorithm stops, the size of the cut is at least half of the optimum Consider the neighbors of each vertex after the algorithm stops 1. After each iteration, the number of edges in the cut increases by at least one. Obviously E is upper bound on the number of cutting edges. Thus the algorithm will stop after at most |E steps 2. Suppose the algorithm terminates and gives us a cut (A, B). For each vertex vEV, denote d(v) as the degree of v. Moreover, denote dr(v) as the number of edges of the form (v, u) such that u is in the same partition of v. Similarly denote de(v) as the number of the edges of the form (v, u) such that u is in the different partition from v. Obviously d(v) - di(v) + dE(v) When the algorithm terminates, we have de(v) 2 di(v) for all v EV. Otherwise we can move some v to the other partition to give a larger cut. Denote OPT as the optimal cut and C as the cut given by the algorithm. Then vEV VEV