Let $G = (V, E)$ be a graph with vertex set $V$ and edge set $E$. A subset $I$ of $V$ is called an independent set if for any two distinct vertices $u$ and $v$ in $I$, $(u, v)$ is not an edge in $E$.

Let $n$ and $m$ denote the number of vertices and edges in $G$, respectively, and assume that $m ≥ n/2$.

Consider the following algorithm, in which all random choices made are mutually independent:

Algorithm IndepSet(G):

Step 1: Set $H = G$.

Step 2: Let $d = 2m/n$. For each vertex $v$ of $H$, with probability $1−1/d$, delete the vertex $v$, together with its incident edges, from $H$.

Step 3: As long as the graph $H$ contains edges, do the following: Pick an arbitrary edge $(u, v)$ in $H$, and remove the vertex $u$, together with its incident edges, from $H$.

Step 4: Let $I$ be the vertex set of the graph $H$. Return $I$.

• Argue that the set $I$ that is returned by this algorithm is an independent set in G.

Any help appreciated. Have thought of anything even to get the question started over the past 6 hours.


The argument follows from Step 3. You need only to argue that none of the vertices in $I$ are adjacent, but if they were, then you would not have completed Step 3 - "As long as the graph $H$ contains edges..." - which only terminates when $H$ is completely disconnected. Note also that it removes edges by removing vertices (rather than just the edge itself), therefore given vertices $u$ and $v$ in $V(H)$, if $(u,v)$ is not in $E(H)$, it was not in $E(G)$ to begin with.

Therefore for every distinct pair of vertices $u$ and $v$ in $I$, the edge $(u,v)$ is not in $G$, hence $I$ is an independent set.

Note that Step 2 is performing a similar task to Step 3, it just picks some vertices at random, regardless of whether it has an incident edges, but the same argument as above holds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.