4
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ You seem to propose a solution and wait for comments. That's not what this platform works well for. What is your question, exactly? $\endgroup$ – Raphael Oct 24 '16 at 22:45
  • $\begingroup$ @Raphael I've edited the main body of the post to make my questions more explicit. $\endgroup$ – user95224 Oct 24 '16 at 23:17
  • $\begingroup$ @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}$. $\endgroup$ – David Smith Oct 25 '16 at 5:18
  • $\begingroup$ @DavidSmith Thanks. I just notice that the graph is $3$-regular. $\endgroup$ – PSPACEhard Oct 25 '16 at 5:23
  • $\begingroup$ 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$. $\endgroup$ – user95224 Oct 25 '16 at 5:23
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Why does the first inequality hold? $\endgroup$ – user95224 Oct 25 '16 at 6:48
  • 1
    $\begingroup$ @user95224 It is because $\small X - Y \leq Z$. $\endgroup$ – PSPACEhard Oct 25 '16 at 6:51

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.