arXiv:1510.05886v2 [cs.DM] 13 Mar 2017

Approximation Algorithm for Minimum Weight
Connected m-Fold Dominating Set
Zhao Zhang1
1

Jiao Zhou2

Ker-I Ko3

Ding-zhu Du4

College of Mathematics Physics and Information Engineering, Zhejiang Normal University
Jinhua, Zhejiang, 321004, China
2

College of Mathematics and System Sciences, Xinjiang University
Urumqi, Xinjiang, 830046, China

3

Department of Computer Science, National Chiao Tung University
Hsinchu, 30050, Taiwan
4

Department of Computer Science, University of Texas at Dallas
Richardson, Texas, 75080, USA

Abstract: Using connected dominating set (CDS) to serve as a virtual backbone in
a wireless networks can save energy and reduce interference. Since nodes may fail due
to accidental damage or energy depletion, it is desirable that the virtual backbone has
some fault-tolerance. A k-connected m-fold dominating set ((k, m)-CDS) of a graph G
is a node set D such that every node in V \ D has at least m neighbors in D and the
subgraph of G induced by D is k-connected. Using (k, m)-CDS can tolerate the failure of
min{k − 1, m − 1} nodes. In this paper, we study Minimum Weight (1, m)-CDS problem
((1, m)-MWCDS), and present an (H(δ+m)+2H(δ−1))-approximation algorithm, where
δ is the maximum degree of the graph and H(·) is the Harmonic number. Notice that
there is a 1.35 ln n-approximation algorithm for the (1, 1)-MWCDS problem, where n is
the number of nodes in the graph. Though our constant in O(ln ·) is larger than 1.35, n
is replaced by δ. Such a replacement enables us to obtain a 3.67-approximation for the
connecting part of (1, m)-MWCDS problem on unit disk graphs.
Keyword: m-fold dominating set, connected dominating set, non-submodular function, greedy algorithm, unit disk graph.

1

Introduction

A wireless sensor network (WSN) consists of spatially distributed autonomous sensors
to monitor physical or environmental condition, and to cooperatively pass their data
through the network. During recent years, WSN has been widely used in many fields,
1

such as environment and habitat monitoring, disaster recovery, health applications, etc.
Since there is no fixed or predefined infrastructure in WSNs, frequent flooding of control
messages from sensors may cause a lot of redundant contentions and collisions. Therefore,
people have proposed the concept of virtual backbone which corresponds to a connected
dominating set in a graph (Das and Bhargharan [4] and Ephremides et al. [8]).
Given a graph G with node set V and edge set E, a subset of nodes C ⊆ V is said to
be a dominating set (DS) of G if any v ∈ V \ C is adjacent to at least one node of C. We
say that a dominating set C of G is a connected dominating set of G if the subgraph of
G induced by C, denoted by G[C], is connected. Nodes in C are called dominators, the
nodes in V \ C are called dominatees.
Because sensors in a WSN are prone to failures due to accidental damage or battery
depletion, it is important to maintain a certain degree of redundancy such that the virtual
backbone is more fault-tolerant. In a more general setting, every sensor has a cost, it
is desirable that under the condition that tasks can be successfully accomplished, the
whole cost of virtual backbone is as small as possible. These considerations lead to the
Minimum Node-Weighted k-Connected m-Fold Dominating Set problem (abbreviated as
(k, m)-MWCDS), which is defined as follows:
Definition 1.1 ((k, m)-MWCDS). Let G be a connected graph, k and m be two positive
integers, c : V → R+ be a cost function on nodes. A node subset D ⊆ V is an m-fold
dominating set (m-DS) if every node in V \ D has at least m neighbors in D. It is a kconnected m-fold dominating set ((k, m)-CDS) if furthermore, the subgraph of G induced
by D is k-connected. The (k, m)-MWCDS problem
is to find a (k, m)-CDS D such that
P
the cost of D is minimized, that is, c(D) = u∈D c(u) is as small as possible.
After Dai and Wu [3] proposed using (k, k)-CDS as a model for fault-tolerant virtual
backbone, a lot of approximation algorithms emerged, most of which are on unit disk
graphs. In a unit disk graph (UDG), every node corresponds to a sensor on the plane,
two nodes are adjacent if and only if the Euclidean distance between the corresponding
sensors is at most one unit. There are a lot of studies on fault-tolerant virtual backbone
in UDG which assume unit weight on each disk. However, for a general graph with a
general weight function, related studies are rare.

In this paper, we present a (H(δ + m) + 2H(δ − 1))-approximation algorithm for the
(1, m)-MWCDS
Pγ problem on a general graph, where δ is the maximum degree of the graph,
and H(γ) = 1 1/i is the Harmonic number. It is a two-phase greedy algorithm. First,
it constructs an m-fold dominating set D1 of G. Then it connects D1 by adding a set
of connectors D2 . It is well known that if the potential function and the cost function
related with a greedy algorithm is monotone increasing and submodular, then an O(ln n)
performance ration can be achieved. Unfortunately, for various minimum CDS problems,
no such potential functions are known. Nevertheless, we manage, in this paper, to deal
with a nonsubmodular potential function and achieve an O(ln δ) performance ratio.
It should be pointed out that for a general graph, Guha and Khuller [11] proposed a
1.35 ln n-approximation for the (1, 1)-MWCDS problem. Though our constant in O(ln n)
2

is larger, the parameter n in the performance ratio is replaced by δ. In many cases, δ might
be substantially smaller than n. In particular, for an UDG, due to such an replacement,
after having found an m-DS, the connecting part has a performance ratio at most 3.67. In
[34], Zou et al. proposed a method for the connecting part with performance ratio at most
3.875, which makes use of a 1.55-approximation algorithm [16] for the classic Minimum
Steiner Tree problem. If using currently best ratio for Minimum Steiner Tree problem [1],
then their ratio is at most 3.475. Notice that the algorithm in [1] uses randomized iterative
rounding. So, although our ratio 3.67 is a litter larger than 3.475, our algorithm has the
advantage that it is purely combinatorial. Furthermore, we believe that our method is
also of more theoretical interests and may find more applications in the study of other
related problems.
The rest of this paper is organized as follows. Section 2 introduces related works.
Some notation and some preliminary are given in Section 3. In Section 4, the algorithm
is presented. Section 5 analyzes the performance ratio. Section 6 improves the ratio on
unit disk graph. Section 7 concludes the paper.

2

Related work

The idea of using a connected dominating set as a virtual backbone for WSN was
proposed by Das and Bhargharan [4] and Ephremides et al. [8]. Constructing a CDS
of the minimum size is NP-hard. In fact, Guha and Khuller [11] proved that a minimum CDS cannot be approximated within ρ ln n for any 0 < ρ < 1 unless NP ⊆
DT IME(nO(loglogn) ). In the same paper, they proposed two greedy algorithms with performance ratios of 2(H(δ) + 1) and H(δ) + 2, respectively, where δ is the maximum degree
of the graph and H(·) is the harmonic number. This was improved by Ruan et al. [17]
to 2 + ln δ. Du et al. [5] presented a (1 + ε) ln(δ − 1)-approximation algorithm, where ε
is an arbitrary positive real number.
For unit disk graphs, a polynomial time approximation scheme (PTAS) was given by
Cheng et al. [2], which was generalized to higher dimensional space by Zhang et al. [28].
There are a lot of studies on distributed algorithms for this problem. For a comprehensive
study on CDS in UDG, the readers may refer to the book [7].
Considering the weighted version of the CDS problem, Guha and Khuller [11] proposed
a (cn +1) ln n-approximation algorithm in a general graph, where cn ln k is the performance
ratio for the node weighted Steiner tree problem (k is the number of terminal nodes to
be connected). Later, they [12] improved it to an algorithm of performance ratio at most
(1.35 + ε) ln n. For the minimum weight CDS in UDG, Zou et al. [34] gave a (9.875 + ε)approximation.
The problem of constructing fault-tolerant virtual backbones was introduced by Dai
and Wu [3]. They proposed three heuristic algorithms for the minimum (k, k)-CDS problem. However, no performance ratio analysis was given. A lot of works have been done for
the CDS problem in UDG. The first constant approximation algorithm in this aspect was
3

given by Wang et al. [24], who obtained a 72-approximation for the (2, 1)-CDS problem
in UDG. Shang et al. [18] gave an algorithm for the minimum (1, m)-CDS problem and
an algorithm for the minimum (2, m)-CDS problem in UDG, the performance ratios are
5 + m5 for m ≤ 5 and 7 for m > 5, and 5 + 25
for 2 ≤ m ≤ 5 and 11 for m > 5, rem
spectively. Constant approximation algorithms also exist for (3, m)-CDS in UDG [25, 26].
Recently, Shi et al. [20] presented the first constant approximation algorithm for general
(k, m)-CDS on UDG.
For the fault-tolerant CDS problem in a general graph, Zhang et al. [30] gave a
2rH(δr + m − 1)-approximation for the minimum r-hop (1, m)-CDS problem, where δr is
the maximum degree in Gr , the r-th power graph of G. A node u is r-hop dominated by
a set D if it is at most r-hops away from D. In particular, taking r = 1, the algorithm in
[30] has performance ratio at most 2H(δ + m − 1) for the minimum (1, m)-CDS problem.
This was improved by our recent work [33] to 2 + H(δ + m − 2). We also gave an
(ln δ + o(ln δ))-approximation algorithm for the minimum (2, m)-CDS problem [19] and
the minimum (3, m)-CDS problem [32] on a general graph.
For the weighted version of fault-tolerant CDS problem on UDG, as a consequence of
recent work [13], the minimum weight (1, 1)-CDS problem admits a PTAS. Combining
the constant approximation algorithm for the minimum weight m-fold dominating set
problem [9] and the 3.475-approximation algorithm for the connecting part [34], (1, m)MWCDS on UDG admits a constant-approximation. Recently, we [20, 31] gave the first
constant approximation algorithm for the general minimum weight (k, m)-CDS problem
on unit disk graph.
As far as we know, there is no previous work on the approximation of the weighted
version of fault-tolerant CDS problem in a general graph.
Notice that in [34], the 3.875-approximation for the connecting part is based on the
1.55-approximation algorithm [16] for the classic minimum Steiner tree problem. If the
best known ratio for the Steiner tree problem is used, which is 1.39 currently, then their
connecting part has performance ratio at most 3.475. Notice that the 1.39-approximation
for the Steiner tree problem uses randomized iterative rounding. So, although our performance ratio is larger than 3.475, it has the advantage that it is purely combinatorial.

3

Preliminaries

In this section, we introduce some notation and give some preliminary results. For a
node u ∈ V (G), denote by NG (u) the set of neighbors of u in G, andSdegG (u) = |NG (u)| is
the degree of node u in G. For a node subset D ⊆ V (G), NG (D) = u∈D NG (u) \ D is the
neighbor set of D, G[D] is the subgraph of G induced by D. When there is no confusion
in the context, the vertex set of a subgraph will be used to denote the subgraph itself.
For an element set U, suppose f : 2U 7→ R+ is a set function on U (called a potential

4

function). For two element sets C, D ⊆ U, let
△D f (C) = f (C ∪ D) − f (C)
be the marginal profit obtained by adding D into C. For simplicity, △u f (C) will be
used to denote △{u} f (C) when u is a node. Potential function f is monotone increasing
if f (C) ≤ f (D) holds for any subsets C ⊆ D ⊆ V . It is submodular if and only if
△u f (C) ≥ △u f (D) holds for any C ⊆ D ⊆ V and any u ∈ V \ D. A monotone increasing
and submodular function f with f (∅) = 0 is called a polymatroid. Given an element set
U with cost function c : U 7→ R+ and given a polymatroid f : 2U 7→ R+ , denote by
Ωf = {C ⊆ U : △u f (C) = 0 for any u ∈ U }. The Submodular Cover problem is:
X
min c(C) =
c(u)
u∈C

s.t. C ∈ Ωf .

The following is a classic result which can be found in [6] Theorem 2.29.
Theorem 3.1. The greedy algorithm for the submodular coverPproblem has performance
γ
ratio H(γ), where γ = max{f ({u}) : u ∈ U} and H(γ) =
i=1 1/i is the Harmonic
number.

4
4.1

The Algorithm
The Algorithm

For a node set C, denote by p(C) the number of components in G[C]. For a node
u ∈ V \ C, let NC (u) denote the set of neighbors of u in C. Define

max{m − |NC (u)|, 0}, u ∈ V \ C,
qC (u) =
0,
u ∈ C,
and
q(C) = m|V | −

X

qC (u).

u∈V

For a node set U ⊆ V , denote by NCC (U) the set of components of G[C] which are
adjacent to U. Every component in NCC (U) is called a component neighbor of U in G[C].
For a node u ∈ V , we shall use Su to denote some star with center u, that is, Su is a
subgraph of G induced by edges between node u and some of u’s neighbors in G. In
particular, a node is a star of cardinality one and an edge is a star of cardinality two.
To abuse the notation a little, we also use Su to denote the set of nodes in Su . Suppose
Su \ {u} = {u1, u2 , . . . , us }, where c(u1 ) ≤ c(u2 ) ≤ . . . ≤ c(us ). Define
p′C (Su )

= |NCC (u)| − 1 +

s
X

min{1, − △ui p(C ∪ {u, u1, . . . , ui−1})}.

i=1

5

(1)

Call eC (Su ) = p′C (Su )/c(Su ) the efficiency of Su with respect to C.
The algorithm is presented in Algorithm 1.
Algorithm 1
Input: A connected graph G = (V, E).
Output: A (1, m)-CDS DG of G.
1: Set D1 ← ∅
2: while there exists a node u ∈ V \ D1 such that △u q(D1 ) > 0, do
3:
select u which maximizes △u q(D1 )/c(u)
4:
D1 ← D1 ∪ {u}
5: end while
6: Set D2 ← ∅
7: while there exists a star Su ⊆ V \ (D1 ∪ D2 ) such that p′D1 ∪D2 (Su ) > 0, do
8:
select a star Su with the largest efficiency with respect to D1 ∪ D2 .
9:
D2 ← D2 ∪ S u
10: end while
11: Output DG ← D1 ∪ D2

4.2

The Idea of the Algorithm

The idea underlying the algorithm is as follows. Potential function qD1 (u) measures
how many more times that node u needs to be dominated, and q(D1 ) is the total residual
domination requirement. As can be seen from Lemma 5.2, at the end of the first phase,
we have an m-fold dominating set D1 . Then, the second phase aims to connect it by
adding a connector set D2 . A natural potential function for connection is p(D1 ∪ D2 ), the
number of components of G[D1 ∪ D2 ]. That is, every iteration chooses a node set S to
be added into D2 which reduces the number of components by the largest amount until
p(D1 ∪ D2 ) reaches 1. It is a folklore result (see Lemma 5.5) that simultaneously adding
at most two nodes can reduce the number of components (even when ading any single
node does not reduce the number of components). So, it is natural to use
max{− △S p(D1 ∪ D2 )/c(S) : S ⊆ V \ (D1 ∪ D2 ), 1 ≤ |S| ≤ 2}

(2)

to work as a criterion for the choice of node set S to be added into D2 . However, choosing
at most two nodes might yield a solution with very bad performance ratio. Consider
the example shown in Fig.1, its optimal solution OP T = {u, v1 , . . . , S
vd } has cost opt =
1 + (d + 1)ε. If (2) is used as the greedy criterion, then the output is di=1 {ui , vi }, whose
S
cost is c( di=1 {ui , vi }) = d(1 + ε) ≈ d · opt = n−2
opt. To overcome such a shortcoming,
3
an idea is to choose some star Su to maximize − △Su p(D1 ∪ D2 )/c(Su ) in each iteration.
However, the computation of a most efficient star will take exponential time. This is why
we define p′ as in (1) to be used in the greedy criterion. On one hand, p′ also plays the
role of counting the reduction on components. On the other hand, a most efficient Su
to maximize p′D1 ∪D2 (Su )/c(Su ) can be found in polynomial time, which will be shown in
Subsection 5.2.
6

u1
v1

s
✚
✡❩
❏
✚
❩
✚ ✡ ❏ ❩
u
❝
✚ ✡
❏ ❩
✚ ❩ ❏ ❩❩
✚
❝✚ u2 ❝✡✚✚✡ ❏❩❩
❝ud−1 ❝ud
✡ ❏
❩
✚ ✡
❏
❩
✚
❩ ❝vd
❝✚ v2 ❝✡ . . . ❏ ❝vd−1

s
s
...
{z
}
d
Figure 1: Solid nodes represent nodes in C. The costs on circled nodes are c(u1 ) = c(u2 ) =
. . . = c(ud ) = 1, c(v1 ) = c(v2 ) = . . . = c(vd ) = ε, and c(u) = 1 + ε.
s

|

5

s

The Analysis of the Algorithm
In this section, we analyze the performance ratio of Algorithm 1.

5.1

The Analysis of D1

Lemma 5.1. Function q is a polymatroid.
Proof. Obviously, q(∅) = 0. It is easy to see that for any node u ∈ V , function −qC (u) is
monotone increasing and submodular with respect to C. So, function q, being the summation of a constant function and some monotone increasing and submodular functions,
is also monotone increasing and submodular.
Lemma 5.2. The final node set D1 in Algorithm 1 is an m-fold dominating set of G.
Proof. If there exists a node u ∈ V \D1 with |ND1 (u)| < m, then − △u qD1 (u) =
−qD1 ∪{u} (u) + qD1 (u) = −0 + (m − |ND1 (u)|) > 0, and − △u qD1 (v) ≥ 0 for any node
v P
∈ V \ {u} (by the monotonicity of −qD1 (v) with respect to D1 ). Thus △u q(D1 ) =
− v∈V △u qD1 (v) > 0, and the algorithm does not terminate at this stage.

Theorem 5.3. The final node set D1 in Algorithm 1 has weight w(D1) ≤ H(m + δ) · opt,
where δ is the maximum degree of graph G, and opt is the optimal value for the m-MWCDS
problem.

Proof. By Lemma 5.1 and Lemma 5.2, the minimum weight m-fold dominating set problem is a special submodular cover problem with potential function q. So by Theorem 3.1,
we have w(D1) ≤ H(γ) · opt′ , where opt′ is the optimal value for the m-MWDS problem.
Then, the result follows from the observation that opt′ ≤ opt and γ = max{q({u})} =
u∈V
P
max{m|V | − v∈V \{u} (m − |N{u} (v)|)} = max{m + dG (u)} = m + δ.
u∈V

u∈V

7

5.2

The Computation of an Optimal Star for Greedy Choice

The idea for the definition of p′C (Su ) is as follows: Adding node u into C will merge
e which reduces
those components in NCC (u) into one component of G[C ∪ {u}], say C,
the number of components by |NCC (u)| − 1. Then adding nodes in Su \ {u} sequentially
according to the increasing order of their costs. Notice that
− △ui p(C ∪ {u1 , . . . , ui−1 }) = |NCC (ui ) \ NCC (u, u1, . . . , ui−1 )|

(3)

e So, the term in the summation of
is the number of components newly merged into C.
definition (1) indicates that if adding ui merges at least one more component, we regard
its contribution to p′C (Su ) as one. The advantage of such a counting is that an optimal
star for the greedy criterion is polynomial-time computable. This claim is based on the
following lemma. A simple relation will be used in the proof: for four positive real numbers
a, b, c, d
a+b
b
a
b
≥ ⇒ ≥ .
(4)
c+d
d
c
d
Lemma 5.4. Suppose C is a dominating set of graph G. Then, there exists a most
efficient star Su with respect to C such that |NCC (v)| = 1 for every node v ∈ Su \ {u}.
Furthermore, if we denote by Cv the unique component in NCC (v), then components in
{Cv }v∈Su \{u} are all distinct and they are also distinct from those components in NCC (u).
Proof. Suppose Su is a most efficient star with Su \ {u} = {u1, . . . , us } such that c(u1 ) ≤
. . . ≤ c(us ). We first show that for any i = 1, . . . , s,
− △ui p(C ∪ {u, u1, . . . , ui−1}) ≥ 1.

(5)

Suppose this is not true. Let i be the first index with − △ui p(C ∪ {u, u1, . . . , ui−1 }) = 0.
Then by (3), we have NCC (ui ) ⊆ NCC (u, u1, . . . , ui−1 ) and thus NCC (u, u1, . . . , ui−1) =
NCC (u, u1, . . . , ui ). It follows that for any j > i,
− △uj p(C ∪ {u, u1, . . . , ui−1 , ui+1, . . . , uj−1}) = − △ui p(C ∪ {u, u1, . . . , uj−1}).
So, for the star Su′ = Su \ {ui }, we have p′C (Su′ ) = p′C (Su ) and thus p′C (Su′ )/c(Su′ ) >
p′C (Su )/c(Su ), contradicting the maximality of p′C (Su )/c(Su ).
As a consequence of (5),
p′C (Su ) = |NCC (u)| − 1 + s.
Suppose there is a node ui with |NCC (ui )| ≥ 2, we choose ui to be such that i is as
small as possible. Let Su′ = Su \ {ui }. Notice that for any j > i,
− △uj p(C ∪ {u, u1, . . . , ui−1 , ui+1 , . . . , uj−1}) ≥ − △ui p(C ∪ {u, u1, . . . , uj−1}).
Combining this with (5), we have
p′C (Su′ ) = |NCC (u)| − 1 + (s − 1) = p′C (Su ) − 1.
8

By the maximality of Su , we have
p′C (Su )
p′C (Su′ ) + 1
p′C (Su′ )
≤
=
.
c(Su′ )
c(Su )
c(Su′ ) + c(ui )
Then by (4),

p′C (Su′ )
1
≤
.
c(Su′ )
c(ui )

It follows that
1
c(Su′ ) + 1
p′C (Su′ ) + 1
1
p′C (ui )
p′C (Su )
c(ui )
=
≤
=
≤
,
c(Su )
c(Su′ ) + c(ui )
c(Su′ ) + c(ui )
c(ui )
c(ui )

where the last inequality holds because p′C (ui ) = |NCC (ui )| − 1 ≥ 1. Hence ui is a also a
most efficient star. It is a trivial star satisfing the requirement of the lemma.
Next, suppose Su is a nontrivial star in which every v ∈ Su \ {u} has |NCC (v)| = 1.
Notice that an equivalent statement of (5) is that |NCC (ui ) \ NCC (u, u1, . . . , ui−1)| ≥ 1
for any i = 1, . . . , s. The second part of this lemma follows.
By Lemma 5.4, a most efficient star with respect to C can be found in the following
way. Guessing the center of the star requires time O(n). Suppose u is the guessed center.
Let N (u) = {v : v is a neighbor of u in G and |NCC (v)| = 1}. Order the nodes in N (u)
as u1 , . . . , us such that c(u1 ) ≤ . . . ≤ c(us ). For i = 1, . . . , s, scan ui sequentially. If
ui has NCC (ui ) ⊆ NCC (u, u1, . . . , ui−1), then remove it from N (u) . For convenience of
statement, suppose the remaining set N (u) = {u1 , u2 . . . , ut}. Then, the node set of a most
efficient star centered at u must be of the form {u, u1, u2 , . . . , ul } for some l ∈ {0, . . . , t}.
So, it suffices to compute the efficiency of the t + 1 sets {u, u1, . . . , ul } for l = 0, . . . , t
and choose the most efficient one from them. Clearly, such a computation can be done in
polynomial time.

5.3

Correctness of the Algorithm

The following result is a folklore in the study of CDS (see, for example, [22]).
Lemma 5.5. Suppose D is a dominating set of G such that G[D] is not connected. Then,
two nearest components of G[D] are at most three hops away.
Theorem 5.6. The output DG of Algorithm 1 is a (1, m)-CDS.
Proof. By Lemma 5.2, D1 is an m-fold DS, and thus DG is also an m-DS. If G[DG ] is not
connected, consider two nearest components of G[DG ], say G1 and G2 . Let P = u0 u1 . . . ut
be a shortest path between G1 and G2 , where u0 ∈ V (G1 ) and ut ∈ V (G2 ). By Lemma
5.5, we have t = 2 or 3. Then, u1 (in the case t = 2) or u1u2 (in the case t = 3) is a star
Su1 with p′DG (Su1 ) > 0. The algorithm will not terminate.
9

5.4

Decomposition of Optimal Solution

The following lemma, as well as its proof, can be illustrated by Fig.2.
Lemma 5.7. Let G be a connected graph, C be a dominating set of G and C ∗ be a
connected dominating set of G. Then C ∗ \C can be decomposed into the union of node
sets C ∗ \C = Y0 ∪ Y1 ∪ Y2 ∪, . . . , ∪Yh such that:
(i) for 1 ≤ i ≤ h, subgraph G[Yi ] contains a star;
(ii) subgraph G[C ∪ Y1 ∪ Y2 ∪, . . . , ∪Yh ] is connected;
(iii) for 1 ≤ i ≤ h, |NCC (Yi )| ≥ 2;
(iv) any node of C ∗ \C belongs to at most two sets of {Y0, Y1 , Y2 , . . . , Yh }.
Proof. Let H be the graph obtained from G[C ∪ C ∗ ] by contracting every component of
G[C] into a super-node (call it a terminal node). Since G[C ∪ C ∗ ] is connected, H is also
connected, and thus H contains a spanning tree T . Recursively pruning non-terminal
leaves, we obtain a tree T ′ in which every leaf is a terminal node (see Fig.2(a)(b)). Let
Y0 be the set of pruned nodes. We may assume that
every non-terminal node has at least one terminal neighbor in T ′ .

(6)

In fact, if this is not true, then we can modify T ′ into another tree satisfying this assumption. See Fig.2(c)(d) for an illustration. In (c), node u does not have a terminal neighbor
in T ′ . Since C is a dominating set, u is adjacent with some component of G[C], say the
component corresponding to terminal node v. Adding edge uv creates a unique cycle in
T ′ + uv. Removing the edge on this cycle which is incident with u in T ′ , we have another
tree in which u has a terminal neighbor (see Fig.2(d)). Notice that the removed edge is
between two non-terminal nodes. So, the number of non-terminal nodes which have no
terminal neighbors is strictly reduced. Recursively making such a modification results in
a tree satisfying assumption (6).
Tree T ′ can be viewed as a Steiner tree. By splitting off at non-leaf terminal nodes,
T can be decomposed into full components T1′ , . . . , Tl′ (a full component in a Steiner tree
is a subtree in which a node is a leaf if and only if it is a terminal node, see Fig.6(e)). Let
Ti be the subtree of Ti′ induced by those non-terminal nodes.
′

For each i ∈ {1, . . . , l}, let vi be an arbitrary node of Ti and view Ti as a tree rooted
at vi . For each node v ∈ V (Ti ), let Sv be the star centered at node v which
Sl contains all
children of v in Ti . Let Si = {Sv : v ∈ V (Ti ) and |NCC (Sv )| ≥ 2}. Let S = i=1 Si . Then
{Yv = V (Sv ) : Sv ∈ S} is a desired decomposition of C ∗ \ (C ∪ Y0 ) (see Fig.6(f)).
It should be noted that property (6) is used to guarantee that no node is missed in
the decomposition. For example, in Fig.6(c) which does not satisfy this assumption, if we
choose x to be the root of the lower subtree, then Su = uy and Sy = y are stars which
does not have at least two terminal neighbors in T ′ , and thus they are excluded from S.
But then, node y does not belong to any star in the decomposition.
10

s
s

❝

s
s

❝

❝

❝

s

s

❝

❛❝

s

❝
❝

s

❛❝

s

s

❛❝

❛❝

❝

s
❛❝

s

s

❝

s

s

❝

s

❝

❝

vs

x❝

❝

❝

❝

s

s

s

s

❝

u❝
y❝

s

s

❝

(c)

s
s

❝

❝
s

❝

(b)

s
❝

s
❝

(a)

s

s

❝

❝

❝

❝

s

s

(d)

❝

s

s

❝ sss ❝

T1 ❝ T2
s ❝ T3 ❝
❝
s

s

s

(e)

❝

s

❝

❝

S1 ❝ S2
❝ S3 ❝

❝

❝
❝S4
❝S5

(f)

Figure 2: An example for the decomposition of C ∗ \ C. Solid nodes are terminal nodes
which correspond to components of G[C]. In (a), double circle nodes are pruned, yielding
tree T ′ in (b). Figures in (c) and (d) are used to show how to obtain a tree satisfying
assumption (6). In (c), the dashed edge uv is in G but not in T ′ . Adding edge uv and
removing edge ux results in the tree in (d). Full components of T ′ are shown in (e). Figure
(f ) shows the decomposed stars.

11

5.5

The Performance Ratio

Theorem 5.8. The connector set D2 of Algorithm 1 has cost c(D2 ) ≤ 2H(δ − 1)opt.
Proof. Let S1 , S2 , . . . , Sg be the sets chosen by Algorithm 1 in the order of their selection
(0)
into set D2 . Let DG = D1 . For 1 ≤ i ≤ g, let
(i)

(0)

DG = DG ∪ S1 ∪ . . . ∪ Si .
For i = 1, . . . , g, denote
(i−1)

ri = − △Si p(DG

) and wi =

c(Si )
(i−1)

− △Si p(DG

)

.

Suppose {Y0, Y1 , . . . , Yh } is the decomposition of OP T \ D1 as in Lemma 5.7, where
Yi is a star centered at node vi . For i = 1, . . . , g + 1 and j = 1, . . . , h, denote
ai,j = p′D(i−1) (Yj ).

(7)

G

For 1 ≤ j ≤ h, define
f (Yj ) =

g
X

(ai,j − ai+1,j )wi ,

i=1

and let

f (OP T ) =

h
X

f (Yj ).

(8)

j=1

Claim 1. For any j = 1, . . . , h, f (Yj ) ≤ H(a1,j )c(Yj ).
Since Si is chosen according to Lemma 5.4, the special structure of Si implies that
(i−1)

p′D(i−1) (Si ) = − △Si p(DG

).

G

Hence,
wi =

c(Si )
.
′
p (i−1) (Si )
DG

Then, by the greedy choice of Si , we have
c(Yj )
c(Yj )
c(Si )
.
≤ ′
=
wi = ′
p (i−1) (Si )
p (i−1) (Yj )
ai,j
DG

(9)

DG

By the definition of p′ , it can be seen that ai,j is a decreasing function on variable i. Hence
ai,j − ai+1,j ≥ 0. Combining this with (9),
f (Yj ) ≤

g
X

(ai,j − ai+1,j )

i=1

≤ c(Yj )

g
X

c(Yj )
ai,j

H(ai,j ) − H(ai+1,j )

i=1


= c(Yj ) H(a1,j ) − H(ag+1,j ) ,
12



where the second inequality uses the fact that for any integers a ≥ b,
a
a
X
X
1
1
a−b
=
≤
= H(a) − H(b).
a
a
l
l=b+1
l=b+1
(g)

Observe that ag+1,j = 0 since DG is connected, the claim follows.
Claim 2. c(D2 ) ≤ f (OP T ).
Notice that c(D2 ) and f (Yj ) can be rewritten as
!
!
!
g
g
g
g
g
g
g
X
X
X
X
X
X
X
rl (wi − wi−1 )
rl w 1 +
rl w i =
rl −
ri w i =
c(D2 ) =
i=1

i=1

l=i+1

l=i

i=2

l=1

l=i

(10)

and
f (Yj ) = a1,j w1 +

g
X

ai,j (wi − wi−1 ).

(11)

i=2

′

By the monotonicity of p , we have
greedy choice of Si−1 , we have
wi =

c(Si )
′
p (i−1) (Si )
DG

≥

p′ (i−1) (Si )
DG

≤ p′

c(Si )
′
p (i−2) (Si )
DG

≥

(i−2)

DG

(Si ). Combining this with the

c(Si−1 )
′
p (i−2) (Si−1 )
DG

= wi−1 .

In other words, wi − wi−1 ≥ 0 for i = 1, . . . , g. Then, by (8), (10), and (11), it can be
seen that to prove Claim 2, it suffices to prove that for i = 1, . . . , g,
h
X

ai,j ≥

j=1

g
X

rl .

(12)

l=i

The right hand side is
g
X
l=i

rl =

g
X
l=i

(l−1)
−△Sl p(DG )

=

g
X

(l−1)

p(DG

l=i

(l) 
(i−1)
(g)
(i−1)
)−p(DG ) = p(DG )−p(DG ) = p(DG )−1.

So, proving (12) is equivalent to proving
h
X
j=1

(i−1)

p′D(i−1) (Yj ) + 1 ≥ p(DG

).

(13)

G

This inequality can be illustrated by Fig.3. In this figure, OP T is decomposed into four
stars. A comprehension for the value p′D (Y1 ) = 3 is that in Fig.3(c), the double circled
e
components are merged into the triangled component. Call the new component as C.
′
Then, the comprehension of pD (Y2 ) = 3 is that in Fig.3(d), double circled components are
merged into the triangled component. Notice that this triangled component is contained
e and thus we can regard it as C
e in our comprehension. Continue this procedure
in C,
13

sequentially in such a way that Y1 ∪ . . . ∪ Yl is connected for l = 1, . . . , 4. Finally, all
components of G[D] are merged into one component, the reduction on the number of
components is p(D) − 1. Notice that the inequality might be strict because some components are counted more than once in the summation part. For example, the component
labeled by u4 is repetitively counted.
ut1

ut2

u4 t

ut3
S❞1

❞

v1

u5 t

❞v2

v4 ❞

❞v3

v5 ❞

t❣

❞
❞

t❣

❞
❞

S2

S4

❞

t

❞
❞

❞

❞

❞ S3

u6 t u7 t u8 t u9 t
(a)

(b)

(c)

t
△

t
△

❣
t

❞

❞
t
△

❞
❣
t

t

t
△

t❣

t❣

t
△
❞

t❣

t

❞
t❣

(d)

(e)

(f)

Figure 3: An illustration for inequality (13). Solid circles indicate components.
Claim 2 is proved.
By Lemma 5.7 (iv), we have
h
X

c(Yi ) ≤ 2opt.

(14)

i=1

Then by Claim 1, Claim 2, and the observation that a1,j ≤ δ − 1, we have
c(D2 ) ≤

h
X

c(Yj )H(δ − 1) ≤ 2H(δ − 1)opt.

j=1

The theorem is proved.
Combining Theorem 5.3 and Theorem 5.8, we have the following result.

Theorem 5.9. Algorithm 1 is a polynomial-time H(δ + m) + 2H(δ − 1) -approximation
for the m-MWCDS problem.
14

6

Implementation on Unit Disk Graphs

Notice that the maximum degree δ in the performance ratio of the second part of
the algorithm comes from a1,j ≤ δ − 1. So, to improve the approximation factor when
the graph under consideration is a unit disk graph, we improve the upper bound for a1,j
first. We use notation T1 , . . . , Tl in the proof of Lemma 5.7. Recall that each Ti has
V (Ti ) ⊆ C ∗ \ C and is decomposed into some stars, and the final decomposition of C ∗ \ C
is the union of these stars and a set of pruned nodes. We shall use k·k to denote Euclidean
length.
Lemma 6.1. In a unit disk graph, there exists a set of subtrees T1 , . . . , Tl in the proof of
Lemma 5.7 such that any node v ∈ V (Ti ) has |NCC (v)| + degTi (v) ≤ 5.
Proof. Construct a spanning tree of G[C ∪C ∗ ] as follows. First, replace each component of
G[C] by a spanning tree of that component, which is called a tree component. Then, find
a minimum length tree T which spans all nodes of C ∗ \ C and all tree components, where
“minimum length” is with respect to Euclidean distance. For convenience of statement,
we shall call a tree which spans all nodes of C ∗ \ C and all tree components as a valid tree.
Each component of G[C] is called a component node of such a tree and is dealt with as a
whole in the following. Similarly to the proof of Lemma 5.7, by pruning leafs in C ∗ \ C
and by splitting off at component nodes, we obtain a set of full components T1′ , . . . , Tl′ .
Let Ti be the subtree of Ti′ with component nodes removed. We choose tree T such that
l
X
X

degTi (u) is as small as possible.

(15)

i=1 u∈V (Ti )

Suppose there is a node v ∈ V (Ti ) with |NCC (v)|+degTi (v) = t > 6, assume NCC (v)∪
NTi (v) = {x1 , . . . , xt }, where xj is a node in C ∗ \ C or a node in a component neighbor
of v (if v is adjacent with more than one node of a component neighbor, only one node
of that component neighbor is chosen to appear in {x1 , . . . , xt }), and x1 , . . . , xt are in a
clockwise order around node v. Since t > 6, there is an index j with ∠xj vxj+1 < π/3
(xt+1 is viewed as x1 ). Then kxj xj+1 k < max{kvxj k, kvxj+1k}, say kxj xj+1 k < kvxj k.
Replacing edge vxj by xj xj+1 , we obtain another valid tree whose Euclidean length is
shorter than T , a contradiction. So,
every node v ∈ V (Ti ) has |NCC (v)| + degTi (v) ≤ 6.

(16)

A node u with |NCC (v)| + degTi (v) = 6 is called bad.
Similar argument shows that for any bad node v ∈ V (Ti ), ∠xj vxj+1 = π/3 for j =
1, . . . , 6 and kvx1 k = · · · = kvx6 k. In other words, x1 , . . . , x6 locate at the corners of a
regular hexagon with center v. First, suppose node v has a component neighbor, say x1 is
in a component neighbor of v. If x2 ∈ C, then x2 must be in a same component of G[C] as
x1 , because kx1 x2 k = kvx1 k ≤ 1, contradicting our convention that one component has at
most one node appearing in {x1 , . . . , x6 }. So, x2 ∈ C ∗ \ C. Then, Te = T − {vx2 } + {x1 x2 }
15

P P
is a valid tree with the same length as T . Notice that li=1 u∈V (Ti ) degTi (u) is decreased
by two (edge x1 x2 does not contribute to the degree sum since one of its end is in a
component neighbor and thus does not belong to Ti ), contradicting the choice of T (see
(15)). So, for j = 1, . . . , 6, xj ∈ C ∗ \ C. Since Te = T − {vxj−1 , vxj+1} + {xj xj−1 , xj xj+1 }
is also a valid tree whose length is the same as T , we have |NCC (xj )| + degTei (xj ) ≤ 6. By
noticing that degTei (xj ) = degTi (xj ) + 2 (since both xj−1 , xj+1 ∈ C ∗ \ C), we have
|NCC (xj )| + degTi (xj ) ≤ 4.

(17)

This inequality holds for any j = 1,P
. . . , 6.PNotice that Tb = T P
− {vxP
1 } + {x1 x2 } is a valid
l
l
deg
(u)
=
tree with the same length as T and i=1 u∈V (Tbi )
i=1
u∈V (Ti ) degTi (u). By
Tbi
property (16) and (17), we have

 |NCC (u)| + degTi (u) − 1 ≤ 5, u = v,
|NCC (u)| + degTbi (u) =
|NCC (u)| + degTi (u) + 1 ≤ 5, u = x1 or x2 ,

|NCC (u)| + degTi (u) ≤ 6,
u 6= v, x1 , x2 .

So, the number of bad nodes in Tb is strictly reduced. By recursively executing such an
operation, we have a tree satisfying the requirement of this lemma.

Recall that condition (6) plays an important role in the decomposition. This does no
pose any difficulty here, because by the modification method in the proof of Lemma 5.7,
if u ∈ C ∗ \ C is not adjacent with any component neighbor in T ′ , then we may just add an
edge between u and a component neighbor, and remove an edge between u and another
node in C ∗ \ C. Such an operation does not increase the value of |NCC (u)| + degTi (u).

Theorem 6.2. When applied to unit disk graphs, the node set D2 produced by Algorithm
1 has cost c(D2 ) ≤ 3.67opt.
Proof. Let T1 , . . . , Tl be the subtrees in Lemma 6.1. Choose node vi = arg max{c(v) : v ∈
V (Ti )} to be the root of Ti . Decompose C ∗ \ C as in the proof of Lemma 5.7. Let
(i)
{Yv } be the set of stars coming from the decomposition of Ti . To avoid ambiguity, we
(i)
use a1,Yv(i) to denote p′D1 (Yv ) (which is a1,j in the proof of Theorem 5.8). By Lemma
6.1, if v = vi , then a1,Yv(i) ≤ |NCD1 (v)| − 1 + degTi (v) ≤ 4; if v 6= vi , then a1,Yv(i) ≤
|NCD1 (v)| − 1 + degTi (v) − 1 ≤ 3 (this is because the parent of v is not in Yv if v 6= vi ).
Notice that vi belongs to exactly one star in the decomposition of C ∗ \ C. Hence
inequality (14) can be improved to
l X
X
i=1

c(Yv(i) )

+

l
X

c(vi ) ≤ 2opt.

(18)

i=1

(i)
Yv

Combining Lemma 6.1 with Claim 1 and Claim 2 of Theorem 5.8,


l X
l
X
X
X
H(4)c(Yv(i) ) + H(3)
c(D2 ) ≤
c(Yv(i) )H(a1,Yv(i) ) ≤
c(Yv(i) ) .
i
i=1 Y (i)
v

i=1

(i)

Yv ,v6=vi

16

(19)

Since D1 is an m-fold dominating set, every vi has at least one component neighbor.
(i)
Then by Lemma 6.1, degTi (vi ) ≤ 4, and thus Yvi has at most five nodes. Since vi has the
(i)
maximum cost in Ti , we have c(Yvi ) ≤ 5c(vi ). So,
(i)


c(Yvi )
(i)
≤ H(3)c(Yv(i)
)
+
5c(v
)/4
<
H(3)
c(Y
)
+
c(v
)
.
=
+
i
i
vi
i
4
Combining this inequality with (18) and (19),


l X
l
X
X
c(D2 ) ≤ H(3) 
c(vi ) ≤ 2H(3)opt < 3.67opt.
c(Yv(i) ) +
H(4)c(Yv(i)
)
i

H(3)c(Yv(i)
)
i

i=1 Y (i)
v

i=1

The theorem is proved.

7

Conclusion

In this paper, we presented a (H(δ + m) + 2H(δ − 1))-approximation algorithm for the
minimum weight (1, m)-CDS problem, where δ is the maximum degree of the graph. Compared with the 1.35 ln n-approximation algorithm for the minimum (1, 1)-CDS problem
[12], our constant is larger. However, since in many cases, the maximum degree is much
smaller than the number of nodes, our result is an improvement on the performance ratio
in some sense. In particular, the replacement of n by δ in the performance ratio makes
it possible to obtain a 3.67-approximation for the connecting part when the topology of
the network is a unit disk graph. In fact, Zou et al. obtained a 2.5ρ-approximation for
the connecting part in a unit disk graph, where ρ is the performance ratio for the minimum Steiner tree problem. If the best ρ = 1.39 is used, their algorithm has performance
ratio 3.475. Notice that the 1.39-approximation algorithm for the minimum Steiner tree
problem uses a combination of iterated rounding and random rounding. Our algorithm
has the advantage of purely combinatorial and deterministic. Furthermore, we expect our
method to have a theoretical value which can be used to deal with other problems.

Acknowledgements
This research is supported by NSFC (61222201,11531011), SRFDP (20126501110001),
and Xingjiang Talent Youth Project (2013711011). It is accomplished when the second
author is visiting National Chiao Tung University, Taiwan, sponsored by “Aiming for
the Top University Program” of the National Chiao Tung University and Ministry of
Education, Taiwan.

References
[1] Byrka J, Grandoni F, Rothvoss T, Sanità L (2013) J. ACM, 60(1), Article 6.
17

[2] Cheng X, Huang X, Li D, Wu W, Du DZ (2003) A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks.
Networks, 42(4), 202–208.
[3] Dai F, Wu J (2006) On constructing k-connected k-dominating set in wireless ad hoc
and sensor networks. J Parallel Distrib Comput 66(7), 947–958.
[4] Das B, Bharghavan V (1997) Routing in ad-hoc networks using minimum connected
dominating sets. IEEE International Conference on Comunications, Montreal, 376–
380.
[5] Du DZ, Graham RL, Pardalos PM, Wan PJ, Wu WL, Zhao W (2008) Analysis of
greedy approximation with nonsubmodular potential functions. SODA’08, 167–175.
[6] Du DZ, Ko K, Hu X (2012) Design and analysis of approximation algorithms.
Springer, New York.
[7] Du DZ, Wan PJ (2013) Connected Dominating Set: Theory and Applications,
Springer, New York.
[8] Ephremides A, Wieselthier J, Baker D (1987) A design concept for reliable mobile
radio networks with frequency hopping signaling. Proc IEEE 56–73.
[9] Fukunage T (2015) Constant-approximation algorithms for highly-connected multidominating sets in unit disk graphs. arXiv:1511.09156.
[10] Gao X, Wang Y, Li X, Wu W (2009) Analysis on theoretical bounds for approximating dominating set problems. Discrete Math. Algo. Appl., 1(1), 71–84.
[11] Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets.
Algorithmica, 20(4), 374–387.
[12] Guha S, Khuller S (1999) Improved methods for approximating node weithed steiner
trees and connected dominating sets. Information and Computation 150, 57–74.
[13] Li J, Jin Y (2015) A PTAS for the weighted unit disk cover problem. ICALP’15.
[14] Li M, Wan P, Yao F (2009) Tighter approximation bounds for minimum CDS in
wireless ad hoc networks. ISAAC’09, LNCS 5878, 699–709.
[15] Li Y, Wu Y, Ai C, Beyah R (2012) On the construction of k-connected m-dominating
sets in wireless networks. J. Comb. Optim. 23, 118–139.
[16] Robins G, Zelikovsky A (2000) Improved Steiner tree approximation in graphs.
SODA’00, 770–779.
[17] Ruan L, Du H, Jia X, Wu W, Li Y, Ko K (2004) A greedy approximation for minimum
connected dominating sets. Theor. Comput. Sci. 329(1), 325–330.
[18] Shang W, Yao F, Wan P, Hu X (2008) On minimum m-connected k-dominating set
problem in unit disc graphs. J. Comb. Optim. 16, 99–106.
18

[19] Shi Y, Zhang Y, Zhang Z, Wu W (2016) A greedy algorithm for the minimum 2connected m-fold dominating set problem. J. Comb. Optim. 31, 136–151.
[20] Shi Y, Zhang Z, Mo Y, Du D-Z (2017) Approximation algorithm for
minimum weight fault-tolerant virtual backbone. IEEE/ACM Trans. Net.
doi:10.1109/TNET.2016.2607723. in Unit Disk Graphs
[21] Thai M, Zhang N, Tiwari R, Xu X (2007) On approximation algorithms of kconnected m-dominating sets in disk graphs. Theor. Comput. Sci. 385, 49–59.
[22] Wan PG, Alzoubi KM, Frieder O (2002) Distributed construction of connected dominating set in wireless ad hoc networks. INFOCOM’02 1597–1604, Mobile Networks
and Applications, 9, 141–149.
[23] Wan PJ, Wang L, Yao F (2008) Two-phased approximation algorithms for minimum
CDS in wireless ad hoc networks. ICDCS’08, 337–344.
[24] Wang F, Thai M, Du DZ (2009) On the construction of 2-connected virtual backbone
in wireless networks. IEEE Trans. Wirel. Commun. 8(3), 1230–1237.
[25] Wang W, Kim D, An M, Gao W, Li X, Zhang Z, Wu W (2013) On construction
of quality fault-tolerant virtual backbone in wireless networks. IEEE/ACM Trans.
Netw. 21(5), 1499–1510.
[26] Wang W, Liu B, Kim D, Li D, Wang J, Jiang Y (2015) A better constant approximation for minimum 3-connected m-dominating set problem in unit disk graph using
Tutte decomposition, to appear in INFOCOM’15.
[27] Wu W, Du H, Jia X, Li Y, Huang S (2006) Minimum connected dominating sets and
maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352, 1–7.
[28] Zhang Z, Gao X, Wu W, Du DZ (2009) A PTAS for minimum connected dominating
set in 3-dimensional wireless sensor networks. J. Glob. Optim. 45, 451–458.
[29] Zhang Z, Willson J, Wu W, Zhu X, Du DZ (2015) (3 + ε)-approximation for the minimum weight k-cover problem, in submission. A preliminary version was Computer
Communications (INFOCOM), 2015 IEEE Conference on, pp 1364–1372.
[30] Zhang Z, Liu Q, Li D (2009) Two algorithms for connected r-hop k-dominationg set.
Discrete Math. Algo. Appl. 1(4), 485–498.
[31] Zhang Z, Shi Y (2015) Approximation algorithm for minimum weight fault-tolerant
virtual backbone in homogeneous wireless sensor network. Computer Communications (INFOCOM), 2015 IEEE Conference on, pp 1080–1085.
[32] Zhang Z, Zhou J, Mo Y, Du D-Z (2016) Performance-guaranteed approximation
algorithm for fault-tolerant connected dominating set in wireless networks. INFOCOM2016.

19

[33] Zhou J, Zhang Z, Wu W, Xing K (2014) A greedy algorithm for the fault-tolerant
connected dominating set in a general graph. J. Comb. Optim. 28(1), 310–319.
[34] Zou F, Li X, Gao S, Wu W (2009) Node-weighted Steiner tree approximation in unit
disk graphs. J. Comb. Optim. 18, 342–349.
[35] Zou F, Wang Y, Xu X, Du H, Li X, Wan P, Wu W (2011) New approximations
for weighted dominating sets and connected dominating sets in unit disk graphs.
Theoret. Comput. Sci. 412(3), 198–208.

20

