We next show a generalized version of our algorithm from section
3. First, the algorithm works for weighted graphs. Second, we allow for different trade-offs between the two dominating sets we compute in the algorithm. Recall that in section
3 we start by computing a partial dominating set
S, and then we add to it additional set
\(S'\) to dominate the rest of the nodes. Previously we just constructed
\(S'\) as the set of all undominated nodes, but we will see in section
4.2 an algorithm that exploits the structure of undominated nodes to get an improved approximation for this part. To get a better approximation for the whole algorithm, we can stop the algorithm for computing a partial dominating set earlier and get an improved approximation for the first part as well. We start by presenting our general scheme, which allows us to get a deterministic algorithm for weighted graphs with the same guarantees obtained in section
3, and then we show a randomized algorithm that can obtain an improved approximation.
4.1 Deterministic algorithm
We again follow the primal-dual method. We associate a packing value \(0 \le x_v\) to each node such that for any node u, the value \(X_u = \sum _{v \in N^{+}_u} x_v \le w_u\). For each node \(v \in V\), let \(\tau _v = \min _{u \in N^{+}_v} w_u\) be the minimum weight of a node that can dominate v.
Before proving this lemma, we illustrate it can be used to derive one of our main results which is presented in the following theorem.
Back to the proof of lemma
11, to bound
\(w_S\), we use observation
10 and orient the edges of
G such that the out-degree of each node is at most
\(\alpha \). The orientation is used only for the analysis. For each node
v, let
\(N^{\textrm{in}}_v\) be the set of incoming neighbors and
\(N^{\textrm{out}}_v\) be the set of outgoing neighbors of
v in this fixed orientation.
Consider the packing values at the end of the algorithm. Note that through the algorithm, we freeze the packing value of a node as soon as it gets dominated. With this, we can write the following for each node
\(u \in S\):
$$\begin{aligned} X_u= & {} \sum _{v \in N^{\textrm{in}}_u} x_v + x_u + \sum _{v' \in N^{\textrm{out}}_u} x_{v'} \ge \frac{w_u}{1 + \varepsilon }\\\Rightarrow & {} \sum _{v \in N^{\textrm{in}}_u} x_v \ge \frac{w_u}{1 + \varepsilon } - \lambda \tau _u - \sum _{v' \in N^{\textrm{out}}_u} \lambda \tau _{v'}\\\ge & {} w_u \left( \frac{1}{1 + \varepsilon } - \lambda (\alpha + 1)\right) . \end{aligned}$$
This implies:
$$\begin{aligned} \begin{aligned} w_S&= \sum _{u \in S} w_u \le \sum _{u \in S} \left( \frac{1}{1 + \varepsilon } - \lambda (\alpha + 1)\right) ^{-1} \sum _{v \in N^{\textrm{in}}_u} x_v\\&\le \left( \frac{1}{1 + \varepsilon } - \lambda (\alpha + 1)\right) ^{-1} \sum _{v \in N^{+}_S} x_v \sum _{u\in S} {\mathbb {I}}[v \in N^{\textrm{in}}_u]\\&\le \alpha \left( \frac{1}{1 + \varepsilon } - \lambda (\alpha + 1)\right) ^{-1} \sum _{v \in N^{+}_S} x_v. \end{aligned} \end{aligned}$$
(1)
In the last inequality, we upper bound
\(\sum _{u \in S}{\mathbb {I}}[v \in N_{u}^{in}]\) with
\(\alpha \). This is because out-degree of
v is at most
\(\alpha \), so
v can be an incoming neighbor of at most
\(\alpha \) nodes.
The bound of eq.
1 along with observation
13 guarantee property (a) and property (b). The only remaining component is the round complexity. Note that each iteration of the procedure runs in
O(1) rounds in the
\(\textsf{CONGEST}\)model. So in total, there are
\(O(r) = O(\log _{1 + \varepsilon } \Delta \lambda ) = O\left( \frac{\log (\Delta \lambda )}{\varepsilon }\right) \) many rounds.
\(\square \)
4.2 Randomized algorithm
In the previous section, to extend our partial dominating set S to a dominating set, we simply added one node to S for each undominated node and this introduced a factor 2 in the approximation factor. Here, we show how we can get \(\alpha + O(\log \alpha )\) approximation, but we need \(O(\frac{\alpha }{\log \alpha } \log \Delta )\) rounds rather than \(O(\log \Delta )\) rounds. The algorithm also becomes randomized.
To reduce the approximation factor, we can leverage property (b) of lemma
11. To explain the intuition, we focus first on the unweighted case. If the problem is unweighted (so
\(\tau _v\) is 1 for all the nodes), then property (b) implies that each node has at most
\(\lambda ^{-1}\) undominated neighbors. The reason is that
\(X_u = \sum _{v \in N^{+}_u} x_v \le 1\) for all
u. Now since any node
\(v \not \in N^{+}_S\) has
\(x_v \ge \lambda \), there can only be at most
\(\lambda ^{-1}\) undominated nodes in
\(N^{+}_u\). So, dominating the set of nodes that are not in
\(N^+_{S}\) is a set cover problem with maximum set size
\(\lambda ^{-1}\) which can be approximated with a factor of
\(O(\log \lambda ^{-1})\) in
\(O(\log \lambda ^{-1} \log \Delta )\) rounds according to [
19] (Note that an undominated node can be a neighbor of many dominated nodes, so the frequency in the set cover instance can be as large as
\(\Delta + 1\)). Recall that the size of
S is bounded by
\(\alpha \left( \frac{1}{1 + \varepsilon } - \lambda (\alpha + 1)\right) ^{-1} \cdot \textrm{OPT}\). On the other hand, for extending
S, we add
\(O(\log \lambda ^{-1} \cdot \textrm{OPT})\) many nodes. If we set
\(\lambda = \Theta \left( \frac{\log \alpha }{\alpha ^2}\right) \) and
\(\varepsilon = \Theta \left( \frac{\log \alpha }{\alpha }\right) \), with straightforward calculations we can show that the expected size of the final dominating set is
\((\alpha + O(\log \alpha )) \cdot \textrm{OPT}\) and the algorithm takes
\(O\left( \frac{\alpha }{\log \alpha } \log \Delta \right) \) many rounds. The bottleneck for the round complexity is the first phase when we construct
S as there the number of rounds depends linearly on
\(\frac{1}{\varepsilon }\).
The weighted case is more subtle as there is no bound on the set size. Now lemma
11 implies that
\( x_v \ge \lambda \tau _v\), which is a different value for every
v, hence we cannot argue anymore that each node has at most
\(\lambda ^{-1}\) undominated neighbors. We are not aware of a result in the literature that we can use as a black box or with a clean reduction for this case, but we still want to exploit property (b) of lemma
11 to get an improved approximation. To do so, we devise a simple iterative randomized algorithm for this case. Towards resolving this, we also improve on the results of [
18,
19] for solving the dominating set problem on general graphs. There, they presented an
\(O(k^2)\) rounds randomized algorithm with expected
\(O(k\Delta ^{\frac{2}{k}} \log \Delta )\) approximation factor for the dominating set problem. We shave off the factor
\(\log \Delta \) in their bound as it is stated in theorem
3.
Our algorithm of extending S in full generality is stated in the following lemma.
Before proving lemma
14, we first show how we can prove the claim of theorem
2 via optimizing the parameters in lemma
11 and lemma
14. The theorem is restated below.
Back to the proof of lemma
14, we now try to use these two observations to show the claims of this lemma. First, note that the set
\(S \cup S'\) is not necessarily a dominating set. Consider the subproblem of dominating
\(V {\setminus } N^{+}_{S \cup S'}\). Clearly, we can dominate these nodes with a set of weight at most
\(\textrm{OPT}\). Moreover,
\(\{x_v\}_{v \not \in N^{+}_{S\cup S'}}\) is a feasible packing for this subproblem. Multiply the packing value of each node
\(v \not \in S \cup S'\) by a factor
\(\gamma \) and update
\(X_u\) for each
\(u \not \in S \cup S'\). The packing for this subproblem remains feasible. This is because, in the last iteration, we sample all nodes of
\(\Gamma _1\). So at the end of this iteration, a node
u that is not in
\(S \cup S'\) has
\(X_u \le \gamma ^{-1}w_u\) and as a result, multiplying the packing values by a factor
\(\gamma \) is safe.
Now, we define \(\Gamma _2\) as \(\{u \not \in S \cup S': X_u \ge \gamma ^{-1} w_u\}\) and run the procedure with \(\Gamma _2\). We repeat this for \(t = \lceil \log _{\gamma } \lambda ^{-1}\rceil \) times and claim that after that, \(S \cup S'\) is a dominating set.
Suppose it is not and let
v be an undominated node. At the very beginning,
\(x_v \ge \lambda \tau _v\) due to property (b) of lemma
11. Since
v is undominated, its packing value is
\(\gamma ^{i} x_v\) after we finish the process of
\(\Gamma _i\). Since
\(t = \lceil \log _{\gamma } \lambda ^{-1}\rceil \), there should be an
i such that the packing value of
v is at least
\(\gamma ^{-1} \tau _v\) when we finish working with
\(\Gamma _{i-1}\). On the other hand and from the definition of
\(\tau _v\), there is a neighbor
u of
v with weight
\(\tau _v\). This means that
u is in
\(\Gamma _i\) and it remains in
\(\Gamma _i\) until it is sampled. This contradicts that
v is not dominated.
From lemma
16, the expected weight of the sampled nodes in one phase is
\(\gamma (\gamma + 1)\cdot \textrm{OPT}\). So in total, the expected weight of
\(S'\) is
\(\gamma (\gamma +1)\lceil \log _{\gamma } \lambda ^{-1}\rceil \cdot \textrm{OPT}\).
Each iteration of each phase can be run in
O(1) rounds in the
\(\textsf{CONGEST}\)model. So in total, the algorithm needs
$$\begin{aligned} O(t \cdot r) = O(\log _\gamma \lambda ^{-1} \log _\gamma \Delta ) \end{aligned}$$
many rounds.
\(\square \)