0
$\begingroup$

Suppose that $d > 1$. Define a $d$-dominating set of a graph $G = (V,E)$ to be a set $D \subseteq V$ such that for any $v \in V$, either $v \in D$ or $v$ has $\geq $ $d$ neighbors in $D$. I would like to show that a graph $G$ on $n$ vertices and minimum degree $\delta \geq 150$ contains a $d$-dominating set of size $O(n \ln{\delta}/\delta)$. Here is my current approach.

Consider an arbitrary $p \in [0,1]$. Randomly and independently, select each vertex of $V$ with probability $p$. Say $X$ is the set of all vertices selected. Define $Y_X$ to be the set of all vertices in $V \setminus X$ that have at most $d-1$ neighbors in $X$, so that $X \cup Y_X$ is a $d$-dominating set. The expected value of $X$ is $np$. Further,

Pr[$v \in Y_X$] $\leq (1-p) \cdot \sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta - i} = \sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$.

Hence, the expected value of $|X| + |Y_X|$ is at most $np + n\sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$. Thus, there must exist an $X$ such that $|X| + |Y_X| \leq np + n\sum_{i=0}^{d-1} {\delta \choose i} p^i(1-p)^{\delta + 1 - i}$.

Now, I would like to find a $p$ that minimizes the right-hand side of the above inequality, but the summation expression is very unwieldy, so I'm not sure how to proceed from here.

$\endgroup$
1
  • $\begingroup$ Have you tried using the one-sided Chebyshev inequality to get a simpler expression? (I haven't tried this myself, just a thought.) $\endgroup$
    – saulspatz
    May 2, 2019 at 11:48

1 Answer 1

1
$\begingroup$

You had the right approach but it is true that computing $E[|Y_X|]$ explicitly is difficult. In this case it is appropriate to use the Chernoff bound. With the Chernoff bound we get $Pr(v\in Y_X)\le (1-p)e^{-\delta p(1-\frac{d}{\delta p})^2/2}\le (1-p)e^{-\delta p/3}$ where the second inequality is true for large $\delta$. Then by substituting $p=\frac{3\ln \delta}{\delta}$ we get $Pr(v\in Y_X)\le \frac{1}{\delta}-\frac{3\ln \delta}{\delta^2}$ hence $E[|X|+|Y|]\le \frac{3n\ln \delta}{\delta}+n(\frac{1}{\delta}-\frac{3\ln \delta}{\delta^2})=O(\frac{n\ln\delta}{\delta})$ as desired.

$\endgroup$

You must log in to answer this question.

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