Transcript Languages and Finite Automata

Maximal Independent Set
1
Independent Set (IS):
In a graph G=(V,E), |V|=n, |E|=m, any
set of nodes that are not adjacent
2
Maximal Independent Set (MIS):
An independent set that is no
subset of any other independent set
3
Size of Maximal Independent Sets
A graph G…
…a MIS of min size… …a MIS of max size
Remark 1: The ratio between the size of a maximum MIS
and a minimum MIS is unbounded (i.e., O(n))!
Remark 2: finding a minimum/maximum MIS is an NPhard problem, while a MIS can be found in polynomial time
4
Applications in DS: network monitoring
• A MIS is also a Dominating Set (DS) of the graph
(the converse in not true, unless the DS is
independent), namely every node in G is at distance at
most 1 from at least one node in the MIS (otherwise
the MIS could be enlarged, against the assumption of
maximality!)
 In a network graph G consisting of nodes
representing processors, a MIS defines a set of
processors which can monitor the correct functioning
of all the nodes in G (in such an application, one should
find a MIS of minimum size, to minimize the number
of sentinels, but as said before this is known to be
NP-hard)
5
A Sequential Greedy algorithm
Suppose that
Initially
I
will hold the final MIS
I 
G
6
Phase 1:
Pick a node
v1
v1
and add it to
I
G  G1
7
Remove
v1
and neighbors N (v1 )
G1
8
Remove
v1
and neighbors N (v1 )
G2
9
Phase 2:
Pick a node
v2
and add it to
I
G2
v2
10
Remove
v2
and neighbors N (v2 )
G2
v2
11
Remove
v2
and neighbors N (v2 )
G3
12
Phases 3,4,5,…:
Repeat until all nodes are removed
G3
13
Phases 3,4,5,…,x:
Repeat until all nodes are removed
Gx 1
No remaining nodes
14
At the end, set
I
will be a MIS of
G
G
15
Running time of the algorithm: Θ(m)
Number of phases of the algorithm: O(n)
Worst case graph (for number of phases):
n nodes, n-1 phases
16
Homework
Can you see a distributed version of the
algorithm just given?
17
A General Algorithm For Computing a MIS
Same as the sequential greedy algorithm, but at
each phase, instead of a single node, we now
select any independent set (this selection should
be seen as a black box at this stage)
 The underlying idea is that this approach will be
useful for a distributed algorithm
18
Example:
Suppose that
Initially
I
will hold the final MIS
I 
G
19
Phase 1:
Find any independent set I1
And insert I1 to I :
I  I  I1
G  G1
20
remove I1 and neighbors N (I1 )
G1
21
remove I1 and neighbors N (I1 )
G1
22
remove I1 and neighbors N (I1 )
G2
23
Phase 2:
On new graph
Find any independent set I2
And insert I2 to I :
I  I  I2
G2
24
remove I2 and neighbors N (I2 )
G2
25
remove I2 and neighbors N (I2 )
G3
26
Phase 3:
On new graph
Find any independent set I3
And insert I3 to I :
I  I  I3
G3
27
remove I3 and neighbors N (I3 )
G3
28
remove I3 and neighbors N (I3 )
G4
No nodes are left
29
Final MIS
I
G
30
Analysis
1. The algorithm is correct, since independence
and maximality follow by construction
2. The number of phases depends on the choice
of the independent set in each phase: The
larger the subgraph removed at the end of a
phase, the smaller the residual graph, and
then the faster the algorithm. Then, how do
we choose such a set, so that independence is
guaranteed and the convergence is fast?
31
Example: If I1 is MIS,
1 phase is needed
Example: If each Ik contains one node,
(n ) phases may be needed
(sequential greedy algorithm)
32
A Randomized Sync. Distributed Algorithm
• Follows the general MIS algorithm
paradigm, by choosing randomly at each
phase the independent set, in such a way
that it is expected to remove many nodes
from the current residual graph
• Works with synchronous, uniform models,
and does not make use of the processor IDs
Remark: It is randomized in a Las Vegas
sense, i.e., it uses randomization only to
reduce the expected running time, but
always terminates with a correct result
33
Let d be the maximum node degree
in the whole graph
1
2
d
Suppose that d is known to all the nodes
(this may require a pre-processing)
34
At each phase
k:
Each node z  Gk elects itself
with probability p  1
d
1
2
d
z
Elected nodes are candidates for
independent set Ik
35
However, it is possible that neighbor nodes
are elected simultaneously (nodes can check
it out by testing their neighborhood)
Gk
Problematic nodes
36
All the problematic nodes step back to the
unelected status, and proceed to the next
phase. The remaining elected nodes form
independent set Ik
Gk
Ik
Ik
Ik
Ik
37
Analysis:
Success for a node z  Gk in phase k :
z disappears at the end of phase k
(enters Ik or N (Ik ) )
A good scenario
that guarantees
success
No neighbor elects itself
1
2
y
z elects itself
38
Basics of Probability
Let A and B denote two events in a probability space; let
1.
2.
3.
A (i.e., not A) be the event that A does not occur;
AՈB be the event that both A and B occur;
AUB be the event that A or (non-exclusive) B occurs.
Then, we have that:
1. P(A)=1-P(A);
2. P(AՈB)=P(A)·P(B) (if A and B are independent)
3. P(AUB)=P(A)+P(B)-P(AՈB) (if A and B are mutually
exclusive, then P(AՈB)=0, and P(AUB)=P(A)+P(B)).
39
Fundamental inequality
k  1, k  
| t | k, t  
e  2,7182...
 t
e  1 
k

t
2
k
  t
   1    e t
  k
40
Probability for a node z of success in a phase:
P(success z) = P((z enters Ik) OR (z enters N(Ik))
≥ P(z enters Ik)
i.e., it is at least the probability that it elects itself
AND no neighbor elects itself, and since these
events are independent, if y=|N(z)|, then
P(z enters Ik) = p·(1-p)y (recall that p=1/d)
1p
1p
1
No neighbor elects itself
1p
y
2
z
p
elects itself
41
Probability of success for a node in a phase:
At least
p1  p   p(1  p)
y
d
1
1
 1  
d d
First (left) ineq.
with t =-1
d
1 
1

1  
ed  d 
1

2ed
For
d 2
42
Therefore, node z disappears at the end
of phase k with probability at least 1
2ed
1
y
2
z
 Node z does not disappear at the end
1
of phase k with probability at most 1 
2ed
43
Definition: Bad event for node
z:
after 4ed ln n phases
node
z did not disappear
Independent
events
This happens with probability
P(ANDk=1,..,4ed lnn (z does not disappear at the end of phase k))
i.e., at most:
1 

1 

 2ed 
4ed lnn
2ed

1 

 1 
  2ed 

2lnn





e
(first (right) ineq. with t =-1 and n =2ed)
1
2lnn

1
n2
44
Bad event for G:
after 4ed ln n phases
at least one node did not disappear
This happens with probability (notice
that events are not mutually exclusive):
P(ORxG(bad event for x)) ≤
1
P(bad event for x )  n

n
x G

2

1
n
45
Good event for G:
within 4ed ln n phases
all nodes disappear
This happens with probability:
1  [probabili ty of bad event for G]  1 -
1
n
(i.e., with high probability)
46
Total number of phases:
Time complexity
4ed lnn  O (d logn )
# rounds for each phase: 3
(w.h.p.)
1. In round 1, each node adjusts its neighborhood (see round
3 of the previous phase), and then tries to elect itself; if
this is the case, it notifies its neighbors;
2. In round 2, each node receives notifications from
neighbors, decide whether it is in Ik, and notifies
neighbors;
3. In round 3, each node receiving notifications from elected
neighbors, realizes to be in N(Ik), notifies its neighbors
about that, and stops.
 total # of rounds: O (d logn )
(w.h.p.)
47
Homework
Can you provide a good bound on the number
of messages?
48