5
$\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$
6
  • $\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, 2016 at 22:45
  • $\begingroup$ @Raphael I've edited the main body of the post to make my questions more explicit. $\endgroup$
    – user95224
    Oct 24, 2016 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$ Oct 25, 2016 at 5:18
  • $\begingroup$ @DavidSmith Thanks. I just notice that the graph is $3$-regular. $\endgroup$
    – PSPACEhard
    Oct 25, 2016 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, 2016 at 5:23

1 Answer 1

4
$\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$
2
  • $\begingroup$ Why does the first inequality hold? $\endgroup$
    – user95224
    Oct 25, 2016 at 6:48
  • 1
    $\begingroup$ @user95224 It is because $\small X - Y \leq Z$. $\endgroup$
    – PSPACEhard
    Oct 25, 2016 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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