(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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.