# Relaxed minimum dominating set

(I moved this question from cs exchange to here, because it might be more on the topic here)

Let $$G=(V,E)$$ be a directed graph with $$n$$ nodes. For a subset of nodes $$S\subseteq V$$, let $$\mathcal{N}(S,k)$$ denote the directed $$k$$-neighborhood of $$S$$ ($$d_G(u,v)$$ is directed shortest path distance from $$u$$ to $$v$$): $$\mathcal{N}(S,k):=\{u\in V\colon \exists v\in S: d_G(u,v)\le k\}$$

Problem: For a given bound $$B$$, find the minimum cardinality set $$S$$, which dominates all but $$B$$ vertices in $$k$$ steps: $$\min \{|S| \colon S\subseteq V, \; \lvert \mathcal{N}(S,k)\rvert\ge n-B \} \qquad (\star)$$

For $$B=0$$, this is equivalent to minimum dominating set for graph $$G^{(k)}=(V, E^{(k)})$$, in which $$E^{(k)}$$ denotes all the edges in $$E$$, plus their transitive closures up to $$k$$ steps. By adding $$B>0$$, it becomes a relaxed minimum dominating set. Given that for $$k=1$$ and $$B=0$$, this problem becomes a standard minimum dominating set, there is probably no efficient algorithms for this problem. My questions are (answer to any one is highly appreciated):

1. Is an efficient approximation algorithm for some special class of graphs, say bounded out-degree $$\Delta$$ graphs?
2. Is this problem related to the highway dimension? (link)
3. Let $$S(B,k)$$ denote the set of all minimizers for $$(\star)$$. As the value of $$B$$ increases the constraint becomes more relaxed, and the size of the minimizer $$\lvert S(B,k)\rvert$$ must decrease. However, is there some continuity in these sets? In other words, can we find a sequence of sets $$S_1, S_2, \dots$$ respectively belonging to $$S(B=1,k), S(B=2,k), \dots$$, such that $$S_1 \supseteq S_2 \supseteq \dots$$?
4. Here is a real relaxation of this problem: $$\min \sum_{v\in V} x_v,\\ s.t.\; \forall v\in V \; x_v, b_v\in[0,1] , \sum_{(u,v)\in E^{(k)}} x_u \ge 1-b_v,\sum_{v\in V} b_v \le B$$ Since the integral optimal solutions $$x_v^\star,b_v^\star\in\{0,1\}$$ are feasible points here, the optimum should be less than or equal to OPT, and by u.a.r sampling from $$x^\star, b^\star$$ as the minimizers of the real relaxation, we have: $$\tilde b_v \sim \mathcal{B}(n=1,p=b_v^\star),\; \tilde x_v \sim \mathcal{B}(n=1,p=x_v^\star).$$ ($$\mathcal{B}$$: binomial), can we use Chernof bounds on $$\sum_v \tilde b_v$$ snd $$\sum_v \tilde x_u$$ to prove something about the resulting integral solution?