Let's consider an undirected graph G that for any vertices, i, j E I and there is no edge between i and į in E. A set i is a maximal independent set if no additional vertices of V can be added to I...

I. I need help with this discrete math problem (problem 4)!

Extracted text: Let's consider an undirected graph G that for any vertices, i, j E I and there is no edge between i and į in E. A set i is a maximal independent set if no additional vertices of V can be added to I without violating its independence. Note, however, that a maximal independent set is not necessarily the largest independent set in G. Let a(G) denote the size of the largest maximal independent set in G. = (V,E). An independent subset is a subset I cV such


Extracted text: One way of trying to avoid dependence on ordering is the use of randomized algorithms. Essentially, by processing the vertices in a random order, you can potentially avoid (with a high probability) any particularly bad orderings. So, consider the following randomized algorithm for constructing independent sets: First, starting with an empty set I, add each vertex of G to I independently with probability p Next, for any edges with both vertices in I, delete one of the two vertices from I (at random) Note – in the second step, deleting one vertex from I may remove multiple edges from I! Return the final set I 4. Argue that the output of this algorithm is an independent set. Is it a maximal independent set? Explain in 2-3 sentences.