(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, privacy policy and cookie policy