I have an unweighted, undirected graph G=(V,E) from which I am sampling a set S of $\frac{kn}{ε^2}$ edges uniformly at random, where k is constant and ε is a variable parameter. From this set S I want to find an estimate of the value of the max cut (A,B) of G, defined as $|(A×B)∩E|$. In particular I must show that if I compute: $$|(A×B)∩S|·\frac{|E|}{|S|}$$ I can obtain an estimate that is within (1±ε) the value of the max cut (A,B) of G. Now, I am quite confused on how to approach this. I guess I should first compute the expected value of $|(A×B)∩S|$, but I am not really sure how to do it. Any suggestion or reference would be much appreciated.

EDIT: a further related question following the answer below. Consider another cut $(C,D)$ in G, which is not the max cut. Its estimated value will similarly be: $$|(C×D)∩S|·\frac{|E|}{|S|}$$ What is the probability that this value is greater than $|(C×D)∩E|+ε·|(A×B)∩E|$? In this case I would answer that this probability is $\le\frac{1}{kn}$ because I can apply the Chebyshev's inequality (or a different one, such as Chernoff) to show that for the cut $(C,D)$ it is also true that: $$Pr[|μ¯−μ|≥ϵμ]\le\frac{1}{kn}$$ which means that the probability that: $$|(C×D)∩S|·\frac{|E|}{|S|} \gt (1+ε)|(C×D)∩E| $$ is $\le\frac{1}{kn}$, i.e. quite small. And since: $$(1+ε)|(C×D)∩E| \le [|(C×D)∩E|+ε·|(A×B)∩E|]$$ the same probability applies. Is this a wrong approach?


It is an application of concentration inequality. For $1 \leq i \leq |S|$, define random variable $$ X_i = \begin{cases} 1 & \text{if the $i$-th edge in $S$ belongs to the max cut $(A, B)$} \\ 0 & \text{otherwise} \end{cases} $$ Then, we have $$ \Pr[X_i = 1] = \frac{|(A \times B) \cap E|} {|E|} \tag{$1$} $$ and $$ X_1 + X_2 + \cdots + X_{|S|} = |(A \times B) \cap S| \tag{$2$} $$ Denote by $\mu = \frac{|(A \times B) \cap E|}{|E|}$ the ratio of the # of edges in the max cut to $|E|$ and by $\bar{\mu} = \frac{|(A\times B) \cap S|}{|S|}$ an estimation of $\mu$. We have \begin{align} \mathsf{E}[\bar\mu]\ =\ &\mathsf{E}\left[\frac{|(A \times B) \cap S| }{|S|}\right] \\ {\small\text{(by Eq. $(2)$)}}\quad=\ &\frac{1}{|S|} \cdot \mathsf{E}[X_1 + \cdots + X_{|S|}] \\ {\small\text{(by linearity of expectation and Eq. $(1)$)}}\quad=\ &\frac{1}{|S|}\cdot |S| \cdot \frac{|(A \times B) \cap E|}{|E|} \\ =\ &\frac{|(A \times B) \cap E|}{|E|} = \mu \end{align} That is, $\bar{\mu}$ is an unbiased estimator of $\mu$. Further, we have $$ \mathsf{Var}[\bar\mu] = \frac{1}{|S|^2} \mathsf{Var}(|(A \times B) \cap S|) = \frac{1}{|S|^2}\mathsf{Var}(X_1 + \cdots + X_{|S|}) = \frac{1}{|S|} \mathsf{Var}(X_1) \leq \frac{1}{4|S|} \tag{$3$} $$ By the Chebyshev's inequality and the fact that a max cut has at least $|E| / 2$ edges (i.e., $\mu \geq \frac{1}{2}$), $$ \Pr[|\bar\mu - \mu| \geq \epsilon \mu] \leq \frac{\mathsf{Var}[\bar\mu]}{\epsilon^2 \mu^2} \leq \frac{1}{4|S|\cdot \epsilon^2 \cdot (1/2)^2} = \frac{1}{kn} $$ In other words, the event that $( 1- \epsilon)\mu \leq \bar\mu \leq ( 1 + \epsilon) \mu$ holds with probability at least $1 - \frac{1}{n}$ when $k = 1$. By multiplying $\mu$ and $\bar\mu$ simultaneously by $|E|$, you will get the result you want.

  • $\begingroup$ That's a great explanation! I also added a further related problem (see the EDIT). $\endgroup$ – Gianluca John Massimiani Dec 27 '17 at 16:31
  • $\begingroup$ @GianlucaJohnMassimiani By convention, it is better to post your second question as a new question in math.stackexchange. As to your second question, it is not valid because my derivation above is based on the fact that a max cut has at least $|E| / 2$ edges, but this may be not the case for $(C, D)$. However, you can obtain the same conclusion as follows. $\endgroup$ – PSPACEhard Dec 28 '17 at 2:27
  • $\begingroup$ @GianlucaJohnMassimiani Let $$\bar\mu = \frac{|(C \times D) \cap S|}{|S|},\quad \mu = \frac{|(C \times D) \cap E|}{|E|}$$ and $$\eta = \frac{|(A \times B) \cap E|}{|E|}$$ We have by Chebyshev's inequality, $$\Pr[|\bar\mu - \mu| \geq \epsilon \eta] \leq \frac{\mathsf{Var}[\bar\mu]}{\epsilon^2\eta^2} \leq \frac{1}{4|S| \cdot \epsilon^2 \cdot (1 / 2)^2} = \frac{1}{kn}$$ $\endgroup$ – PSPACEhard Dec 28 '17 at 2:30

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.