arXiv:1511.09156v1 [] 30 Nov 2015

Constant-approximation algorithms for highly connected
multi-dominating sets in unit disk graphs
Takuro Fukunaga
National Institute of Informatics, Japan
JST, ERATO, Kawarabayashi Large Graph Project, Japan
takuro@nii.ac.jp
Abstract
Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating
set ((k, m)-CDS) is defined as a subset S of V such that each node in V \ S has at least m neighbors in
S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum
weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS
problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been
actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in
a wireless ad hoc network. However, constant-approximation algorithms are known only for k ≤ 3 in the
unweighted (k, m)-CDS problem, and for (k, m) = (1, 1) in the weighted (k, m)-CDS problem. In this
paper, we consider the case in which m ≥ k, and we present a simple O(5k k!)-approximation algorithm
for the unweighted (k, m)-CDS problem, and a primal-dual O(k2 log k)-approximation algorithm for the
weighted (k, m)-CDS problem. Both algorithms achieve constant approximation factors when k is a fixed
constant.

1

Introduction

Compared with a traditional communication network, a wireless ad hoc network has the advantage of not
requiring any infrastructure, such as base stations and WiFi routers; this is a great benefit when operating
sensor networks, vehicle networks, or networks in disaster areas. However, for efficient operation of a wireless
ad hoc network, we have to overcome many technical challenges. One of these is to reduce the redundant
communication caused by flooding messages. Since it is difficult to maintain information over an entire
wireless ad hoc network, when a message is sent from one node to another, it is common practice to flood
the message to all nodes in the network. This uses more power than is necessary, and lowers the efficiency
of the network.
A typical solution to the inefficiency due to flooding is to construct a virtual backbone network, as follows:
we choose several backbone nodes from the network, and then we construct a subnetwork that comprises
only these backbone nodes. When a message arrives, first, it is delivered to a backbone node, next, it is
flooded to all the backbone nodes via the virtual backbone network, and finally, the destination node receives
the message from an adjacent backbone node. This improves energy efficiency more as the virtual backbone
network is smaller. However, it is also important that the virtual backbone network be fault tolerant.
Developing algorithms for constructing a virtual backbone network is an active area of research. A
promising approach is to formulate a virtual backbone network as a connected dominating set (CDS), and
to consider an algorithm for finding a minimum cardinality or a minimum weight CDS. For an undirected
graph with a node set V , a CDS is defined as a subset S of V such that each node in V \ S is adjacent to at
least one node in S, and S induces a connected subgraph. This approach has gained in popularity, and many
proposals have been published. It is typically assumed that the input graph is a unit disk graph, which is a
1

natural choice for modeling a wireless network. Since the problem of finding the minimum cardinality CDS
is NP-hard even for unit disk graphs [8], some studies have considered approximation algorithms.
A CDS does not give a fault-tolerant virtual backbone network. This is because a CDS is only required
to be connected, and each node outside a CDS is required to have only one neighbor in the CDS. Hence, if a
backbone node fails, the virtual backbone network may be disconnected, or a non-backbone node may lose
access to the virtual backbone network. To overcome this disadvantage, Dai and Wu [9] proposed replacing a
CDS by a k-connected k-dominating set, and they addressed the problem of finding a minimum k-connected
k-dominating set in a unit disk graph. A subset S of the node set V is called k-connected if the subgraph
induced by S is k-connected (i.e., it is connected even if any k − 1 nodes are removed), and is called kdominating if each node v ∈ V \ S has k neighbors in S. Triggered by their study, much attention has been
paid to this problem, extending the notion of a k-connected k-dominating set to a more-general k-connected
m-dominating set ((k, m)-CDS).
The problem of finding a minimum cardinality (k, m)-CDS in a unit disk graph is called the unweighted
(k, m)-CDS problem. If each node is given a nonnegative weight, and the objective is to minimize the weight
of a (k, m)-CDS, then this is called the weighted (k, m)-CDS problem. As for the unweighted (k, m)-CDS
problem, a constant-approximation algorithm was given by Shang et al. [17] for k ≤ 2, and by Wang et al.
[20] for k = 3. The latter algorithm was improved by Wang et al. [21]. We note that the analysis of the
algorithm for k = 2 in [17] contains an error, and thus the approximation factor given therein is not correct;
although this is not our main focus, it will be explained in Appendix A. As for the weighted (k, m)-CDS
problem, there are several constant-approximation algorithms for k = m = 1, but we are aware of no previous
studies that investigate the case of (k, m) 6= (1, 1).
After these previous studies, a natural question arises as to whether there is a constant-approximation
algorithm for the unweighted (k, m)-CDS problem with k ≥ 4, and for the weighted problem with (k, m) 6=
(1, 1). For the unweighted problem, this question has been already addressed in both [20] and [21]. We
answer this question affirmatively. The main contribution of this paper is to present constant-approximation
algorithms for both the unweighted and the weighted (k, m)-CDS problems when k is a constant and k ≤ m.
Specifically, we present two algorithms; one is an O(5k k!)-approximation algorithm for the unweighted
(k, m)-CDS problem, and the other is an O(k 2 log k)-approximation algorithm for the weighted (k, m)-CDS
problem. Notice that both algorithms achieve a constant factor if k is a constant. The approximation factor
of the latter algorithm is better than that of the former, and it can be applied to the weighted problem,
while the former algorithm is restricted to the unweighted problem. However, the former algorithm is
simple, easy to analyze, and can also be applied to other graph classes. In fact, for k ∈ {2, 3}, the former
algorithm is obtained by introducing more specification into the algorithms given in [17, 21]. Hence our
analysis on the former algorithm gives a simple proof for the fact that the algorithms in [17, 21] achieve
Constant-approximation for k ∈ {2, 3}.
Figure 1 shows a (4, 4)-CDS computed by our O(k 2 log k)-approximation algorithm in a unit disk graph
on 400 nodes. Square nodes represent the 161 nodes chosen to be part of the (4, 4)-CDS.

1.1

Organization

The remainder of this paper is organized as follows. Section 2 surveys related works. Section 3 introduces
preliminaries facts used in this paper. Section 4 presents our O(5k k!)-approximation algorithm for the unweighted (k, m)-CDS problem. Section 5 provides our O(k 2 log k)-approximation algorithm for the weighted
(k, m)-CDS problem. Section 7 concludes the paper. Appendix A rectifies the analysis on the algorithm of
Shang et al. [17] for the unweighted (2, m)-CDS problem.

2

Figure 1: A (4, 4)-CDS computed by the O(k 2 log k)-approximation algorithm in a unit disk graph on 400
nodes

2

Related works

The study of the (1, 1)-CDS problem for general graphs was initiated by Guha and Khuller [13]. They
presented an O(H(∆))-approximation algorithm for the unweighted (1, 1)-CDS problem in graphs with
maximum degree ∆, where H(∆) denotes the ∆-th harmonic number. They also gave a reduction from the
set cover to the unweighted (1, 1)-CDS problem, which shows that no polynomial-time algorithm achieves an
approximation factor (1 − )H(∆) for any fixed  ∈ (0, 1) unless NP ⊆ DTIME[nO(log log n) ]. For the weighted
(1, 1)-CDS problem, they gave an O(log n)-approximation algorithm, where n is the number of nodes in the
given graph.
The unweighted (1, 1)-CDS problem is NP-hard, even in unit disk graphs [8]. Marathe et al. [15] showed
that the unweighted (1, 1)-CDS problem in unit disk graphs admits a 10-approximation algorithm. This has
been improved by subsequent studies, and the current best result is due to Cheng et al. [5], who gave a
polynomial-time approximation scheme (PTAS) for the unweighted (1, 1)-CDS problem in unit disk graphs;
note that the existence of a PTAS means that for any fixed constant  > 0, there exists a (1+)-approximation
algorithm that runs in polynomial time.
The first constant-approximation algorithm for the weighted (1, 1)-CDS problem in unit disk graphs was
due to Ambühl et al. [2]. The current best approximation factor for the same problem is (4 + ). This
is achieved by combining the (3 + )-approximation algorithm due to Willson et al. [22] for the minimum
weight 1-cover problem, and the (1+)-approximation algorithm due to Zou et al. [25]. for the node-weighted
Steiner tree problem.
The first study of the (k, m)-CDS problem was conducted by Dai and Wu [9]. They found several
heuristic algorithms for the unweighted problem with k = m in unit disk graphs. Thus far, several constantapproximation algorithms have been given for the unweighted (k, m)-CDS problem in unit disk graphs. For
example, the algorithm of Thai et al. [18] is for k = 1, the algorithm of Wang, Thai, and Du [19] is for
(k, m) = (2, 1), and the algorithm of Wang et al. [20] is for k = 3. The current best result is due to
Shang et al. [17] for k ≤ 2, and due to Wang et al. [21] for k = 3. Several previous papers claimed constantapproximation algorithms for k ≥ 4, but Kim et al. [14] showed that all of them had technical errors. As far
as we know, there is no known constant-approximation algorithm for the unweighted (k, m)-CDS problem
with k ≥ 4 or for the weighted (k, m)-CDS problem with (k, m) 6= (1, 1). For the weighted problem, it is
not even known whether a constant-approximation algorithm exists for the problem of finding a minimum
weight m-dominating set in a unit disk graph when m > 1.
We note that distributed algorithms for the unweighted (1, 1)-CDS problem are also actively being studied.
Since this paper will focus on centralized algorithms, we will only refer to a few of these studies [1, 11, 23].

3

3

Preliminaries

Let α ≥ 1. An algorithm for a minimization problem is called an α-approximation if it always outputs
a feasible solution whose objective value is at most α times the optimal value for any feasible instance.
If an algorithm is an α-approximation, α is called the approximation factor of this algorithm. When the
approximation factor is a constant, the algorithm is called a constant-approximation algorithm.
Let G = (V, E) be an undirected graph with a node set V and an edge set E. For X ⊆ V , let G[X]
denote the subgraph of G induced by X; i.e., its node set is X and the edge set consists of the edges that
join nodes in X. Throughout the paper, on the power set of V , we define maximality and minimality with
respect to inclusion. In other words, X is minimal in a family V ⊆ 2V if there is no Y ∈ V with Y ⊂ X, and
X is maximal in V if there is no Y ∈ V with X ⊂ Y .
In a unit disk graph, each node is placed on the two-dimensional Euclidean space, and two nodes are
joined by an edge if and only if the distance between them is not larger than a unit length. The following
property of unit disk graphs is well known, and it is used in [17].
Lemma 1. Let G = (V, E) be a unit disk graph. Let v ∈ V , and let u1 , . . . , u6 be distinct neighbors of v.
Then E includes an edge that joins two nodes in {u1 , . . . , u6 }.
For the most part, our algorithms will require only the property stated in Lemma 1; the exception is the
algorithm for computing a minimum weight m-dominating set, presented in Section 5.1.
For X ⊆ V , we denote the set of neighbors of X in G by Γ(X). In other words, Γ(X) = {v ∈ V \ X : uv ∈
E for some u ∈ X}. We also let X + denote X ∪ Γ(X) for any X ⊆ V . For X, T ⊆ V , we simply denote
Γ(X) ∩ T by ΓT (X). The following property of the function Γ has been frequently used in previous works
on the survivable networks design (see e.g., [16]). Here, we provide a proof for completeness.
Lemma 2. For any X, Y, T ⊆ V , the following hold:
|ΓT (X)| + |ΓT (Y )| ≥ |ΓT (X ∩ Y )| + |ΓT (X ∪ Y )|,

(1)

|ΓT (X)| + |ΓT (Y )| ≥ |ΓT (X \ Y + )| + |ΓT (Y \ X + )|.

(2)

Proof. We prove (1) by counting the contribution of each node v ∈ T to each side. Let v ∈ ΓT (X ∩ Y ).
Since v has a neighbor in each of X and Y , v belongs to either X or ΓT (X), and to either Y or ΓT (Y ).
If v is contained in both ΓT (X) and ΓT (Y ), then v 6∈ X ∪ Y holds, and hence v ∈ ΓT (X ∪ Y ). Next, let
v ∈ ΓT (X ∪ Y ). Then v 6∈ X ∪ Y , and v has a neighbor in X ∪ Y . If v has a neighbor in X ∩ Y , then v is
contained in both ΓT (X) and ΓT (Y ), and v ∈ ΓT (X ∩ Y ) holds. Otherwise, v is contained in either ΓT (X)
or ΓT (Y ). In sum, if a node is counted at least once on the right-hand side of (1), it is also on the left-hand
side. If the right-hand side counts a node twice, then the left-hand side does, too. Thus, (1) holds.
To prove (2), let Y 0 denote V \ Y + . Then ΓT (Y ) = ΓT (Y 0 ), and X \ Y + = X ∩ Y 0 holds. In what follows,
we prove that Y \ X + = V \ (X ∪ Y 0 )+ holds. Since ΓT (V \ (X ∪ Y 0 )+ ) = ΓT (X ∪ Y 0 ), this means that (2)
can be proven by applying (1) to X and Y 0 .
Y \ X + ⊆ V \ (X ∪ Y 0 )+ holds because the nodes in Y \ X + are not contained in X ∪ Y 0 , and none has a
neighbor in X (otherwise v ∈ X + ) or in Y 0 (otherwise Y 0 has a node in Y + ). Let v ∈ V \ (X ∪ Y 0 )+ . Then
v is in neither X + nor (Y 0 )+ , and v 6∈ (Y 0 )+ implies v ∈ Y . Hence, V \ (X ∪ Y 0 )+ ⊆ Y \ X + holds.
Let X ⊆ V . For T ⊆ V , X is called a T -cut if X ⊆ T and X 6= ∅ 6= T \ X + , and it is called a Steiner
T -cut if X ∩ T 6= ∅ =
6 T \ X + . For T ⊆ V and r ∈ T , a T -cut X (resp., a Steiner T -cut X) is called a
(T, r)-cut (resp., Steiner (T, r)-cut) if r 6∈ X + .
A graph G is k-connected when it is connected even when any k − 1 or fewer nodes are removed from
the graph. We note that a graph on at most k nodes is k-connected by definition if it is a complete graph.
By Menger’s theorem, a graph G is k-connected if and only if |Γ(X)| ≥ k for any nonempty X ⊆ V with
X + 6= V . A subset T of V is k-connected if and only if |ΓT (X)| ≥ k for any T -cut X (recall that the
k-connectivity of T is defined by the k-connectivity of G[T ]).
4

Our algorithms take the same approach as the algorithms proposed in previous studies; they compute an
m-dominating set in the first step, and increase its connectivity by one in each of the subsequent steps. Hence,
after computing an m-dominating set, our algorithms repeat the process to solve the following problem.
Definition 1 (Augmentation problem). Given an undirected graph G = (V, E), a nonnegative weight w(v)
P
for each node v ∈ V , and a (k − 1, m)-CDS T ⊆ V , find S ⊆ V \ T that minimizes v∈S w(v), subject to
the condition that T ∪ S is k-connected.
For T ⊆ V , a path P is called a T -path if both end nodes of P are included in T , and no inner nodes of
P are included in T .
A family L of subsets of V is said to be laminar if any X, Y ∈ L satisfies X ⊆ Y , Y ⊆ X, or X ∩ Y = ∅.
L is said to be strongly laminar if any X, Y ∈ L satisfies X ⊆ Y , Y ⊆ X, or X ∩ Y + = ∅ = X + ∩ Y . Let
L be a laminar family. If X is minimal in L, we call X a leaf of L. For some Y ∈ L, if X is a maximal
member of L subject to X ⊂ Y , then we say that X is a child of Y .

4

Simple algorithm for the unweighted problem

In this section, we present an O(5k k!)-approximation algorithm for the unweighted (k, m)-CDS problem
with m ≥ k. We may assume G is k-connected, since otherwise G has no (k, m)-CDS. As noted above, our
algorithm computes an m-dominating set by applying the constant-approximation algorithm given in [17],
and it then increases the connectivity by repeatedly solving the augmentation problem.
Now let us assume that there is a (k − 1, m)-CDS T , and let us consider increasing its connectivity to
k. Since T is (k − 1)-connected, all T -cuts X satisfy |ΓT (X)| ≥ k − 1. We say a T -cut X is a demand cut
if |ΓT (X)| = k − 1. We say that a T -path P covers a demand cut X if one end node of P is in X, and the
other end node is in T \ X + .
The following lemma was used in previous studies [17, 20, 21].
Lemma 3. Let T be a (k − 1, m)-CDS, and let m ≥ k. For every demand cut X, there is a T -path that
covers X and contains at most two inner nodes.
We also need the following fundamental lemma.
Lemma 4. Let T be a (k − 1, m)-CDS, and let m ≥ k. Let S ⊆ V \ T . If a (T ∪ S)-cut X ⊆ T ∪ S satisfies
|ΓT ∪S (X)| ≤ k − 1, then X ∩ T is a demand cut.
Proof. Since T is an m-dominating set, if X ⊆ S, then |ΓT ∪S (X)| ≥ |ΓT (X)| ≥ m ≥ k holds, which
contradicts the assumption. If T ⊆ X, then X 0 := (T ∪ S) \ X + satisfies k ≤ |ΓT ∪S (X 0 )| by the same reason.
Since ΓT ∪S (X 0 ) = ΓT ∪S (X), this does not happen. Hence X ∩ T is a T -cut. The lemma is immediate from
ΓT (X ∩ T ) ⊆ ΓT (X) ⊆ ΓT ∪S (X).
A node set S ⊆ V \ T is feasible for the augmentation problem if every demand cut X is covered by a
T -path in G[S ∪ T ]. To see this, suppose that G[T ∪ S] is not k-connected. Then there exists a (T ∪ S)cut X such that |ΓT ∪S (X)| ≤ k − 1. By Lemma 4, X ∩ T is a demand cut; i.e., |ΓT (X ∩ T )| = k − 1.
Notice that ΓT (X ∩ T ) ⊆ ΓT (X) ⊆ ΓT ∪S (X). Hence, |ΓT (X ∩ T )| = k − 1 ≥ |ΓT ∪S (X)| indicates that
ΓT (X ∩ T ) = ΓT (X) = ΓT ∪S (X). This implies that G[S ∪ T ] has no T -path that covers X ∩ T .
From these observations, we can consider the following simple algorithm for the augmentation problem.
Initialize a solution S to an empty set. If T ∪ S is not k-connected, there exists a demand cut X that is
not covered by any T -path in G[T ∪ S]. The algorithm chooses such a demand cut X, and adds to S the
inner nodes of a T -path covering X that is guaranteed by Lemma 3. The algorithm repeats this until T ∪ S
becomes k-connected. In fact, this is exactly the same as the algorithms proposed in [17, 21] for k ≤ 3.
Every iteration of this algorithm adds at most two nodes to S. Hence, in order to obtain an approximation

5

guarantee for this algorithm, it is critical to analyze how many iterations are required to ensure that T ∪ S
is k-connected.
We analyze the number of iterations for a general connectivity requirement k. To do this, we make a
slight modification to the algorithm. We restrict the demand cut X that is chosen in each iteration, as
follows. Instead of an arbitrary demand cut X that is not covered by any T -path in G[T ∪ S], our algorithm
always chooses a minimal of such cuts. This procedure is described in detail as Algorithm 1.
Algorithm 1 Simple Algorithm
Input: an undirected graph G = (V, E) and a (k − 1, m)-CDS T ⊆ V with m ≥ k
Output: S ⊆ V \ T such that G[T ∪ S] is k-connected
S ←− ∅
while G[T ∪ S] is not k-connected do
X ←− a minimal demand cut that is not covered by any T -path in G[T ∪ S]
P ←− a minimum-length T -path that covers X
add the inner nodes in P to S
end while
output S
In the following theorem, we show that O(k|T |) iterations are sufficient to ensure that Algorithm 1
computes a feasible solution.
Theorem 1. Algorithm 1 outputs a solution after k(2|T | − 3) iterations.
Each iteration of Algorithm 1 adds at most two nodes to the solution. Hence, Theorem 1 immediately
implies that Algorithm 1 outputs a solution S such that |S| ≤ 2k(2|T | − 3). Let OPT denote the minimum
size of (k, m)-CDSs. If |T | ≤ αOPT, then |T ∪ S| ≤ 5kαOPT. Hence, Theorem 1 indicates that Algorithm 1
achieves an approximation factor of 5kα for the unweighted augmentation problem, if T is computed by an
α-approximation algorithm for the unweighted (k − 1, m)-CDS problem. Therefore, the following result is
obtained.
Corollary 1. There exists an O(5k k!)-approximation algorithm for the unweighted (k, m)-CDS problem in
unit disk graphs if m ≥ k.
We note that our algorithm for the augmentation problem does not rely on any property specific to unit
disk graphs, and so the result in Corollary 1 can be extended to any graph class that admits a constantapproximation algorithm for finding a minimum m-dominating set. One such example is the class of bounded
clique- and tree-width graphs [6].
In the remainder of this section, we prove Theorem 1. We begin by selecting an arbitrary node r ∈ T .
For S ⊆ V \ T , let D(r, S) denote the family of all demand cuts X such that r 6∈ X + , and X is not covered
by any T -path in G[T ∪ S].
Lemma 5. Let r ∈ T and S ⊆ V \ T . Let X, Y ∈ D(r, S). If X is minimal in D(r, S), then X ∩ Y = ∅ or
X ⊆ Y holds. If X is maximal in D(r, S), then X ∩ Y = ∅ or Y ⊆ X holds.
Proof. Suppose that some pair of X and Y violates this claim. Note that we must consider two cases: X
is minimal or maximal. In both cases, X ∩ Y 6= ∅. If X is minimal, then X 6⊆ Y , and the minimality of X
implies that Y ⊂ X does not hold. If X is maximal, then Y 6⊆ X, and the maximality of X implies that
X ⊂ Y does not hold. Hence, in both cases, ∅ 6= X ∩ Y ⊂ X ⊂ X ∪ Y holds. Also, r 6∈ (X ∪ Y )+ follows
from r 6∈ X + and r 6∈ Y + , and r 6∈ (X ∩ Y )+ follows, because (X ∩ Y )+ ⊆ (X ∪ Y )+ . Therefore, both X ∩ Y
and X ∪ Y are (T, r)-cuts.
For each T -path P in G[T ∪ S], we add an edge joining two end nodes of P to G[T ]. Let G0 denote the
graph with the node set T obtained by this operation. Consider inequality (1), where ΓT is defined with
6

respect to the graph G0 . The left-hand side of (1) is exactly 2(k − 1), because X, Y ∈ D(r, S), and the
right-hand side is at least 2(k − 1), because X ∩ Y and X ∪ Y are (T, r)-cuts. Hence, the inequality holds
with equality, and |ΓT (X ∩ Y )| = |ΓT (X ∪ Y )| = k − 1. This means that both X ∩ Y and X ∪ Y belong to
D(S, r). This contradicts the minimality or the maximality of X.
Define A as the family of demand cuts chosen in the while loop of Algorithm 1. For r ∈ T , let Ar =
{X ∈ A : r 6∈ Γ(X)}.
Lemma 6. |Ar | ≤ 2|T | − 3.
Proof. For each X ∈ Ar , we let X 0 denote T \ X + if r ∈ X, and otherwise, we denote it as X. Then X 0 is
a (T, r)-cut for any X ∈ Ar . We can prove that {X 0 : X ∈ Ar } is a laminar family on T \ {r}. The lemma
follows from this, because the size of a laminar family on the set of cardinality |T | − 1 is at most 2|T | − 3.
Suppose that there exist X, Y ∈ Ar such that X 0 ∩ Y 0 6= ∅, X 0 \ Y 0 6= ∅, and Y 0 \ X 0 6= ∅. We may assume
without loss of generality that X is chosen in an earlier iteration than that in which Y is chosen. Let S
denote the subset at the beginning of the iteration during which X is chosen. Then both X 0 and Y 0 belong
to D(r, S). If r 6∈ X, then X 0 is minimal in D(r, S), and Lemma 5 shows that X 0 ∩ Y 0 = ∅ or X 0 ⊆ Y 0 . If
r ∈ X, then X 0 is maximal in D(r, S), and Lemma 5 shows that X 0 ∩ Y 0 = ∅ or Y 0 ⊆ X 0 . In either case, this
contradicts the definitions of X and Y .
If X ∈ A does not belong to Ar for some r ∈ T , then r is contained in ΓT (X). Recall that |ΓT (X)| = k −1
Sk
for all demand cuts X. Hence, for any distinct nodes r1 , . . . , rk ∈ T , we have A = i=1 Ari , and so
Pk
|A| ≤ i=1 |Ari | ≤ k(2|T | − 3), where the last inequality follows from Lemma 6. Since Algorithm 1 iterates
|A| times, Theorem 1 has been proven.

5

Primal-dual algorithm for the weighted problem

In this section, we consider the weighted (k, m)-CDS problem. Our algorithm for this problem is also based
on a subroutine that solves the augmentation problem. We show that there is a constant-approximation
algorithm for the augmentation problem with general node weights. This algorithm is based on the primaldual method, which is a technique for computing an approximate solution from a linear programming (LP)
relaxation of the problem. Before introducing the primal-dual algorithm, we consider the weighted mdominating set problem, which demands a minimum weight m-dominating set; we prove that the problem
admits a constant-approximation algorithm.

5.1

Approximation algorithm for the weighted m-dominating set problem

Our algorithm reduces the weighted m-dominating set problem to the following geometric problem.
Definition 2 (Disk multicover problem). We are given a set P of points and a set D of disks on the
Euclidean plane, a demand d(p) for each point p ∈ P , and a nonnegative weight w(i) for each disk i ∈ D.
A subset D0 of D is called a disk cover if each point p ∈ P is contained in at least d(p) disks in D0 . The
P
problem requires finding a disk cover D0 that minimizes the weight i∈D0 w(i).
When d(p) = 1 for all p ∈ P , this is called the disk cover problem. We write p ∈ i if a point p is included
in a disk i.
Bansal and Pruhs [3] presented a constant-approximation algorithm for the disk multicover problem.
Their algorithm is an LP-rounding algorithm. That is to say, their algorithm first solves the following LP
relaxation of the problem:
P
minimize
w(i)x(i)
Pi∈D
subject to
(3)
i∈D:p∈i x(i) ≥ d(p), ∀p ∈ P,
0 ≤ x(i) ≤ 1, ∀i ∈ D,
7

P
P
then it computes a disk cover D0 that satisfies i∈D0 w(i) = O(1) · i∈D w(i)x(i) for an optimal solution x
to (3).
When m = 1, the problem of finding a minimum weight m-dominating set in a unit disk graph can be
reduced to the disk cover problem, as follows. Define D as the set of unit disks corresponding to the nodes
in the unit disk graphs, and define P as the set of the centers of the disks. The weight w(i) of a disk i ∈ D is
defined as the weight of the corresponding node in the graph. For each point p, a disk cover in this instance
includes at least one disk that contains p. This means that the set of nodes corresponding to the disks in
the disk cover is a 1-dominating set of the graph.
From the weighted m-dominating set problem with m ≥ 2, we can similarly define an instance of the
disk multicover problem; D, P , and w are defined in the same way, and the demand d(i) of each disk
i ∈ D is defined as m. By solving this instance, we can obtain an m-dominating set in the unit disk graph.
However, the minimum weight of disk covers in the obtained instance is possibly too large, compared with
the minimum weight of the m-dominating sets. To see this, let D0 be a disk cover in the obtained instance of
the disk multicover problem. The constraint in the disk multicover problem demands that each point i ∈ D0
is included in at least d(i) disks in D0 . On the other hand, in the weighted m-dominating set problem, if a
solution includes a node i, it is feasible even if it does not contain d(i) neighbors of i. In other words, the
constraint of the disk multicover problem in the constructed instance is stronger than the one demanded in
the original instance of the weighted m-dominating set problem. Accordingly, there does not seem to exist
a straightforward reduction from the weighted m-dominating set problem to the disk multicover problem.
Nevertheless, we show that the weighted m-dominating set problem in a unit disk graph can be approximated via an algorithm for the disk multicover problem. Our algorithm first solves the following LP
relaxation of the weighted m-dominating set problem:
P
minimize
w(v)x(v)
Pv∈V
subject to
(4)
u∈Γ(v)\S x(u) ≥ (m − |S|)(1 − x(v)), ∀v ∈ V, ∀S ⊆ Γ(v),
0 ≤ x(v) ≤ 1,
∀v ∈ V.
Although (4) has an exponential number of constraints, the separation can be done in polynomial time.
Namely, given x, we can judge whether x is a feasible solution for (4), as follows. For each v, sort the neighbors
Pi−m0
u1 , . . . , ui ∈ Γ(v) so that x(u1 ) ≤ · · · ≤ x(ui ). If j=1 x(uj ) ≥ (m − m0 )(1 − x(v)) for each m0 = 0, . . . , m,
Pi−m0
then the constraint defined from v and all S ⊆ Γ(v) is satisfied by x. If j=1 x(uj ) ≥ (m − m0 )(1 − x(v))
does not hold for some m0 = 0, . . . , m, then the constraint defined from v and S := {ui−m0 +1 , . . . , ui } (S := ∅
when m0 = 0) is violated by x. Hence, the separation can be done by checking whether the m + 1 inequalities
hold for each node v. Therefore, the ellipsoid method can be used to solve (4) in polynomial time.
Let x∗ denote an optimal solution for (4). We define U as {v ∈ V : x∗ (v) ≤ 1/2}. Our algorithm invokes
an algorithm for the disk multicover problem after the input is set as follows. D is defined as the set of
disks corresponding to the nodes in U , and P is defined as the set of the center of the disks in D. The
demand d(p) of the point p ∈ P corresponding to a node u ∈ U is defined as m − |Γ(u) \ U |. We solve the
obtained instance of the disk multicover problem by using an LP rounding algorithm based on (3), such as
the algorithm of Bansal and Pruhs [3]. Let D0 be the set of nodes corresponding to the disks in the obtained
approximate solution. Our algorithm outputs D0 ∪ (V \ U ) as an approximate solution for the weighted
m-dominating set problem.
Theorem 2. Our algorithm approximates the weighted m-dominating set problem in a unit disk graph
within a constant factor, if the algorithm for the disk multicover problem computes a solution of weight at
P
most O(1) · i∈D w(i)x(i) for an optimal solution x to (3).
Proof. Let OPT denote the minimum weight of the m-dominating sets, and let x∗ denote an optimal solution
P
for (4). Then, v∈V w(v)x∗ (v) ≤ OPT holds because (4) relaxes the weighted m-dominating set problem
(i.e., the incidence vector of each m-dominating set is a feasible solution to (4)).

8

For each v ∈ U , let pv and iv respectively denote the point in P and the disk in D corresponding to v.
Define x̄ ∈ [0, 1]D by x̄(iv ) = 2x∗ (v) for each v ∈ U . Then, for each v ∈ U ,
X
X
x̄(i) = 2
x∗ (u) ≥ 2(m − |Γ(v) \ U |)(1 − x∗ (v)) ≥ m − |Γ(v) \ U | = d(pv )
i∈D:pv ∈i

u∈ΓU (v)∪{v}

holds, where the first inequality follows from the constraint of (4), and the second inequality follows from
x∗ (v) ≤ 1/2. Hence, x̄ is a feasible solution to (3). The algorithm for the disk multicover problem computes
P
P
P
a solution D0 ⊆ D such that i∈D0 w(i) ≤ α i∈D w(i)x̄(i) ≤ 2α v∈U w(v)x∗ (v) for some constant α. On
P
P
the other hand, i∈V \U w(i) < 2 v∈V \U w(v)x∗ (v), because x∗ (v) > 1/2 for each v ∈ V \ U . Therefore,
P
P
∗
∗
v∈D 0 ∪(V \U ) w(v) ≤ 2α
v∈V w (v)x (v) ≤ 2αOPT.
Let u be a node that is not contained in D0 ∪ (V \ U ). Then, u has d(pu ) = m − |Γ(u) \ U | neighbors in
0
D and |Γ(u) \ U | neighbors in (V \ U ). Therefore, D0 ∪ (V \ U ) is a required disk cover.
A drawback to our algorithm is that it requires the ellipsoid method, which tends to be slow in practice.
When m ∈ {k, k +1}, this can be avoided by using the above-mentioned straightforward reduction to the disk
multicover problem. Recall that the reduction does not work in general because a node in an m-dominating
set S may not have m neighbors in S. However, when S is k-connected for some k ≥ m − 1, each node
v ∈ S has m − 1 neighbors in S. Note that v is not counted as a neighbor of v. Hence, the minimum weight
of the disk covers can be bounded by the minimum weight of the (k, m)-CDSs, and the straightforward
reduction gives an m-dominating set that has a weight within a constant factor of the minimum weight of
the (k, m)-CDSs.

5.2

Algorithm for the augmentation problem

First, let us give an overview of our algorithm for the augmentation problem. When the connectivity
requirement k is equal to one, the augmentation problem is known as the node-weighted Steiner tree problem.
For general graphs, it is hard to approximate this problem within a factor of o(log n), because it extends
the set cover problem. However, in unit disk graphs, there is a constant-approximation algorithm for the
node-weighted Steiner tree problem. Zou et al. [24] proved the existence of such an algorithm from the fact
that any unit disk graph has a spanning tree of maximum degree five. This property of unit disk graphs
is well known, and it can be shown by using the following observation: if there is a node v of degree more
than five in a spanning tree, then by Lemma 1, there is an edge uu0 that joins two neighbors u and u0 of
v. Replacing the edge vu by another edge uu0 transforms the spanning tree into another spanning tree in
which the degree of v is decreased by one (to ensure the existence of a spanning tree of maximum degree
five, we must consider the degree of u0 , because it is increased by the operation). This approach cannot be
directly extended to the general connectivity requirement k, because this operation does not preserve the
connectivity of a graph. To see this, consider the graph on seven nodes u, v1 , . . . , v6 such that v1 . . . , v6 form
a cycle of length six, and u is adjacent to each of v1 , . . . , v6 . This graph is 3-connected, and the degree of u
is six. To decrease the degree of u, replace one edge uvi by another edge vi−1 vi , and then vi will have only
two neighbors; hence, the connectivity of the graph has been decreased to two.
Nevertheless, we will show that Lemma 1 can be used to show that the augmentation problem admits
a better approximation algorithm for unit disk graphs than it does for general graphs. We will use the
lemma in the framework of primal-dual method, which has been applied successfully to many network design
problems [12]. Our algorithm repeats growing several dual variables simultaneously in an LP relaxation. This
approach has been used in the augmentation problem with node weights [4, 10], but its approximation factor
depends on the number of nodes. This is because the approximation factor is decided by the number of dual
variables that are grown simultaneously in a single constraint. In our LP relaxation of the augmentation
problem, each dual variable corresponds to a demand cut, and each constraint corresponds to a node in
the given graph. Since this number cannot be bounded, the primal-dual method does not achieve a good

9

approximation factor for general graphs, but we will show that this number can be bounded in unit disk
graphs, due to Lemma 1.
Let us explain the detail of our algorithm. We choose a root node r ∈ T , and we consider the problem
of finding a minimum weight node set S ⊆ V \ T such that every (T, r)-cut X with |ΓT (X)| = k − 1 is
covered by a T -path in G[T ∪ S]. By repeating this for k roots, we obtain an approximate solution for the
augmentation problem.
For the remainder of this subsection, we fix a root node r ∈ T . We say a Steiner (T, r)-cut X is a demand
cut if |ΓT (X)| = k − 1 (note that this is slightly different from the definition in Section 4). We denote by D
the family of all demand cuts. Observe that S is a feasible solution for the current problem defined from r if
and only if Γ(X) ∩ S 6= ∅ for each demand cut X. Thus, an LP relaxation of the problem can be formulated
as follows:
P
minimize
w(v)x(v)
Pv∈V \T
(5)
subject to
v∈Γ(X)\T x(v) ≥ 1, ∀X ∈ D,
x(v) ≥ 0,
∀v ∈ V \ T.
The dual of this LP is

P
maximize
y(X)
PX∈D
subject to
X∈D:v∈Γ(X) y(X) ≤ w(v), ∀v ∈ V \ T,
y(X) ≥ 0,
∀X ∈ D.

(6)

We say that a node v ∈ V \ T covers a demand cut X if v ∈ Γ(X), and a node set S covers X if there exists
a node v ∈ S that covers X.
A subfamily F of D is called uncrossable when (i) any X, Y ∈ F satisfy X ∩ Y, X ∪ Y ∈ F or X \
Y + , Y \ X + ∈ F, and (ii) if X ∩ Y ∩ T 6= ∅, then X ∩ Y, X ∪ Y ∈ F holds. In general, the family D is not
uncrossable. We will present a constant-approximation algorithm for the problem when D is uncrossable.
If D is not uncrossable, our algorithm finds an uncrossable subfamily F of D, and it uses the algorithm for
an uncrossable family to find a node set that covers all demand cuts in F. After adding to the solution
all the nodes in the obtained node set, the algorithm updates D, setting it equal to the residual family,
which consists of all the demand cuts that are not covered by the current solution. This is repeated until
D becomes uncrossable. We can prove that the algorithm for an uncrossable family is invoked O(k) times.
Indeed, this part of the algorithm (given in Section 5.2.1) is a straightforward application of the result
presented by Nutov [16], who used the decomposition into uncrossable subfamilies to design an algorithm
for a node-connectivity survivable network design problem.
Below, we first explain how to find an uncrossable subfamily of D when D is not uncrossable in Section 5.2.1, and then we present an algorithm for covering an uncrossable family in Section 5.2.2.
5.2.1

Decomposition into uncrossable subfamilies

We note that the result here can be found in Nutov [16]. We present detailed proofs of all results in this
subsection for completeness.
Let a min-core signify a minimal demand cut in D, and let M be the family of all min-cores. If a demand
cut X includes only one min-core as a subset (i.e., |{Y ∈ M : Y ⊆ X}| = 1), then it is called a core. The
core family of X ∈ M, denoted by C(X), is the family of cores that include X.
We first characterize the case when D and a family of cores are uncrossable.
Lemma 7.
• The core family of Z ∈ M is a ring family; i.e., for any X, Y ∈ C(Z), X ∩ Y, X ∪ Y ∈ C(Z) holds.
• Let Z, W ∈ M be distinct min-cores. If X ∈ C(Z) and Y ∈ C(W ), then X ∩ Y ∩ T = ∅.
• The family D of all demand cuts is uncrossable if and only if there are no X, Y ∈ D such that
X ∩ T ⊆ Γ(Y ).
10

S
• A family C 0 := Z∈M0 C(Z) defined from M0 ⊆ M is uncrossable if and only if there are no X, Y ∈ C 0
such that X ∩ T ⊆ Γ(Y ).
Proof. Let X, Y ∈ D. If

X ∩ Y ∩ T 6= ∅

(7)

holds, both X ∩ Y and X ∪ Y are Steiner (T, r)-cuts. In this case, the right-hand side of (1) is at least
2(k − 1). Since the left-hand side of (1) is equal to 2(k − 1), the inequality holds with equality, which implies
X ∩ Y, X ∪ Y ∈ D.
If X, Y ∈ C(Z) for some Z ∈ M, (7) always holds, because ∅ 6= Z ∩ T ⊆ X ∩ Y ∩ T . Hence, C(Z) is a
ring family. Let X ∈ C(Z) and Y ∈ C(W ) for some Z, W ∈ M with Z 6= W . If (7) holds, X ∩ Y includes a
min-core as a subset. However, this implies that X or Y includes two different min-cores as subsets, which
contradicts the fact that X and Y are cores. Therefore, the first two conditions are proven.
Next, let us prove the remaining two conditions. Let X, Y ∈ D. If X ∩ T ⊆ Γ(Y ), then neither X ∩ Y
nor X \ Y + belongs to D, because X ∩ Y and X \ Y + contain no node in T . Hence, D is not uncrossable in
this case. If X, Y ∈ C 0 and X ∩ T ⊆ Γ(Y ), for the same reason as in the previous case, C 0 is not uncrossable.
For the remainder of the proof, we will assume that X ∩ T 6⊆ Γ(Y ) and Y ∩ T 6⊆ Γ(X). In this case, (7)
or
(X ∩ T ) \ Y + 6= ∅ =
6 (Y ∩ T ) \ X +
(8)
holds. As observed above, X ∩ Y, X ∪ Y ∈ D holds when (7) holds. If (8) holds, both X \ Y + and Y \ X +
are Steiner (T, r)-cuts. Hence, as in (7), (2) holds with equality, implying X \ Y + , Y \ X + ∈ D. Therefore,
D is uncrossable.
S
Let X, Y ∈ C 0 := Z∈M0 C(Z). If X, Y ∈ C(Z) for some Z ∈ M0 , we have already seen that X ∩Y, X ∪Y ∈
C 0 holds. Suppose that X ∈ C(Z) and Y ∈ C(W ) for some distinct Z, W ∈ M0 . In this case, as seen above,
(7) does not hold, and hence (8) must hold. If X \ Y + does not include Z, then X includes two min-cores.
Since this contradicts the definition of X, we have X \ Y + ∈ C(Z) ⊆ C 0 . With similar reasoning, we can see
that Y \ X + ∈ C(W ) ⊆ C 0 . The uncrossability of C 0 follows from these relationships.
We will use max-core to denote a maximal core. We note that a ring family has a unique maximal
element, and so C(X) includes a unique max-core for each X ∈ M. Let X, Y ∈ M, and let X 0 and Y 0 be
the max-cores of C(X) and C(Y ), respectively. We say that X and Y are dependent if Y ∩ T ⊆ Γ(X 0 ), or if
X ∩ T ⊆ Γ(Y 0 ). Otherwise, X and Y are called independent. If a set of min-cores are pairwise independent,
then the union of the core families of those min-cores is uncrossable, as shown in the following lemma.
S
Lemma 8. Let M0 ⊆ M. If each pair of X, Y ∈ M0 is independent, then X∈M0 C(X) is uncrossable.
S
Proof. For brevity, let C 0 denote X∈M0 C(X). Suppose that C 0 is not uncrossable. Then, by Lemma 7, there
are two cores X, Y ∈ C 0 such that X ∩ T ⊆ Γ(Y ). Let X ∈ C(Z) and Y ∈ C(W ) for min-cores Z, W ∈ M0 .
Then Z ∩ T ⊆ X ∩ T ⊆ Γ(Y ). Let W 0 be the max-core of C(W ). Since Y ⊆ W 0 , each node in Γ(Y ) \ Γ(W 0 )
is included in W 0 . By the second condition in Lemma 7, Z ∩ W 0 ∩ T = ∅ holds. Therefore, Z ∩ T ⊆ Γ(W 0 )
holds, which means that Z and W are dependent. Since this contradicts the definition of M0 , the lemma is
proven.
Let γ := minX∈M |X ∩ T |. Note that if γ ≥ k, there is no X, Y ∈ D with X ∩ T ⊆ Γ(Y ), i.e., D is
uncrossable. Hence we consider the case of γ ≤ k − 1. In this case, we first divide the family of all cores
into 2b(k − 1)/γc + 1 uncrossable families. This can be done by dividing M into subfamilies, each of which
consists of pairwise independent min-cores. The details are explained in the following lemma.
S2k0 +1
Lemma 9. Let k 0 denote b(k − 1)/γc. There exist M1 , . . . , M2k0 +1 ⊆ M such that i=1 Mi = M and
each pair of min-cores in Mi is independent for all i = 1, . . . , 2k 0 + 1.

11

Proof. We consider a digraph whose node set is M. The digraph contains an arc from a node corresponding
to X ∈ M to another node corresponding to Y ∈ M if X ∩ T ⊆ Γ(Y 0 ), where Y 0 is the max-core in
C(Y ). The node sets in {X ∩ T : X ∈ M} are disjoint, based on the second condition in Lemma 7, and
|ΓT (Y 0 )| = k − 1 holds for each demand cut Y 0 . Hence the in-degree of each node in the digraph is at most
k 0 . Let Ḡ denote the undirected graph obtained from the digraph by ignoring the orientations of the arcs.
Any induced subgraph of Ḡ has a node of degree at most 2k 0 . It is known that the chromatic number of such
a graph is at most 2k 0 + 1. Namely, the node set of Ḡ can be decomposed into 2k 0 + 1 independent sets. If
we define Mi to be the family of min-cores corresponding to the i-th independent set in the decomposition,
then each pair of min-cores in Mi is independent.
Our algorithm repeatedly adds nodes to a solution, and when it terminates, the solution covers all the
demand cuts. At a given iteration, if the family of all demand cuts uncovered by the current solution is
not uncrossable, then the algorithm uses Lemma 9 to decompose the family of cores into 2b(k − 1)/γc + 1
uncrossable families. Then, for each of the uncrossable families, the algorithm finds nodes that cover all the
demand cuts therein, and those nodes are added to the solution. Let Di denote the family of demand cuts
that is not covered by the solution when the i-th iteration begins, and let γi denote minX∈Di |X ∩ T |. Notice
that D1 = D, and γi+1 ≥ 2γi holds because each demand cut in Di+1 includes at least two min-cores in
Pdlog(γ /(k−1))e
Di . Hence, the number of uncrossable families constructed in the algorithm is at most i=0 1
{(k −
1)/(2i γ1 ) + 1} = O(k/γ1 ). Since γ1 ≥ 1, if we have a constant-approximation algorithm for covering an
uncrossable family of demand cuts, we have an O(k)-approximation algorithm for covering all demand cuts.
5.2.2

Covering an uncrossable family of demand cuts

Here, we explain how to cover an uncrossable family F of demand cuts. First, we introduce several properties
of an uncrossable family.
Lemma 10. Let F be an uncrossable family of subsets of V . Let X, Y ∈ F. If X is a min-core of F, then
either X ⊆ Y or X ∩ Y + = ∅ = X + ∩ Y holds. In particular, if both X and Y are min-cores of F, the latter
condition holds.
Proof. We note that X ∩ Y + = ∅ = X + ∩ Y holds if and only if X ∩ Y + = ∅. Suppose that X 6⊆ Y and
X ∩ Y + 6= ∅. Since F is uncrossable, X ∩ Y, X ∪ Y ∈ F or X \ Y + , Y \ X + ∈ F holds. Note that X 6⊆ Y
implies X ∩ Y ⊂ X, and X ∩ Y + 6= ∅ implies X \ Y + ⊂ X. Hence, if either X ∩ Y ∈ F or X \ Y + ∈ F holds,
we have a contradiction with the minimality of X.
For S ⊆ V , let FS denote {X ∈ F : S ∩ Γ(X) = ∅}.
Lemma 11. If F ⊆ 2V is uncrossable, then FS is also uncrossable for any S ⊆ V .
Proof. Let X, Y ∈ FS . Since F is uncrossable, X ∩ Y, X ∪ Y ∈ F or X \ Y + , Y \ X + ∈ F holds.
Suppose that the former holds. If X ∩ Y 6∈ FS , then Γ(X ∩ Y ) includes a node v ∈ S. Since Γ(X ∩ Y ) ⊆
Γ(X) ∪ Γ(Y ), v covers X or Y . However, this contradicts the fact that X, Y ∈ FS . Hence, X ∩ Y ∈ FS .
Similarly, we can prove X ∪ Y ∈ FS , because Γ(X ∪ Y ) ⊆ Γ(X) ∪ Γ(Y ).
Next, suppose that the latter holds. We note that Γ(X\Y + ) ⊆ Γ(X)∪Γ(Y ) and Γ(Y \X + ) ⊆ Γ(X)∪Γ(Y ).
Hence, as above, we can prove that X \ Y + , Y \ X + ∈ FS .
Now we present our algorithm for covering an uncrossable family F of demand cuts. The algorithm
consists of an increase phase and a deletion phase. First, we present the increase phase. In this phase, the
algorithm maintains the following variables.
• The dual solution y. This is initialized as y(X) := 0, X ∈ F. During the increase phase, y is always a
feasible solution to (6).

12

• A solution S ⊆ V \ T . This is initialized to S:=∅. The increase phase terminates when S covers all
the demand cuts in F.
In each iteration, the algorithm simultaneously increases y(X) for each min-core X of FS . For ease of
presentation, we will consider this over time. During  units of time, y(X) is increased by  for each min-core
P
X of FS . When X∈F : v∈Γ(X) y(X) becomes equal to w(v) for some v ∈ V \ (T ∪ S), the algorithm stops
increasing y and adds v to S. After this update, if S covers all demand cuts in F, then the algorithm
terminates the increase phase and proceeds to the deletion phase. Otherwise, the algorithm proceeds to the
next iteration of the increase phase. By definition, in these steps, y is always a feasible solution to (6). At
the end of the increase phase, S covers all the demand cuts in F.
Suppose that the increase phase starts at time 0 and ends at time ∆. Let τ ∈ [0, ∆] be an instant during
the increase phase. Let Sτ , Fτ , Mτ denote S, FS , and the family of min-cores of FS , respectively, at time
τ . For each v ∈ V , let dτ (v) denote |{X ∈ Mτ : v ∈ Γ(X)}|. Let L be the family of all demand cuts X that
were in Mτ at time τ . For the analysis given below, we observe the following properties.
Lemma 12. L is strongly laminar.
Proof. Let X, Y ∈ L. Suppose that X ∈ Mτ and Y ∈ Mτ 0 for some τ ≤ τ 0 . Then, Y ∈ Fτ , because
Y ∈ Mτ 0 means that Y is not covered by Sτ . Hence, by Lemma 10, X ⊆ Y or X ∩ Y + = ∅ = X + ∩ Y
holds.
Lemma 13. If G is a unit disk graph, dτ (v) ≤ 5 holds for any v ∈ V \ T and τ ∈ [0, ∆].
Proof. Let X1 , . . . , Xdτ (v) be the members of Mτ whose neighbor sets include v. Let ui denote a neighbor
of v in Xi for each i = 1, . . . , dτ (v). Notice that by Lemma 11, Fτ is uncrossable. Thus, if i 6= j, then by
Lemma 10, Xi ∩ Xj+ = ∅ = Xi+ ∩ Xj . If dτ (v) ≥ 6, ui and uj are adjacent for some i, j ∈ {1, . . . , dτ (v)} with
i 6= j. However, this indicates that uj ∈ Xi+ , which contradicts Xj ∩ Xi+ = ∅.
In the deletion phase, the algorithm modifies S into an inclusionwise minimal node set that covers F
as follows. Let S := {v1 , . . . , v|S| }, where vi is the i-th node added to S in the increase phase for each
i = 1, . . . , |S|. The deletion phase investigates nodes vi ∈ S in decreasing order of their subscripts. If S \ {vi }
covers all demand cuts in F, vi is removed from S. Let S̃ denote S after all nodes have been investigated.
The algorithm outputs S̃ as a solution. We will show that S̃ is a 15-approximate solution.
Lemma 14. Let τ ∈ [0, ∆], and let vi ∈ S̃ with dτ (vi ) ≥ 1. There exist W ∈ Fτ and X ∈ Mτ such that
Γ(W ) ∩ (S̃ ∪ {v1 , . . . , vi }) = {vi }, vi ∈ Γ(X), and X ⊆ W or X ∩ W + = ∅ = X + ∩ W .
Proof. By the definition of the deletion phase, vi ∈ S̃ implies that there exists W ∈ F such that Γ(W ) ∩ (S̃ ∪
{v1 , . . . , vi }) = {vi }. Note that W ∈ Fτ holds because no node in {v1 , . . . , vi−1 } covers W . Since dτ (vi ) ≥ 1,
there exists X ∈ Mτ with vi ∈ Γ(X). By Lemma 10, X ⊆ W or X ∩ W + = ∅ = X + ∩ W holds.
For vi ∈ S̃, we will call (W, X) in Lemma 14 a witness pair of vi .
P
Lemma 15.
v∈S̃ dτ (v) ≤ 15|Mτ | − 5 for any τ ∈ [0, ∆].
Proof. Let v be a node in S̃ such that dτ (v) ≥ 1, from which v 6∈ Sτ follows by Lemma 13. We categorize
such a node v into two types. If there exists a witness pair (Wv , Xv ) of v such that Xv ⊆ Wv , v is said to
be of the first type; otherwise, v is said to be of the second type.
Let us count the number of nodes v of the first type. Let X ∈ Mτ . Suppose that there are two nodes of
the first type, u, v ∈ S̃, such that X = Xu = Xv . Then X ⊆ Wu ∩ Wv holds. Recall that Γ(Wu ) ∩ S̃ = {u},
Γ(Wv ) ∩ S̃ = {v}, and u, v ∈ Γ(X) ⊆ (Wu ∩ Wv )+ . These imply that Γ(Wu ∪ Wv ) ∩ S̃ = ∅. Since
Wu ∩ Wv ∩ T ⊇ X ∩ T 6= ∅, the definition of uncrossability indicates that Wu ∪ Wv ∈ F. However, this
contradicts the definition of S̃. Therefore, for each X ∈ Mτ , there exists at most one node of the first type
with Xv = X. That is to say, there are at most |Mτ | nodes of the first type.
13

Next, we count the number of nodes of the second type. Let v be a node of the second type. There
exists Y ∈ Mτ such that Y ⊆ Wv , because Wv is not covered by any node that was added to S earlier
than v in the increase phase. Since v is not the node of the first type, v is not included in Γ(Y ), and thus
S
Y 6= Xv . Let Lτ = τ 0 ∈[τ,∆] Mτ 0 . Since Lτ ⊆ L, and by Lemma 12, L is a strongly laminar family, Lτ
is a strongly laminar family. We assume that Lτ has a unique maximal member; if there is more than one
maximal member of Lτ , we add a node set V to Lτ , which has no effect on the following discussion. Let Z
be a member of Lτ such that Z became a min-core of the residual family of F when v was added to S in the
increase phase. Then v ∈ Z, and hence Xv ⊆ Z and Y ⊆ Wv ⊆ Z, because v ∈ Xv+ and v ∈ Wv+ . Let Zv be
a minimal member of Lτ such that Xv ⊆ Zv and Wv ⊆ Zv . Note that Zv has at least two children in Lτ .
Suppose that there exists a node of the second type, u ∈ S̃ \ {v}, such that dτ (u) ≥ 1 and Wv ⊆ Wu ⊂ Zv .
Then, v ∈ Wu holds, because Γ(Wu ) ∩ S̃ = {u}, and Xv ⊆ Wu because of the strong laminarity of Lτ . Since
this contradicts the definition of Zv , no such u exists. In summary, this means that the number of nodes of
P
the second type is at most Z∈Lτ :ch(Z)≥2 ch(Z), where ch(Z) denotes the number of children of Z in Lτ .
P
Since the leaf set of Lτ is Mτ , we have Z∈Lτ :ch(Z)≥2 ch(Z) ≤ 2|Mτ | − 1.
Thus, |{v ∈ S̃ : dτ (v) ≥ 1}| ≤ 3|Mτ | − 1, and dτ (v) ≤ 5 for each v ∈ S̃, and the lemma has been
proven.
Theorem 3. If F is an uncrossable family of demand cuts, there exists a 15-approximation algorithm for
finding a minimum weight node set that covers all demand cuts in F.
Proof. We will prove that the algorithm presented above is a 15-approximation algorithm. By definition,
solution
the algorithm computes a feasible solution S̃ to the problem, and a solution y ∈ RF
+ is a feasible
P
P
to (6). Since X∈F y(X) is a lower bound on the optimal value, it suffices to prove that v∈S̃ w(v) ≤
P
15 X∈F y(X).
R∆
P
When the increase phase terminates, y satisfies X∈F y(X) = 0 |Mτ |dτ . Moreover, for each node
R∆
P
d
v ∈ V \ T and τ ∈ [0, ∆], dτ
τ (v)dτ holds,
X∈F : v∈Γ(X) y(X) = dτ (v) holds. For each v ∈ S̃, w(v) = 0 dP
P
because w(v) = X∈F : v∈Γ(X) y(X) holds when the algorithm terminates. By Lemma 15, v∈S̃ w(v) =
R∆
R∆
P
P
X∈F y(X).
v∈S̃ 0 dτ (v)dτ ≤ 15 0 |Mτ |dτ = 15
Although we illustrated the algorithm by using a continuous measure of time, it can be easily discretized.
Algorithm 2 shows the details of our algorithm for covering an uncrossable family of demand cuts.

5.3

Combined decomposition and covering algorithm

We now summarize our algorithm for the augmentation problem. In Section 5.2.1, we showed that by
applying an algorithm for covering an uncrossable family of demand cuts O(k) times, we can find a node
set that covers all demand cuts. Since Theorem 3 gives a constant-approximation algorithm for covering
an uncrossable family, we have an O(k)-approximation algorithm for covering all demand cuts. Recall that
a demand cut is defined as a Steiner (T, r)-cut for a fixed r ∈ T . For covering all Steiner T -cuts X with
|ΓT (X)| = k −1, we choose k nodes r1 , . . . , rk ∈ T , and apply the algorithm fixing r to each of r1 , . . . , rk . The
union of the obtained solutions is an O(k 2 )-approximate solution for the augmentation problem. Therefore,
we arrive at the following conclusion.
Corollary 2. The augmentation problem admits an O(k 2 )-approximation algorithm. It outputs a solution
P
S such that v∈S w(v) is at most O(k 2 ) times the optimal value of (5).
The details of our algorithm for the augmentation problem are given in Algorithm 3.
For the weighted (k, m)-CDS problem, we first compute an m-dominating set T , using the algorithm
given in Section 5.1. We incrementally increase the connectivity of T by solving the augmentation problem.
This obviously gives an O(k 3 )-approximation algorithm. This approximation factor can be slightly improved,
as follows.
14

Algorithm 2 Covering algorithm for an uncrossable family of demand cuts
Input: a unit disk graph G = (V, E), T ⊆ V , a nonnegative weight w(v) of each node v ∈ V \ T , and an
uncrossable family F ⊆ D
Output: S ⊆ V \ T that covers all demand cuts in F
S ←− ∅, i ← 0
w(v) ←− w(v) for each v ∈ V \ T
while FS := {X ∈ F : S ∩ Γ(X) = ∅} =
6 ∅ do
i ←− i + 1
M ← {min-cores of FS }
d(v) ←− |{X ∈ M : v ∈ Γ(X)}| for each v ∈ V \ (T ∪ S)
α ← minv∈V \(T ∪S) w(v)/d(v)
vi ← arg minv∈V \(T ∪S) w(v)/d(v)
S ←− S ∪ {vi }
w(v) ←− w(v) − αd(v) for each v ∈ V \ (T ∪ S)
end while
for j = i − 1, . . . , 1 do
if S \ {vj } covers F, then S ← S \ {vj }
end for
output S

Algorithm 3 Algorithm for the augmentation problem
Input: Natural numbers k and m with m ≥ k, a k-connected unit disk graph G = (V, E), an m-dominating
set T ⊆ V such that G[T ] is (k − 1)-connected, and a nonnegative weight w(v) for each v ∈ V \ T
Output: S ⊆ V \ T such that G[T ∪ S] is k-connected
S ←− ∅
for k 0 = 1, . . . , k do
rk0 ←− T \ {r1 , . . . , rk0 −1 }
D ←− {X ⊆ V : T ∩ X 6= ∅, rk0 6∈ X + , |Γ(X) ∩ (T ∪ S)| = k − 1}
γ ← minX∈D |X ∩ T |
while γ ≤ k − 1 do
M ← {min-cores of D}
for each X ∈ M do C(X) ← core family of X in D
decompose M into pairwise independent families M1 , . . . , Mb(k−1)/γc ⊆ M
for i = 1, . . . , b(k − 1)/γc do
S
run Algorithm 2 for (G, T ∪ S, w, X∈Mi C(X)) to obtain Si ⊆ V \ (T ∪ S)
end for 
Sb(k−1)/γc 
S←S∪
Si
i=1
D ← {X ∈ D : Γ(X) ∩ S = ∅}
γ ← minX∈D |X ∩ T |
end while
run Algorithm 2 for (G, T ∪ S, w, D) to obtain S 0 ⊆ V \ (T ∪ S)
S ← S ∪ S0
end for
output S

15

Corollary 3. There exists an O(k 2 log k)-approximation algorithm for the weighted (k, m)-CDS problem.
Proof. Let S ∗ denote an optimal solution for the weighted (k, m)-CDS problem, and let x∗ ∈ {0, 1}V denote
its characteristic vector (i.e., x∗ (v) = 1 if v ∈ S ∗ , and x∗ (v) = 0 if v ∈ V \ S ∗ ). For each S ⊆ V , we
P
abbreviate v∈S w(v) to w(S).
We will show that the algorithm described above achieves the approximation factor O(k 2 log k). Recall
that we use the algorithm given in Corollary 2 for the augmentation problem, but with the connectivity
requirement k 0 changed from 1 to k. Let Sk0 denote the solution output by the algorithm for the augmentation
problem when the connectivity requirement is k 0 . Note that in this case, the node set T in the input is
Sk0 −1
i=0 Si , where S0 is the m-dominating set computed by the algorithm given in Section 5.1. Note that
Sk0 −1
Sk0 −1
∗
is k-connected. Hence, when T = i=0 Si , for each demand cut X, Γ(X) \ T includes
S ∪
i=0 Si
at least k − k 0 + 1 nodes in S ∗ . This implies that x∗ /(k − k 0 + 1) is a feasible solution to (5) when the
connectivity requirement is k 0 , and thus w(Sk0 ) = O(k 2 ) · w(S ∗ )/(k − k 0 + 1). For the solution output by our
algorithm for the weighted (k, m)-CDS problem, the weight is at most
k
X
k0 =0

6

w(Sk0 ) = O(k 2 ) · w(S ∗ )

k
X
k0 =0

1
= O(k 2 log k) · w(S ∗ ).
k − k0 + 1

Simulation results

We implemented our algorithms and evaluated their performance for computer simulations of the unweighted (k, m)-CDS problem. For computing a connected m-dominating set, we combined the algorithm
of Shang et al. [17] with a simple heuristic. The program computes a connected m-dominating set using
the algorithm in [17], and then transforms it to form an inclusion-wise minimal connected m-dominating set
by using a greedy method to remove nodes from the solution. After this operation, the connectivity of the
solution is increased by the algorithm in Section 4 (simple algorithm) or by the one in Section 5 (primal-dual
algorithm). We prepared two types of unit disk graphs; nodes were randomly and uniformly generated in a
square region with sides of length 100 for the first type and in a 50 by 200 rectangular region for the other.
In both types, nodes were joined by an edge if their distance was less than or equal to 20.
Figure 2 shows the sizes of the (5, 5)-CDSs computed by our algorithms. We changed the number of
nodes in the graph from 200 to 900. For the solutions computed by the simple algorithm, in the square
region, the minimum size was 84 (when |V | = 600), and the maximum was 101 (when |V | = 800); and
in the rectangular region, the minimum size was 97 (when |V | = 700), and the maximum was 109 (when
|V | = 900). For the solutions computed by the primal-dual algorithm, in the square region, the minimum
size was 81 (when |V | = 600), and the maximum was 95 (when |V | = 800); and in the rectangular region,
the minimum size was 93 (when |V | = 600), and the maximum was 103 (when |V | = 800). We conclude that
the size of the solution does not increase very much compared with the increase in the size of the graph.
Figure 3 shows the size of the (k, 6)-CDSs and the (k, k)-CDSs that were computed by the two algorithms
for k = 1, . . . , 6. Here, the graph was on 600 nodes in the rectangular region. We can see that the size of the
(k, k)-CDS increases almost linearly as k increases from 1 to 6. When the domination number is fixed at 6,
the size of the (k, 6)-CDSs increases slowly. This means that the step in which the (1, m)-CDS is computed
has more influence than the step in which the connectivity is increased. The simulation results indicate
that the heuristic we used for the construction of the (1, m)-CDS is effective. For example, when the graph
is on 600 nodes in a square region, the algorithm of Shang et al. computes a (1, 6)-CDS with 131 nodes,
and our heuristic removes 40 of those nodes. From the obtained (1, 6)-CDS with 91 nodes, the simple and
primal-dual algorithms computed (6, 6)-CDSs with 116 nodes and 113 nodes, respectively. Therefore, both
of our algorithms output (6, 6)-CDSs smaller than the (1, 6)-CDS computed by the algorithm of Shang et al.
This can be observed in each of the simulations we performed.
16

size of (5, 5)-CDSs

110
100
90
80
70
60
50
40
30
20
10
0

simple, 100 × 100
primal-dual, 100 × 100
simple, 50 × 200
primal-dual, 50 × 200
200 300 400 500 600 700 800 900
|V |

size of (k, m)-CDSs

Figure 2: Solution size for various graph sizes
120
110
100
90
80
70
60
50
40
30
20
10
0

simple, m = k
primal-dual, m = k
simple, m = 6
primal-dual, m = 6

size of (k, m)-CDSs

120
simple, m = k
110
primal-dual, m = k
100
simple, m = 6
90
1
2
3
4
5
6
80
primal-dual, m = 6
k
70
Figure 3: Solution size for various connectivity and domination numbers
60
50
In each of the above results, the solutions of the primal-dual algorithm were smaller than those of the
40in most cases, this difference was extremely small, although their approximation
simple algorithm. However,
factors were very different.
30
20
7 Conclusion 10
We presented two constant-approximation
algorithms for the unweighted (k, m)-CDS problem with k ≥ 4,
0
1 problem
2 with 3(k, m) 6=4 (1, 1) in5 unit disk
6 graphs. The first of these is
and for the weighted (k, m)-CDS

a simple algorithm that can be applied to a fairly general class of graphs, although it is restricted to the
unweighted (k, m)-CDS problem. The second is a primal-dual algorithm that has a better approximation
factor and can be applied to the weighted (k, m)-CDS problem.
Computational simulations indicated that the performance of the simple algorithm was not much worse
than that of the primal-dual algorithm, although the approximation factor of the simple algorithm was
exponential in k. This approximation factor may be too high, because our analysis was not specific to unit
disk graphs except when computing the m-dominating set. It will be an interesting future work to perform
a better analysis of the simple algorithm for unit disk graphs.
In addition to the m-dominating sets, there are many other variations of dominating sets in graphs. For
example, a subset S of a node set V is called an m-tuple dominating set if each node in the graph (including
those in S) has m neighbors in S, and it is called a vector dominating set if each node v outside of S has
d(v) nodes in S for a given |V |-dimensional vector d. Refer to [7] for other variations. Our algorithms for the
augmentation problem can be used for increasing the connectivity of these variations if each node outside
the solution has k neighbors in the solution, where k is the required connectivity.

k

17

For the weighted problem, our primal-dual algorithm requires the ellipsoid method for computing an
m-dominating set when k + 1 < m. However, the ellipsoid method is not practical, so another interesting
future work will be to invent a constant-approximation algorithm for the minimum weight m-dominating set
problem, that does not rely on the ellipsoid method.

References
[1] K. M. Alzoubi, P.-J. Wan, and O. Frieder. Message-optimal connected dominating sets in mobile ad
hoc networks. In Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking
&Amp; Computing, MobiHoc ’02, pages 157–164, New York, NY, USA, 2002. ACM.
[2] C. Ambühl, T. Erlebach, M. Mihalák, and M. Nunkesser. Constant-factor approximation for minimumweight (connected) dominating sets in unit disk graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on
Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings,
pages 3–14, 2006.
[3] N. Bansal and K. Pruhs. Weighted geometric set multi-cover via quasi-uniform sampling. In Algorithms ESA 2012 - 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings,
pages 145–156, 2012.
[4] C. Chekuri, A. Ene, and A. Vakilian. Prize-collecting survivable network design in node-weighted
graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012,
Cambridge, MA, USA, August 15-17, 2012. Proceedings, pages 98–109, 2012.
[5] X. Cheng, X. Huang, D. Li, W. Wu, and D. Du. A polynomial-time approximation scheme for the
minimum-connected dominating set in ad hoc wireless networks. Networks, 42(4):202–208, 2003.
[6] F. Cicalese, G. Cordasco, L. Gargano, M. Milanic, and U. Vaccaro. Latency-bounded target set selection
in social networks. Theoretical Computer Science, 535:1–15, 2014.
[7] F. Cicalese, M. Milanic, and U. Vaccaro. On the approximability and exact algorithms for vector
domination and related problems in graphs. Discrete Applied Mathematics, 161(6):750–767, 2013.
[8] B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Mathematics, 86(1-3):165–
177, 1990.
[9] F. Dai and J. Wu. On constructing k-connected k-dominating set in wireless ad hoc and sensor networks.
Journal of Parallel and Distributed Computing, 66(7):947–958, July 2006.
[10] T. Fukunaga. Spider covers for prize-collecting network activation problem. In Proceedings of the
Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA,
USA, January 4-6, 2015, pages 9–24, 2015.
[11] S. Funke, A. Kesselman, U. Meyer, and M. Segal. A simple improved distributed algorithm for minimum
CDS in unit disk graphs. ACM Transactions on Sensor Networks, 2(3):444–453, 2006.
[12] M. X. Goemans and D. P. Williamson. The primal-dual method for approximation algorithms and
its application to network design problems. Approximation algorithms for NP-hard problems, pages
144–191, 1997.

18

[13] S. Guha and S. Khuller. Approximation algorithms for connected dominating sets. Algorithmica,
20(4):374–387, 1998.
[14] D. Kim, W. Wang, X. Li, Z. Zhang, and W. Wu. A new constant factor approximation for computing
3-connected m-dominating sets in homogeneous wireless networks. In INFOCOM 2010. 29th IEEE
International Conference on Computer Communications, Joint Conference of the IEEE Computer and
Communications Societies, 15-19 March 2010, San Diego, CA, USA, pages 2739–2747, 2010.
[15] M. V. Marathe, H. Breu, H. B. H. III, S. S. Ravi, and D. J. Rosenkrantz. Simple heuristics for unit
disk graphs. Networks, 25(2):59–68, 1995.
[16] Z. Nutov. Approximating minimum-cost connectivity problems via uncrossable bifamilies. ACM Transactions on Algorithms, 9(1):1, 2012.
[17] W. Shang, F. Yao, P. Wan, and X. Hu. On minimum m-connected k-dominating set problem in unit
disc graphs. Journal of Combinatorial Optimization, 16(2):99–106, Dec. 2008.
[18] M. T. Thai, N. Zhang, R. Tiwari, and X. Xu. On approximation algorithms of k-connected m-dominating
sets in disk graphs. Theoretical Computer Science, 385(1-3):49–59, 2007.
[19] F. Wang, M. T. Thai, and D. Du. On the construction of 2-connected virtual backbone in wireless
networks. IEEE Transactions on Wireless Communications, 8(3):1230–1237, 2009.
[20] W. Wang, D. Kim, M. K. An, W. Gao, X. Li, Z. Zhang, and W. Wu. On construction of quality faulttolerant virtual backbone in wireless networks. IEEE/ACM Transactions on Networking, 21(5):1499–
1510, 2013.
[21] W. Wang, B. Liu, D. Kim, D. Li, J. Wang, and Y. Jiang. A better constant approximation for minimum
3-connected m-dominating set problem in unit disk graph using Tutte decomposition. In 2015 IEEE
Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1,
2015, pages 1796–1804, 2015.
[22] J. Willson, Z. Zhang, W. Wu, and D. Du. Fault-tolerant coverage with maximum lifetime in wireless
sensor networks. In 2015 IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon,
Hong Kong, April 26 - May 1, 2015, pages 1364–1372, 2015.
[23] J. Yu, L. Jia, D. Yu, G. Li, and X. Cheng. Minimum connected dominating set construction in wireless
networks under the beeping model. In 2015 IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015, pages 972–980, 2015.
[24] F. Zou, X. Li, S. Gao, and W. Wu. Node-weighted Steiner tree approximation in unit disk graphs.
Journal of Combinatorial Optimization, 18(4):342–349, 2009.
[25] F. Zou, Y. Wang, X. Xu, X. Li, H. Du, P. Wan, and W. Wu. New approximations for minimum-weighted
dominating sets and minimum-weighted connected dominating sets on unit disk graphs. Theoretical
Computer Science, 412(3):198–208, 2011.

A

Rectification of Shang et al. for the unweighted (2, m)-CDS

Shang et al. [17] gave an approximation algorithm for the unweighted (2, m)-CDS problem. They claimed
that their algorithm achieves an approximation factor of 5 + 25/m for 2 ≤ m ≤ 5, and 11 for m ≥ 6. We
agree with them that their algorithm achieves a constant approximation factor, but their claim contains an
error. In this section, we explain which part of their claim is wrong, and we provide a correct analysis on
their algorithm.
19

Let us begin with illustrating their algorithm. Let OPT denote the minimum size of (2, m)-CDSs. Let
Si−1
Ii be a maximal independent set of G[V \ i0 =0 Ii0 ] for each i = 1, . . . , m, where I0 = ∅. The algorithm
first computes I1 , . . . , Im , and C ⊆ V \ I1 such that |C| ≤ |I1 | and G[C ∪ I1 ] is connected. The following
properties are proven.
(i) |Ii | ≤ max{5/m, 1}OPT for each i = 1, . . . , m.
Si
Sm
(ii) i0 =1 Ii0 is an i-dominating set for each i = 1, . . . , m, and hence T := i=1 Ii ∪ C is a (1, m)-CDS.
(iii) Each cut-node of G[T ] is included in I1 or in C.
(iv) |T | ≤ (5 + 5/k)OPT for k ≤ 5, and |T | ≤ (7 − 5/k)OPT for k ≥ 6 (this is slightly better than the
conclusion in [17], but they proved this).
After this step, the algorithm computes a node set S such that T ∪ S is 2-connected as follows. First,
S is initialized to an empty set. Then, the algorithm computes a T -cut X such that |ΓT (X)| = 1 and no
T -path in G[T ∪ S] covers X. For this T -cut X, the algorithm finds a T -path that covers X with at most
two inner nodes, and it adds these inner nodes to the solution S. This procedure is repeated until T ∪ S
becomes 2-connected, and the algorithm outputs T ∪ S as a (2, m)-CDS.
Shang et al. [17] claimed that the number of iterations is at most the number of cut-nodes in G[T ], which
is at most |I1 | + |C| ≤ 2|I1 | ≤ 2 max{5/m, 1}OPT, due to properties (i) and (iii). Since each iteration adds
at most two nodes, when the algorithm terminates, |S| ≤ 4 max{5/m, 1}OPT. This is their analysis of the
algorithm.
However, the number of iterations is not bounded by the number of cut-nodes in G[T ]. This can be
observed by considering a star with n leaves. The star has only one cut-node. To make it 2-connected, we
need to add n − 1 paths to connect the leaves.
We claim that a correct upper-bound on the number of iterations is the number of 2-connected components
of G[T ], and this number is bounded by |I1 | + |C| + |I2 | − 1 ≤ 3 max{5/m, 1}OPT − 1.
For proving our claim, let us consider the tree F that represents the 2-connected component decomposition
of G[T ]. Namely, the node set of F is the disjoint union of two node sets B and W . Each node in B
corresponds to a 2-connected component of G[T ], and each node in W corresponds to a cut-node of G[T ].
In what follows, we identify a node in B with the corresponding 2-connected component of G[T ], and we
identify a node in W with the corresponding cut-node of G[T ]. A node b ∈ B and a node w ∈ W are joined
by an edge in F when the component b includes the cut-node w.
In each iteration of the algorithm, a T -path is selected to join two different 2-connected components of
G[T ], and the inner nodes of the path are added to the solution S. Let u and v denote the end nodes of a
T -path P , and let ρu be a 2-connected component that includes u. If more than one component includes u,
we let ρu denote the one nearest to the components including v on F ; ρv is defined in the same way. Let
x be a cut-node of G[T ], and let b and b0 be 2-connected components that include x. When the algorithm
chooses a T -path P , we add a virtual edge that joins b and b0 if x, b, and b0 are on the path between ρu and
ρv on F .
Lemma 16. T ∪ S is 2-connected if virtual edges induce a connected graph on the set of neighbors of each
cut-node x in F .
Proof. Let b1 , b2 , . . . , bi be 2-connected components of G[T ] that include x, and assume that bj and bj+1 are
joined by a virtual edge for each j = 1, . . . , i − 1. Let y and y 0 be a node in b1 and a node in bi , respectively,
such that y 6= x 6= y 0 . There exists a path on G[T ∪ S] that connects y and y 0 , and that does not pass
through x. Hence, x is not a cut-node in G[T ∪ S].
The following lemma presents a bound on the number of iterations in this algorithm.
Lemma 17. The number of iterations is at most 3 max{5/m, 1}OPT − 1.
20

Proof. Let x be a cut-node on F , and let ψx denote the number of connected components induced by the
virtual edges on the neighbor set of x. In each iteration of the algorithm, ψx is decreased by at least one
for some cut-node x. When the first iteration begins, ψx is equal to the degree of x in F . Since all leaves
P
in F are included in B, x∈W ψx = |B| + |W | holds at the beginning of the first iteration. The iterations
P
terminate when x∈W ψx = |W |. Hence, the number of iterations is at most |B|. We will determine |B|
below.
Let H be a spanning tree on G[I1 ∪ C]. We show that each 2-connected component contains a node in
I2 \ C or an edge in H. To see this, suppose that a component b contains no edge in H. If b contains more
than one node in I1 ∪C, then it includes an edge in H. Since, by assumption, this does not happen, b includes
only one node in I1 ∪ C. Notice that each 2-connected component contains at least two nodes, because a
Sm
graph with two nodes joined by an edge is 2-connected. Hence, there exists a node v ∈ i=2 Ii \ C in b. If
v ∈ I2 , we are done. Suppose that v 6∈ I2 . By property (ii), v has neighbors in I1 and in I2 . By property
(iii), v is not a cut-node in G[T ], so these neighbors must be inside b. If the neighbor in I2 is included in C,
b contains two nodes in I1 ∪ C. Since this contradicts the assumption, b contains a node in I2 \ C.
Sm
Nodes in i=2 I2 \ C and edges in G[T ] are not contained in more than one 2-connected component of
G[T ]. The number of edges in H is |I1 | + |C| − 1 ≤ 2 max{5/m, 1}OPT − 1, and |I2 | ≤ max{5/m, 1}OPT
by property (i). Hence |B| ≤ 3 max{5/m, 1}OPT − 1.
From Lemma 17 and property (iv), we obtain the following approximation guarantee for the algorithm.
Theorem 4. The algorithm of Shang et al. [17] attains an approximation factor 5 + 35/k for 2 ≤ k ≤ 5,
and 13 − 5/k for k ≥ 6.

21

