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)
(Amortization )
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 2 V , either
v 2 S or a neighbor u of v is in S.
• Example:
• We are interested in finding a small dominating set.
, , SCS (September 21, 2021)
{ 3,5} {3,4}
If VES ,
n is called dominator
• is
called
If u is adjacent to anadeues , dominated
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)
3 ✓
2
✓
2✓
Distributed Computing, COMP 4001 6
Applications of DS
• A particularly important application of dominating sets is the
construction of an e�cient backbone for routing.
– Hierarchical routing.
• Ideally, in wireless sensor networks “the set of base stations”
should form a dominating set.
• An e�cient 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)
MINIMUM ⇒ Minimal
m it
.
:÷÷✓÷÷mal_
:c
.
!
🙂
✓ YES
✓
YES
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)
Greedily ,
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)
( dominators )
(dominated )
( up for grabs ) dominator
dominatedi¥÷
” ” ” £21bn,
Go 02
,§§¥→u
g 04
– air are neighbors
– tooth u and u are black
– both have to be in a minimum
DS
.
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)
N N ; N
:
G
④
#•q¥a
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)
@
greedy
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)
v9 In : loge
i
–
①
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)
✓ “•
”
£5
Blue = 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 o↵ the initial cost. That’s why we call it
amortize!
, , SCS (September 21, 2021)
I
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)
da
n
N
5
Nz
v
>
NY
iii.÷:
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)
÷
:*
Ñkad% been
weights
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)
An optimal
set s*
exists
Dark color
✓
✓ 0
are elements 0 It is a¥¥÷¥ Or dominating set,every node isdominated by
☒rejustnodes
ofthegrapb
anode in s*
So far we have two set
④ S constructed by the
greedy algorithm
⑨ g* which is minimum
Ds
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 su�ces 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⇤ 2 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)
¥, I ¥*)
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⇤)+1X
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)
☒
k=d(u*) -11
k
É E- ÷ n s
approx . ,
f- dx
:p
:*
± lnx
(Frocmdoelus)
✗ er&⑨f- I 1=2 3 4
Distributed Computing, COMP 4001 23
Analysis (3/3)
• Moreover,
H(n) =
nX
i=1
1/i
is the Harmonic number.
• Therefore the size of the dominating set S thus constructed
satisfies
|S|
X
v⇤2S⇤
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)
–
Good to know
~
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) =
[
u2N(v)
N(u)
the nodes at distance at most 2 from v.
, , SCS (September 21, 2021)
‘ ” ‘” = Him . -iv. I
¥¥oµ
,
AH = set
• f- neighbors
of neighbors of v
Distributed Computing, COMP 4001 27
Example
• Construct examples of distance 2 neighborhoods.
• As before, recall
– W (v) = {u 2 N(v) : u is white}, and
– w(v) = |W (v)|.
, , SCS (September 21, 2021)
Malu ) is
•
•
•
.
the set of
• ooo
‘
v • nodes two
• *
• . hops away
@
from N .
If v sends a me
If u wants to send a message
to its distance 2 neighborhood
what does it to do ?
ggdggg.es/yAtKthm(
Message rat for u
11 . send to all neighbors ~
with an instruction to
relay it to all itsnbs.CM
, 1)
2
. if you receive ☒④ send
it to your neighbor and change 1 too
In distributed algorithms
we will be relaying messages
(message, relay value )
( Ms , Rv#
1. send Cms
,
Rv )
⑥ If you receive it , change RV← RV-1and forward cars ,Rv )
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)
If you have{Ñanµi☐
the nodes then
you can breakthe
ties .
– The nodes take into account only
their distance two neighborhoods Node
N runs a
” centralized ” greedy
algorithm centered at itself
–
The value selected will not
affect a value 2- hops away
–
What happens if you do
distance 3 neighborhood?
Eren says
this :
If instead of distance 2 neighborhood
me choose distance 3 don’t we get
a better approximation ?
distance 4
:
distance = diameter
–
He can customize according to rohatwed !
distance knbl.gg
MI – K ) AAA
allnode! ~
6lormgPm_bkm
You can color a
tneeof%^¥
colors in log*n rounds .
T.gl?e.gTogn £2
*
‘
AM
÷”ÉE÷÷÷÷÷÷÷÷÷÷-÷÷÷÷÷¥÷÷’i- i’ ‘
–
. –
–
i
”
spanning €dw
)
Tree Algorithms
BIG MERGE
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)
I will update
the lecture notes as
class notes
µ
What is the message
cost of the algorithm?
*÷
Distributed Computing, COMP 4001 31
Exercisesa
1. Show that
H(n) =
nX
i=1
1/i lnn+ 1.
Hint: Use calculus to approximate
R
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 2 D} is a feasible solution of the set cover
problem, with |C| = |D|.
(b) Conversely, if C = {Sv : v 2 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 2 V is at most k hops away
from a vertex u 2 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 e�cient 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)