7
$\begingroup$

Let $G = (V, E)$ a graph. A 'dominant set' $W ⊆ V$is a set of nodes, so that for each node $v \in V$ holds that either $v$ itself or a neighbor of $v$ is contained in $W$. Assume that $G$ has minimum degree at least $d > 1$, i.e. each node $v \in V$ has degree $deg(v) ≥ d$.

The algorithm consists of two rounds. In the first round we mark each node independently from the other nodes with probability $p$. In the second round we look at each node $v \in V$ , if neither $v$ nor any of its neighbours were marked in the first lap, we mark $v$ .

Let $X$ be the number of knots marked in the first round. So $E(X) = |V|*p$, because $X \sim Bin(|V|,p)$, right ?

Let $v ∈ V $any (but fixed) node. If think the probability that neither v nor one of the neighbors of v was marked in the first round would be $(1-p)^{deg(v)}$ right ? But how can i finde a upper bound which is only dependent from $d$ and $p$ (and not from $v$).

Let $Y$ be the number of knots marked in the second round. How can i finde a upper bound for $E(Y)$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The probability of being selected in the second round is $(1-p)^{\text{deg}(v)\color{red}{+1}}$.

Use the fact that $\deg v \ge d$ to conclude that $(1-p)^{\deg v+1}\le (1-p)^{d+1}$. Then $EY\le |V|(1-p)^{d+1}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .