CS计算机代考程序代写 algorithm Distributed Computing, COMP 4001 1

Distributed Computing, COMP 4001 1

Distributed

Dominating Set

(DDS)

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 2

Outline

• Dominating Set

• Basic Construction

• Distributed Construction

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 3

Dominating Set

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 4

DS (Dominating Set)

• Given an undirected graph G = (V,E), a dominating set is a
subset S ⊆ V of its nodes such that for all nodes v ∈ V , either
v ∈ S or a neighbor u of v is in S.

• Example:

• We are interested in finding a small dominating set.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 5

More Examples of DSs

• Two more examples

• A given graph has more than one dominating sets.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 6

Applications of DS

• A particularly important application of dominating sets is the
construction of an efficient backbone for routing.

– Hierarchical routing.

• Ideally, in wireless sensor networks “the set of base stations”
should form a dominating set.

• An efficient dominating set algorithm can be used as a basic
building block to solve a number of problems in distributed

computing.

– For example, whenever we need to partition the network

into a small number of local clusters, the computation of a

small dominating set usually facilitates the task.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 7

Minimal and Minimum DS

• A DS is minimal if no proper subset is a DS.

• A DS is minimum if it has the smallest possible size among all
possible DSs.

• Minimal vs Minimum

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 8

Issues

• It is well-known that computing a dominating set of minimum
size (also called MDS) is NP-hard.a

– We therefore look for approximation algorithms, that is,

algorithms which produce solutions which are optimal up to

a certain factor.

• There might be more than one MDS in a graph.

aA minimal dominating set is computable in polynomial time-see Exercise 7.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 9

Basic Construction

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 10

Basic Construction of DS

• All the dominating set algorithms that we study are greedy in
the sense that they operate in the following way.

– Start with S = ∅; add nodes to S until it is a DS.

• To simplify presentation, nodes are colored according to their
state during the execution of an algorithm. We call

– nodes in S black,

– nodes which are covered (have a neighbor in S) gray, and

– all uncovered nodes white.

• As we build the set S the node coloring assignment changes.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 11

Definition of Weight of a Node

• For any node v (regardless of its color) let W (v) denote the set
of white nodes among the direct neighbors of v, including v

itself (if white).

– We call w(v) = |W (v)| the span of v.

• Examples of spans. Assume the central node is v.

From left to right, w(v) = 6, 0, 4, respectively.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 12

Sequential Greedy Algorithm

• Lets start with a non-distributed algorithm!

• Greedy Algorithm

1. S ← ∅;
2. while there exist white nodes do

(a) v := {v : w(v) = maxu{w(u)}};
/* Find a node v with max span; note that v itself may

not be a white node; */

(b) S ← S ∪ {v};
/* Insert v to S */

3. end while

• It’s a simple algorithm!

• The analysis is a bit tricky!

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 13

Sequential Greedy Algorithm

• Theorem 1 The Sequential Greedy Algorithm is
(ln ∆ + 2)-competitive, that is, for the computed dominating set

S and an optimal dominating set S∗, we have

|S|
|S∗|

≤ ln ∆ + 2,

where ∆ is the maximum degree of the graph.

• That is, the Sequential Greedy Algorithm constructs a
Dominating set S whose size is at most (ln ∆ + 2) times the

size of the optimal S∗, i.e.,

|S| ≤ (ln ∆ + 2)|S∗|.

• Analysis of this algorithm uses a cost amortization technique.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 14

How to Amortize the Cost (1/4)

• Each time, we choose a new node (this is the central blue) of
the dominating set (each greedy step), we have cost 1.

• The cost incurred from our choice is of course equal to 1.

• However, when the central node is selected as part of the
dominating set to be constructed, it and all its neighbors will

be removed;

– this is justified because they are dominated by (i.e., are

neighbors of) the node selected.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 15

How to Amortize the Cost (2/4)

• Instead of letting this (blue) node pay the whole cost, we
distribute the cost equally among all newly covered nodes.

– I.e., among the nodes dominated by this (blue) node but

which have not already been accounted for (i.e., have

already been made gray or black in a previous step).

• The total cost does not change … only the way it is distributed
among the nodes does!a

• Indeed, if v is the central node then the total number of nodes
removed will d(v) + 1, where d(v) is the degree of v.

– The total cost will be

(d(v) + 1)
1

d(v) + 1
= 1.

aAmortize means gradually write off the initial cost. That’s why we call it

amortize!

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 16

How to Amortize the Cost (3/4)

• The node v (center), chosen in line 2(a) of the algorithm, is
white itself and let its white neighbors are v1, v2, v3, v4, v5.

– Each of the 6 nodes v, v1, v2, v3, v4, v5 get charged 1/6.

• If v is chosen as a gray node, (and there is a black neighbor)

– only white neighbors v1, v2, v3, v4 get charged (all get 1/4).

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 17

How to Amortize the Cost (4/4)

• If v is chosen as gray node, and all neighbors are white

– only the nodes v1, v2, v3, v4, v5 get charged (they all get 1/5).

• If v is chosen as gray node, and there is a gray neighbor

– only the white neighboring nodes v1, v2, v3, v5 get charged

(they all get 1/4).

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 18

Decomposition into Stars

• There is an optimal dominating set (which we may not be able
to construct with an algorithm); lets call it S∗.

• By the definition of dominating sets (in our case the set S∗),
– to each node which is not in S∗, we can assign a neighbor

from S∗.

• If more than one neighbor from S∗, we select one!

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 19

Decomposition into Stars

• By assigning each node to exactly one neighboring node of S∗,
the graph is decomposed into stars, each having a

dominator node (in S∗) as center and non-dominators as leaves.

• The cost of an optimal dominating set is 1 for each such star.
– Next we show that the amortized cost (distributed costs) of

the greedy algorithm is at most ln ∆ + 2 for each star.

• This suffices to prove the theorem.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 20

Recall the Sequential Greedy Algorithm

• Sequential Greedy Algorithm

1. S ← ∅;
2. while there exist white nodes do

(a) v := {v : w(v) = maxu{w(u)}};
(b) S ← S ∪ {v};

3. end while

• The algorithm constructs some Dominating Set S.
• We will compare it to an optimal one S∗.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 21

Analysis (1/3)

• Consider a single star with center v∗ ∈ S∗ before choosing a
new node u in the greedy algorithm.

• The number of nodes that become dominated when adding u
to the dominating set is w(u).

• Thus, if some white node u in the star of v∗ becomes gray or
black, it gets charged 1/w(u).

• By the greedy condition, u is a node with maximal span and
therefore w(u) ≥ w(v∗).
– Thus, u is charged 1/w(u) which is at most 1/w(v∗).

• Therefore the first node in the star of v∗ which is covered gets
charged at most 1/(d(v∗) + 1).a

aWe denote by d(x) the degree of the node x.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 22

Analysis (2/3)

• When the second node in the star of v∗ is covered, it gets
charged at most 1/d(v∗).

• In general, the ith node that is covered in the star of v∗ gets
charged at most 1/(d(v∗)− i + 2).a

• Thus, the total amortized cost in the star of v∗ is at most

d(v∗)+1∑
d=1

1

d
= H(d(v∗) + 1)

≤ H(∆ + 1)

≤ ln ∆ + 2,

where ∆ is the maximal degree of G.

aEvery time you charge the weight goes down by one.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 23

Analysis (3/3)

• Moreover,

H(n) =
n∑

i=1

1/i

is the Harmonic number.

• Therefore the size of the dominating set S thus constructed
satisfies

|S| ≤

v∗∈S∗
ln ∆ + 2

≤ |S∗|(ln ∆ + 2)

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 24

Issues

• It is known that unless NP ⊆ DTIME(nO(log logn)), no
polynomial-time algorithm can approximate the minimum

dominating set problem better than (1− o(1)) · ln ∆.
– Thus, unless P = NP , the approximation ratio of the simple

greedy algorithm is optimal (up to lower order terms).

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 25

Distributed

Construction

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 26

Distance 2 Neighborhood of node v

• To understand the distributed algorithm we first define the
distance 2 neighborhood of a node.

• Let N(v) denote the set of neighbors of v (including v itself),
and

N2(v) =

u∈N(v)

N(u)

the nodes at distance at most 2 from v.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 27

Example

• Construct examples of distance 2 neighborhoods.

• As before, recall
– W (v) = {u ∈ N(v) : u is white}, and
– w(v) = |W (v)|.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 28

Main Idea of Distributed Greedy Algorithm

• The distributed algorithm hinges on the following observation.

• Claim: if the span of node v is greater than the span of any
other node in its distance 2 neighborhood (i.e., at distance at

most 2 from v), then the greedy algorithm can be made to

choose v before any of the nodes at distance at most 2.

– The greedy algorithm we discussed before selects a node,

say v, of greatest span.

– However, v can figure this out, by merely checking whether

it has the greatest span among all the vertices in its

distance 2 neighborhood N2(v).

– If v exists none of the nodes in N2(v) will ever be chosen by

the greedy algorithm.

• The span of a node can only be reduced if any of the nodes at
distance at most 2 is included in the dominating set.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 29

Distributed Greedy Algorithm

• This leads to a distributed version of the greedy algorithm.

• Every node v executes the following algorithm.
Distributed Greedy Algorithm

1. while v has white neighbors do

2. compute span w(v);

3. send w(v) to nodes at distance at most 2;

4. if w(v) largest within distance 2 (ties are broken by IDs)

then

5. join dominating set

6. end if

7. end while

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 30

Analysis

• Theorem 2 Distributed Greedy Algorithm computes a
dominating set of size at most ln ∆ + 2 times the size of an

optimal dominating set in O(n) rounds.

• The approximation ln ∆ + 2 follows directly from the above
observation and the analysis of the greedy algorithm.

• The time complexity is at most linear because in every
iteration of the while loop, at least one node is added to the

dominating set and because one iteration of the while loop can

be implemented in a constant number of rounds.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 31

Exercisesa

1. Show that

H(n) =
n∑

i=1

1/i ≤ lnn + 1.

Hint: Use calculus to approximate
∫ x
1

1
x
dx.

2. Show that every MIS (Maximal Independent Set) is a

dominating set.

3. Connect the centers of two stars by an edge (Fig. (a) or (b)).

aDo not submit!

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 32

(a) Show that if the two centers are dominators then this gives

rise to a dominating set of size 2 (Fig. (b)).

(b) Every MIS, say I, contains all the leaves of at least one of

the two stars.

4. Find minimum dominating sets in each of the two graphs below

5. Given a graph G = (V,E) with V = {1, 2, . . . , n}, construct a
set cover instance (U, S) as follows: the universe U is V , and

the family of subsets is S = {S1, S2, . . . , Sn} such that Sv
consists of the vertex v and all vertices adjacent to v in G.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 33

(a) Show that if D is a dominating set for G, then

C = {Sv : v ∈ D} is a feasible solution of the set cover
problem, with |C| = |D|.

(b) Conversely, if C = {Sv : v ∈ D} is a feasible solution of the
set cover problem, then D is a dominating set for G, with

|D| = |C|.

6. A subset S ⊆ V , where G = (V,E) is a graph, is called
k-Dominating if every vertex v ∈ V is at most k hops away
from a vertex u ∈ S.

(a) For every integer k construct a graph G and a

k-Dominating set which is not a k + 1-Dominating set.

7. Unlike the the minimum dominating set which is NP-hard, a

minimal dominating set problem can be computed im

polynomial time. Give an algorithm and analyze its complexity.

8. Although the Distributed DS algorithm discussed is distributed

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 34

there are instances when it will be slow. For example: Assume

there is a long path of descending degrees (spans).

Estimate how long it will take until termination. Hint: The

algorithm selects nodes of max span. Hence, every node has to

wait for the neighbor to the left.

, , SCS (September 21, 2021)

Distributed Computing, COMP 4001 35

Sources

• L. Jia, R. Rajaraman, and T. Suel. An efficient distributed
algorithm for constructing small dominating sets. Distributed

Computing, 15(4):193-205, 2002.

• F. Kuhn and R. Wattenhofer. Constant-Time Distributed
Dominating Set Approximation. In Springer Journal for

Distributed Computing, Volume 17, Number 4, May 2005.

, , SCS (September 21, 2021)