Consider an undirected graph G = (V, E). An independent set is a subset I ⊂ V such that for any vertices i, j ∈ I, there
Posted: Fri May 06, 2022 6:48 am
Consider an undirected graph G = (V, E). An independent set is a
subset I ⊂ V such that for any vertices i, j ∈ I, there is no edge
between i and j 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 sent is not
necessarily the largest independent set in G. Let α(G) denote the
size of the largest maximal independent set in G.
One way of trying to avoid this dependence on ordering is the
use of randomized algorithms. Essentially, by processing the
vertices in a random order, you can potentially avoid (with 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 this second step, deleting one vertex from I may
remove multiple edges from I!
• Return the final set I.
1) Argue that the expected number of vertices in I after Step 1
is p|V |.
2) Argue that the expected number of edges in I after Step 1 is
p 2 |E|.
3) Argue that the expected size of I after Step 2 is greater
than or equal to p|V |−p^2 |E|.
subset I ⊂ V such that for any vertices i, j ∈ I, there is no edge
between i and j 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 sent is not
necessarily the largest independent set in G. Let α(G) denote the
size of the largest maximal independent set in G.
One way of trying to avoid this dependence on ordering is the
use of randomized algorithms. Essentially, by processing the
vertices in a random order, you can potentially avoid (with 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 this second step, deleting one vertex from I may
remove multiple edges from I!
• Return the final set I.
1) Argue that the expected number of vertices in I after Step 1
is p|V |.
2) Argue that the expected number of edges in I after Step 1 is
p 2 |E|.
3) Argue that the expected size of I after Step 2 is greater
than or equal to p|V |−p^2 |E|.