Deje $G = (V, E)$ un gráfico. Un 'dominante set' $W ⊆ V$es un conjunto de nodos, de modo que para cada nodo $v \in V$ sostiene que cualquiera de las $v$ o en el de un vecino de $v$ está contenido en $W$. Suponga que $G$ tiene grado mínimo, al menos, $d > 1$, es decir, cada nodo $v \in V$ tiene el grado $deg(v) ≥ d$.
El algoritmo consta de dos rondas. En la primera ronda que marca cada uno de los nodos de forma independiente de los otros nodos con una probabilidad de $p$. En la segunda ronda nos fijamos en cada nodo $v \in V$ si no $v$ ni ninguno de sus vecinos fueron marcados en la primera vuelta, marcamos $v$ .
Deje $X$ el número de nudos marcados en la primera ronda. Por lo $E(X) = |V|*p$, debido a $X \sim Bin(|V|,p)$, ¿verdad ?
Deje $v ∈ V $ninguna (pero fijo) del nodo. Si piensa que la probabilidad de que ni v ni uno de los vecinos de v se marcó en la primera ronda se $(1-p)^{deg(v)}$ derecho ? Pero, ¿cómo puedo finde un límite superior que es sólo dependiente de $d$ e $p$ (y no de $v$).
Deje $Y$ el número de nudos marcados en la segunda ronda. ¿Cómo puedo finde un límite superior para $E(Y)$.
