A k-dominating set in a graph G = (V, E) is a set U ⊆ V such that ever vertex of G is either in U or has at least k neighbors in U . In this paper we give simple distributed approximation algorithms in the local model for the minimum k-dominating set problem for k ≥ 2 in graphs with no K3,h-minor and graphs with no K4,4-minor. In particular, this gives fast distributed approximations for graphs of bounded genus and linklessly embeddable graphs. The algorithms give a constant approximation ratio and run in a constant number of rounds. In addition, we will give a (1 + )-approximation for an arbitrary fixed > 0 which runs in O(log∗ n) rounds where n is the order of a graph.
The minimum dominating set (MDS) problem is one of the most extensively
studied graph-theoretic questions. On one hand, it plays an important role in
graph theory, on the other, it admits many important applications. Its
complexity has been studied in many different computational models and for various
classes of graphs. In general, the problem is NP-hard [
In [
Often a stronger notion of a domination is needed. For example, in some applications it can be desirable to require that every vertex in a graph is dominated not by one vertex from a set but by k vertices for some k ∈ Z+. This can be interpreted as a fault tolerance requirement; Servers are placed in a network so that each vertex/client has direct access to k servers.
To denfie the problem formally we need some notation and terminology. Let
G = (V, E) be a graph with |V | = n. By NG(v) = {u ∈ V : uv ∈ E} we denote
the neighborhood of a vertex v ∈ V and by NG[v] = NG(v) ∪ {v} the closed
neighborhood of v. We use dG(v) (or d(v) if G is clear from the context) to
denote |NG(v)|. Set D ⊆ V is called a dominating set in G if every vertex in
V \ D is adjacent to a vertex in D. A minimum dominating set in a graph G is a
dominating set in G of the smallest size. For a positive integer k, a k-dominating
set in G is a subset D ⊆ V such that for every v ∈ V \ D, |N (v) ∩ D| ≥ k,
that is, for every vertex v ∈ V , v is in D or v has at least k neighbors in D.
In particular, a 1-dominating set is simply a dominating set. In addition, we
will say that a set W k-dominates set U in G, if every vertex from U \ W
has at least k neighbors in W . Note that other notions of k-domination have
been considered and many variants of the problem have been studied (see [
Let Sh denote the surface obtained from the sphere by adding h handles
(see [
In addition to the graphs with no K3,h-minor we will give a distributed approximation algorithm for graphs with no K4,4-minor. This, in particular, yields an algorithms for linklessly embeddable graphs which are sometimes viewed as 3-dimensional analogs of planar graphs. An embedding of a graph in R3 is called linkless if every pair of (vertex) disjoint cycles are unlinked closed curves. It is not difficult to see that K4,4 is not linklessly embeddable (the only fact that will be needed).
We will consider the Local model ([
Our contribution is twofold. First, we show that for graphs of bounded genus
there is an easy distributed algorithm which gives a constant approximation of
the minimum k-dominating set for k ≥ 2. This mirrors the corresponding result
for planar graphs. In addition, the same approach gives a constant approximation
for k ≥ 3 in linklessly embeddable graphs. The case k = 2 is different, and to
address it we use a modification of the algorithm from [
The paper is structured as follows. In the next section, we state some preliminary facts. In the following section we give the first (simple) approximation algorithm for the minimum k-dominating set in graphs with no T Kh,k+1. This yields an algorithm for graphs of bounded genus for k ≥ 2 and for linklessly embeddable graphs when k ≥ 3. In Section 4 we address the 2M DS problem for graphs with no T K4,4 which gives, in particular, an algorithm for linklessly embeddable graphs when k = 2. Finally, in Section 5, we discuss the (1 + )approximation. 2
Preliminaries
We will start our technical discussion with a few facts which will be used later.
We have the following bound for the number of edges in a graph with T Kh (see
[
We will also need a more general bound for E(G) in the case G has no Kp-minor.
The following was proved by Kostochka in [
is a graph on n vertices with no Kr-minor, then |E(G)| ≤ cr√log rn.
One of the main tools used in the proofs will be lemmas from [
graph with no T Kh and let D be a dominating set in G. Then |Dh− 1,l| ≤ c|D|. In addition, we have the following fact.
Lemma 4. Let h ∈ Z+. For l, m ∈ Z+ there is c = c(m, l) such that if G is graph with no T Km,h and D is a dominating set in G then |Dm,l| ≤ c|D|. 3
First algorithm for graphs with bounded genus and linklessly embeddable graphs In our rfist algorithm (Procedure 1) we simply add to the solution all vertices of sufficiently large degree and claim that this gives a constant approximation of a k-dominating set. Specifically, we will show that in the case when k ≥ 2 and G has bounded genus or k ≥ 3 and G is linklessly embeddable, this gives a constant approximation of a minimum k-dominating set. We will need the following lemma in the analysis.
Lemma 5. Let k, h, q ∈ Z+ be such that k ≤ q. If H = H[U, X] is a bipartite graph such that |U | ≥ kq (h − 1) + 1, |X| ≤ q and for every vertex u ∈ U , dH (u) ≥ k, then H contains Kh,k.
Proof. The proof is similar to a proof of an upper bound for the extremal number of a complete bipartite graph. Suppose H has no Kh,k. We will count the number of k-stars (stars of degree k) with centers in U . On one hand, the number of such k-stars is at least Pu∈U d(ku) ≥ | U |. On the other hand, since H has no Kh,k, the number of k-stars is at most |X| (h − 1). Consequently, if k |U | ≥ |Xk | (h − 1) + 1, then H contains Kh,k.
Let h, k ∈ Z+, set L := k+h (h − 1) + 2(k + h) + 1 and consider the following k procedure.
Procedure 1
2. For every v ∈ V (G) \ D, if |N (v) ∩ D| < k, then add v to D. 3. Return D.
In fact we will proves something slightly more general.
Fact 1 For h, k ∈ Z+ let L := k+k h (h − 1) + 2(k + h) + 1. If G is a graph with no T Kh+k+1 and no Kh,k+1, then Procedure 1 applied to G with L returns a k-dominating set of size O(γ k(G)).
Proof. Let W := {v ∈ V (G) : d(v) ≥ L} and let D∗ be an optimal k-dominating set. Then the number of vertices in G which have a neighbor in D∗ \ W is at most (L − 1)|D∗ |. Suppose that v ∈ V (G) \ W has |N (v) ∩ W | < k and so it is added to D in the second step of the algorithm. Then v is either in D∗ or has at least one neighbor in D∗ \ W and so the number of vertices added in step 2 is at most L|D∗ |. Thus to show that |D| = O(γ k(G)) it is enough to show that |W | = O(|D∗ |). To that end, note that for every v ∈ W \ D∗ , N (v) \ D∗ is k-dominated by D∗ . If |N (v) ∩ D∗ | ≥ h + k, then v ∈ Dh∗+k,1. Since G has no T Kh+k+1, D∗ is a k-dominating set and so a 1-dominating set, by Lemma 3, the number of such vertices is O(|D∗ |). Thus we may assume that |N (v) \ D∗ | > L − (h + k) and recall that N (v) \ D∗ is k-dominated by D∗ . Consider a maximum matching M in G[N (v) \ D∗ , D∗ ] and note that if |M | ≥ h + k, then v ∈ Dh∗+k,2. Thus we may assume that |M | < h + k. Since M is a maximum matching in G[N (v) \ D∗ , D∗ ], if w ∈ N (v) \ (D∗ ∪ V (M ), then all neighbors of w which are in D∗ are in V (M ) as otherwise we could increase M . Consequently, |N (N (v)\(D∗ ∪V (M )))∩D∗ | ≤ | V (M )∩D∗ | < h+k. In addition, |E(N (v)\(D∗ ∪V (M )), V (M )∩D∗ )| ≥ k|N (v)\(D∗ ∪V (M ))| because D∗ is a kdominating set,and , by definition of L, |N (v) \ (D∗ ∪ V (M ))| ≥ k+k h (h − 1) + 1. Thus, by Lemma 5, G[N (v) \ (D∗ ∪ V (M )), V (M ) ∩ D∗ ] contains Kh,k, which in connection with v gives Kh,k+1 contradicting the fact that G has no T Kh,k+1. The contradiction shows that |M | ≥ h + k and so v ∈ Dh∗+k,2. By Lemma 3, |Dh∗+k,2| = O(γ k(G)).
We immediately get constant approximations for γ k(G) in linklessly embeddable graphs for k ≥ 3.
dure 1 applied to G returns a k-dominating set of size O(γ k(G)) when applied with h = 4.
Proof. Since G is linklessly embeddable, G has no K4,4-minor and therefore no K4,4 and no T K8. We can apply Procedure 1 with h = 4.
If G is a graph with g(G) ≤ g, then G has no K4g+3,3-minor. Consequently Procedure 1 can be applied to G for every k ≥ 2 gives a constant approximation.
dure 1 returns a k-dominating set of size O(γ k(G)) when applied with h = 4g +3. Proof. Since G has genus bounded by g, G ∈ B4g+3, and so G has no T K4g+3,3. 4
Graphs with no T K4,4 for k = 2
In the case G has no K4,4-minor and k = 2 it is no longer possible to claim that
Procedure 1 gives a constant approximation of γ k(G) and a slightly more
involved algorithm is needed. We will show that a modicfiation of the algorithm
for the minimum dominating set in planar graphs from [
We will start with the following observation.
there is a set S ⊆ V (G) \ U of size |S| ≤ K which 2-dominates U , then there exist s1, s2 ∈ S such that s1 6= s2 and |N (s1) ∩ N (s2) ∩ U | ≥ 4.
Proof. Clearly there exists s1 ∈ S such that |N (s1) ∩ U | ≥ 4K2/K = 4K and there exists s2 ∈ S \ {s1} such that |N (s2) ∩ (N (s1) ∩ U )| ≥ 4K/K ≥ 4.
In what follows, let K := 642, C := 4K2 + K and L := 4C + 3. We will assume that G has no T K4,4.
Procedure 2 1. For every v ∈ V (G): If there is no set S ⊆ V \ {v} such that |S| ≤ K and S 2-dominates N (v), then add v to D1. In addition if d(v) < 2, then add v to D1. 2. Let Z be the set of vertices which are 2-dominated by D1 and let d0(v) := |N (v) \ Z| for v ∈ V . 3. For every u ∈ V \ Z: – If |N (u)∩D1| = 1, then choose v ∈ N (u)\D1 such that d0(v) is maximum and add it to D2. – If |N (u) ∩ D1| = 0, then choose two distinct v, v0 ∈ N (u) with the largest degrees d0 and add them to D2. 4. Return D1 ∪ D2.
Note that Procedure 2 works in the Local model as in the second step a vertex v can obtain locally information about the ball of radius two centered at v to determine if it should be added to D1.
We first note that D1 ∪ D2 is a 2-dominating set.
Proof. Suppose u ∈/ D1 and |N (u) ∩ D1| = i for i = 0, 1. Then d(u) ≥ 2, and so u has at least 2 − i neighbors in V \ D1. In the second step of the procedure 2 − i of them will be added to D2.
Let D∗ be an optimal 2-dominating set in G. We will now show that |D1 ∪ D2| ≤ C|D∗ | for some constant C.
Fact 5 |D1| = O(|D∗ |).
Proof. First note that if d(v) < 2, then v ∈ D∗ . In addition, for v ∈ D1 \ D∗ , we certainly have |N (v)| > K because N (v) is an option for S. Let V1 := {v ∈ D1 \ D∗ : |N (v) ∩ D∗ | ≥ K/2}. We have K|V1|/2 ≤ | EG(V1, D∗ )| < 5 · 64(|V1| + |D∗ |) by Lemma 1, and so |V1| < 320|D∗ |. Let V2 := {v ∈ D1 \ D∗ : |N (v) ∩ D∗ | < K/2}. Take v ∈ V2 and let W ⊆ D∗ be a minimum set which 2dominates N (v) \ D∗ . We have |W | ≥ K/2 because W ∪ (N (v) ∩ D∗ ) 2-dominates N (v). In addition, |N (v) \ D∗ | = |N (v)| − | N (v) ∩ D∗ | > K/2. Therefore, by minimality of W , there is a matching of size at least |W |/2 ≥ K/4 ≥ 4 between W and N (v) \ D∗ , and consequently there is a v, W2-fan of size four. Therefore, v ∈ D4∗,2 and, by Lemma 4, |V2| = O(|D∗ |).
To show that |D1 ∪ D2| = O(|D∗ |) we will now prove that |D2| = O(|D∗ |). Fact 6 |D2| = O(|D∗ |).
Proof. If D∗ \ D1 = ∅, then every vertex in V \ D1 has two neighbors in D1 and D2 = ∅. For a vertex u ∈ V \ (Z ∪ D∗ ) which has one neighbor in D1, there is at least one v ∈ D∗ \ D1 such that u ∈ N (v). We fix one such v and say that u belongs to v. If u has no neighbors in D1, then there exist at least two vertices v, v0 ∈ D∗ \ D1 such that u ∈ N (v) ∩ N (v0). We fix such a pair ( v, v0) and say that u belongs to v if d0(v) < d0(v0) (if the degrees are equal then we select one of v, v0 arbitrarily.)
Note that every vertex u ∈ V \ Z is either in D∗ \ D1 or belongs to exactly one vertex from D∗ \ D1.
In order to show that |D2| = O(|D∗ |) we will argue that for every vertex v ∈ D∗ \ D1 there can be at most a constant number of vertices added to D2 by v and by vertices which belong to v. Let v ∈ D∗ \ D1. Note that v can select at most two vertices to be added to D2. In addition, there exists a set S ⊆ V \ {v} such that |S| ≤ K and S 2-dominates N (v). Fix such a set S and call it Sv. Let N˜ (v) be the set of u ∈ N (v) such that u belongs v. First suppose |N˜ (v)| ≤ L. Since each u ∈ N˜ (v) selects at most two vertices in step 3, the number of vertices added to D2 by vertices from N˜ (v) is at most 2L. Now assume |N˜ (v)| > L. Let w ∈ V \ (D1 ∪ D∗ ∪ Sv) and suppose w has a neighbor in N˜ (v). If |N (w) ∩ N˜ (v)| > C, then Sv 2-dominates (N (w) ∩ N˜ (v)) \ Sv which has size at least 4K2, and so by Lemma 6, G contains K4,4 which is not possible. Thus 0 < |N (w) ∩ N˜ (v)| ≤ C for every vertex v. For a vertex x, if u ∈ N (w) ∩ N˜ (x), u belongs to x and d0(x) > L. Thus if u selects w in step 3, then d0(w) > L. All neighbors of w in G[V \ Z] are either in D∗ \ D1 or in one of the sets N˜ (x). If w has four neighbors in D∗ , then w ∈ D4∗,1. Otherwise, w has at least one neighbor in N˜ (x) for at least (L − 3)/C ≥ 4 vertices x ∈ D∗ \ D1. Consequently, by Lemma 4, the number of such vertices is O(|D∗ |). Finally, since |Sv| ≤ K, there are at most K vertices in Sv which can be added to D2 by vertices in N˜ (v) in step 3.
Thus we have the following theorem.
graph with no T K4,4. Then Procedure 2 finds a 2-dominating set D such that |D| ≤ Cγ 2(G).
From Theorem 7, we get a constant approximation for the 2-minimum dominating set problem in linklessly embeddable graphs.
to G returns a 2-dominating set of size O(γ 2(G)). 5 (1 +
)-approximation
In this section we will show that a modification of the approach from [
holds. Suppose G is a graph on n vertices with no Kp-minor and let ω : E(G) →
that G[Vi] has diameter O(C) and X ω(e) ≤ e∈G˜
X ω(e). e∈G
By combining Theorem 9 with some additional analysis we obtain the following fact.
no Kp-minor and suppose Q is a k-dominating set for G. There is a distributed algorithm which finds a k-dominating set D in G such that
|D| ≤ γ k(G) + δ |Q|.
Note that the case k = 1 is proved in [
on n vertices with genus g. There is a distributed algorithm which finds a kdominating set D in G such that |D| ≤ (1 + )γ k(G). The algorithm runs in
Proof. In view of Corollary 3, there is a distributed algorithm which in a constant number of rounds finds a k-dominating set Q in G such that |Q| ≤ Lγ K (G) for some constant L. Let δ := /L. The by Theorem 10 nfids a dominating set D such that |D| ≤ (1 + )γ k(G).
In addition, using the algorithms for linklessly embeddable graphs from previous sections we obtain the following fact.
on n vertices. There is a distributed algorithm which finds a k-dominating set D in G such that |D| ≤ (1 + )γ k(G). The algorithm runs in C log∗ n rounds where
Proof of Theorem 10. Let Q be a k-dominating set in G. Let G0 be the following oriented graph obtained form the bipartite graph G[Q, V (G) \ Q]. We put the arc from v to w for every edge vw with v ∈ V (G) \ Q and w ∈ Q. Since Q is k-dominating, every vertex v ∈ V (G) \ Q has at least k out-neighbors in G0. By choosing one such out-neighbor arbitrarily, we obtain a set of stars S1, . . . , Sl with centers in vertices from Q. Let Uj := V (Sj ) and let cUj denote the center of Sj , that is {cUj } = Uj ∩ Q. We will refer to sets Uj as small clusters. Let H0 be the digraph obtained from G0 by contracting each Sj to a vertex. (Note that it is possible to have both arcs Uj Ui and UiUj in H0.) Let D := ∅ and let K := 2c · p√log pk/δ where c is the constant in Lemma 2.
We will modify the original small clusters and construct a sequence of digraphs H1, . . . , Hk− 1 by increasing D in each step so that |D| is small with respect to |Q| and clusters in Hk− 1 obtained by deleting vertices which are kdominated by D have out-neighbors in at most K other vertices from Q. Some of the centers of small clusters will be added to D, some vertices will be reassigned from one cluster to another, and, in addition, some vertices will become k-dominated by D and will become inactive. Although we no longer need to kdominate inactive vertices (as they are k-dominated by D), they can still play an important role because they themselves can be inside an optimal k-dominating set. Although the sets Uj will change as we modify them, we will use Uj to refer to the cluster determined by cUj during the execution of the algorithm. For cluster U we use U 00 to denote the set of inactive vertices in U \ {cU } and we set U 0 := U \ U 00. Initially, U 00 := ∅ for every cluster U and we set B0 := V (G) \ Q. We will now describe our procedure which modifies the small clusters. We will use d+(X) to denote the number of out-neighbors of a cluster X in F . Recall
F that clusters are associated with their centers and so cluster X at step i can be different than X at step j for i 6= j.
For the general step, assume i ≥ 1 and let Xi− 1 := {U |d+Hi− 1 (U 0) > K}. If U ∈ Xi− 1, then add cU to D. Consider v ∈ Bi− 1 ∩ U 0. If v becomes k-dominated by D, then move v to U 00 and otherwise, add v to Bi. Every vertex v ∈ Bi has at most k − 1 neighbors in D and so there exists a small cluster W such that cW ∈/ D and vcW ∈ G0. Let v join one such cluster W .
Let Hi be obtained by contracting each small cluster U to a vertex and by adding the arc U W if the set of arcs from U 0 to W 0 in G0 is non-empty.
We will prove the following lemma.
Lemma 7. The following holds: (a) Pk
i=1 |Xi− 1| < δ |Q|/2. (b) For every v ∈ Bk, |NG(v) ∩ D| ≥ k. (c) For every small cluster U there exists a set of small clusters Q0 ⊆ that |Q0| ≤ K and every vertex v ∈ U \ (Bk ∪ {cU }) has NG(v) ∩ Q ⊆
Q0 ∪ D.
To prove the lemma we will show a sequence of claims. Part (a) follows from the following observation.
Claim. |Xi− 1| < δ |Q|/(2k).
Proof. From Lemma 2, PU∈Hi− 1 d+Hi− 1 (U ) = |E(Hi− 1)| ≤ |Xi− 1| < cp√log p|Q|/K = δ |Q|/(2k).
We will now verify part (b).
Claim. If v ∈ Bi, then |NG(v) ∩ D| ≥ i. cp√log p|Q|. Thus Proof. This is certainly true when i = 0. Suppose i ≥ 1. If v ∈ Bi, then v ∈ Bi− 1 and in the ith step of the procedure v ∈ U 0 for some U ∈ Xi− 1. Since cU is added to D, |NG(v) ∩ D| increases by at least one.
Part (c) is slightly more involved and we split the argument into two claims. First note the following.
Proof. We proceed by induction on i. If U ∈ X0, then after adding cu to D and partitioning U into U 0 and U 00, every vertex from U 0 is reassigned and so in the next step U 0 is empty. Suppose U ∈ Xi. Then, by induction, U ∈/ Xi− 1. Thus some vertices from Bi− 1 joined U , as this is the only way for the out-degree of a cluster to increases. Each such vertex is either inactive or is in Bi after cU is added to D in the ith step, and every vertex from Bi ∩ U joins a cluster different than U with center which is not in D. Consequently, none of these added vertices + + is in U 0 in the iteration i + 1, and we have dHi+1 (U 0) ≤ dHi− 1 (U 0).
for every vertex v ∈ U \ (Bi ∪ {cU }), NG(v) ∩ Q ⊆
Q0 ∪ D.
K and Proof. If U ∈/ Xi then d+Hi (U 0) ≤ K and so NG(U 0 \ (Bi ∪ {cU })) ∩ Q ⊆ Q0 for some set Q0 of size at most K. Suppose U ∈ Xi. Then U ∈/ Xi− 1 by Claim 5. Therefore some vertices from Bi− 1 joined U and each of them is either inactive (and dominated by D) or is in Bi. Consider U 0 in the ith iteration of the procedure. The set U 0 is a subset of the union of X and Y , where X is the set U 0 \ Bi− 1 from the iteration i − 1 and Y is the set of vertices added to the small cluster U in the ith iteration. The number of distinct out-neighbors of X in Q is therefore at most K, and the vertices from Y are either dominated by D or are in Bi.
This proves part (c) of the lemma.
We will now continue with the proof of Theorem 10.
Let U1, . . . , Ul denote the clusters in Hk and recall that l = |Q|. Let G∗ be obtained from G by contracting each Ui to a vertex ui. In addition, set ω(uiuj ) = 1 for every edge uiuj ∈ G∗ . Let := δ/ (6c · p√log pK) and use the clustering procedure from Theorem 9 to nfid a partition P of {u1, . . . , ul} into V1, . . . , Vs. Then ω(G˜) ≤ |E(G)| ≤
· cpplog pl < δl/ (6K).
Let ∂P be the set of u ∈ {u1, . . . , ul} such that for some i 6= j, u ∈ Vi and NG∗ (u) ∩ Vj 6= ∅. We have |∂P | ≤ 2ω(G˜) ≤ δl/ (3K).
Let u ∈ ∂P and consider the small cluster U which was contracted to u. Add cU to D and note that by Lemma 7 (b) every vertex v ∈ Bk ∩ U has k-neighbors in D. In addition, by Lemma 7 (c), there is a set Q0 of at most K vertices in Q such that every vertex v ∈ U \ (Bk ∪ {cU }) has NG(v) ∩ Q ⊆ Q0 ∪ D. Since every vertex v ∈ V (G) \ Q has at least k neighbors in Q, by adding Q0 ∪ {cU } to D we k-dominate all vertices from U . Add Q0 ∪ {cU } to D for every U ∈ ∂P . By Lemma 7 (a), we have
|D| ≤ δ |Q|/2 + δl (K + 1)/(3K) < δ |Q|.
Let Wi := SU∈Vi\∂P U . Since the diameter of G[Vi] is O(1), it is possible to nfid in O(1) rounds an optimal set Di ⊆ Vi such that Di ∪ D k-dominates Wi. Let D0 := Sli=1 Di ∪ D and let D∗ denote an optimal k-dominating set in G. Then |D0| ≤
X |Di| + |D| ≤
X |D∗ ∩ Vi| + |D| ≤ | D∗ | + |D| < γ k(G) + δ |Q| where the second inequality follows from the fact that every vertex in Wi can be k-dominated only by vertices in Vi ∪ D and every vertex in SU∈∂P U is kdominated by D.