MIT
80
Proof (approximation)
lBasic
idea: in a k-strong component, edges
get sampled with prob. r / k
»original
sampling theorem works
lProblem:
some edges may be in stronger components, sampled less
lInduct
up from strongest components:
»apply
original sampling theorem inside
»then
“freeze” so don’t affect weaker parts