Suppose we are given a graph G = (V,E) and we want to color each vertex...

  

Transcribed Image Text:

Suppose we are given a graph G = (V,E) and we want to color each vertex with one of three colors, say red,green, blue. Given a coloring of the vertices in V, we say that an edge e = {u, v} is satisfied if the colors assigned to u and u are different. For this question, we used the term coloring to mean a coloring of the vertices of V. Consider the following randomized algorithm for coloring the vertices of V for an input graph G = (V,E). Algorithm 1: Algorithm for Question 1 Input Graph G = (V,E) Output: A coloring of the vertices of V 1 foreach vЄ V do 2 3 4 end Select a color c uniformly at random from the set red, green, blue Color vertex v with the color c 5 return The computed coloring of V Basically, the algorithm uniformly at random assigns one of three colors to each vertex independently and returns that coloring. Recall that uniformly at random means that each color is picked with probability 1/3. Answer the following questions: a. Compute the probability that an arbitrary edge e = {u, v} = E is satisfied by a coloring computed by the randomized algorithm. That is, what is the probability that u, v are assigned different colors by the algorithm? b. Compute the expected number of edges satisfied by a coloring returned by the algorithm. That is, if X is a random variable representing the number of edges satisfied by a coloring returned by the algorithm, compute E[X], the expectation of X. c. For the graph given in Figure 1 below, is it possible to color the vertices using colors red, green, blue so that every edge is satisfied by the coloring? If yes, give one such coloring. If no, explain why not. 2 ст 5 1 4 3 6 Suppose we are given a graph G = (V,E) and we want to color each vertex with one of three colors, say red,green, blue. Given a coloring of the vertices in V, we say that an edge e = {u, v} is satisfied if the colors assigned to u and u are different. For this question, we used the term coloring to mean a coloring of the vertices of V. Consider the following randomized algorithm for coloring the vertices of V for an input graph G = (V,E). Algorithm 1: Algorithm for Question 1 Input Graph G = (V,E) Output: A coloring of the vertices of V 1 foreach vЄ V do 2 3 4 end Select a color c uniformly at random from the set red, green, blue Color vertex v with the color c 5 return The computed coloring of V Basically, the algorithm uniformly at random assigns one of three colors to each vertex independently and returns that coloring. Recall that uniformly at random means that each color is picked with probability 1/3. Answer the following questions: a. Compute the probability that an arbitrary edge e = {u, v} = E is satisfied by a coloring computed by the randomized algorithm. That is, what is the probability that u, v are assigned different colors by the algorithm? b. Compute the expected number of edges satisfied by a coloring returned by the algorithm. That is, if X is a random variable representing the number of edges satisfied by a coloring returned by the algorithm, compute E[X], the expectation of X. c. For the graph given in Figure 1 below, is it possible to color the vertices using colors red, green, blue so that every edge is satisfied by the coloring? If yes, give one such coloring. If no, explain why not. 2 ст 5 1 4 3 6