# Analysis of a randomized algorithm for independent set construction

Suppose that $$G = (V,E)$$ is a 3-regular graph on $$n$$ vertices and $$m$$ edges. Below I propose a randomized algorithm for obtaining an independent set for $$G$$.

Step $$1$$: Delete each vertex (independently) with $$\frac{2}{3}$$ probability.

Step $$2$$: For each remaining edge, delete one of its endvertices.

I want to upper bound the probability that this $$2$$-step algorithm yields an independent set of size smaller than $$\frac{n(1-\varepsilon)}{6}$$, where $$0 < \varepsilon \leq 1$$. My partial attempt is below.

Let $$X_1, X_2, \dots, X_n$$ be independent Poisson trials satisfying $$\textbf{Pr}[X_i = 1] = \frac{1}{3}$$. Hence, $$X = \sum_{i=1}^{n} X_i$$ gives us the number of vertices in $$G$$ that survive Step $$1$$, and $$\textbf{E}[X] = \frac{n}{3}$$.

Let $$Y_1, Y_2, \dots, Y_m$$ likewise be independent Poisson trials satisfying $$\textbf{Pr}[Y_i = 1] = \frac{1}{9}$$. Hence, $$Y = \sum_{i=1}^{m} Y_i$$ gives us the number of edges in $$G$$ that survive Step $$1$$, and $$\textbf{E}[Y] = \frac{n}{6}$$.

Thus, $$X-Y$$ gives us the minimum number of vertices remaining after the algorithm terminates.

Now, the following Chernoff bound seems especially pertinent to this problem, where $$Z$$ is a sum of independent Poisson trials, $$\mu$$ is its expectation, and $$0 < \delta \leq 1$$:

$$\textbf{Pr}[Z < (1 - \delta)\mu] < \exp(\frac{-\mu \delta^2}{2})$$

Of course, $$X-Y$$ is a lower bound on the size of the output independent set, but I'm not sure how I can apply the expression to the Chernoff bound. Can $$X-Y$$ can be conceived as a sum of Poisson indicator variables, which would be required if I wanted to put $$X-Y$$ in place of $$Z$$ in the above bound? If so, then it seems to me that I can use this Chernoff bound to derive an upper bound on the probability that the minimum size of the output independent set is smaller than $$\frac{n(1-\varepsilon)}{6}$$. How can I get from this to my objective: an upper bound on the probability that the actual size of the output independent set is smaller than $$\frac{n(1-\varepsilon)}{6}$$?

• You seem to propose a solution and wait for comments. That's not what this platform works well for. What is your question, exactly? – Raphael Oct 24 '16 at 22:45
• @Raphael I've edited the main body of the post to make my questions more explicit. – user95224 Oct 24 '16 at 23:17
• @NP-hard Each edge is not deleted with probability $\frac{1}{9}$. Hence, the expected number of not-deleted edges is $\frac{3n}{2} \cdot \frac{1}{9} = \frac{n}{6}$. – David Smith Oct 25 '16 at 5:18
• @DavidSmith Thanks. I just notice that the graph is $3$-regular. – PSPACEhard Oct 25 '16 at 5:23
• I am trying to lower bound the number of vertices that survive the 2-step algorithm. In particular, $X-Y$ is the minimum number of vertices surviving the algorithm, and hence the minimum size of the output independent set. But I think that the upper limit of the sum should be $m$. – user95224 Oct 25 '16 at 5:23

You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then \begin{align} \small \Pr\left[Z \leq \frac{n(1 - \epsilon)}{6}\right] \leq&~\small\Pr\left[X - Y \leq \frac{n(1 - \epsilon)}{6}\right] \\ =&~\small\Pr\left[n - (X - Y) \geq n - \frac{n(1-\epsilon)}{6}\right] \\ =&~\small\Pr\left[n - (X - Y) \geq \frac{(5 + \epsilon)n}{6}\right] \\ \leq&~\small \frac{5n / 6}{(5 + \epsilon) n/ 6} = \frac{5}{5 + \epsilon} \end{align} where the last inequality is by Markov inequality and $\small \mathbb{E}[n - (X - Y)] = \frac{5n}{6}$.
Though the bound is weak, we can reduce it by repeating your algorithm multiple times (e.g., $\small \ell$) and then selecting the independent set with maximum size. The probability that the resultant size is still smaller than $\small \frac{n(1- \epsilon)}{6}$ then is at most $\small \left(\frac{5}{5+\epsilon}\right)^\ell$.
• @user95224 It is because $\small X - Y \leq Z$. – PSPACEhard Oct 25 '16 at 6:51