Computation on Graphs: Maximal Independent Sets
C
C
S
S
1
1
4
4
0
0
:
:
C
C
o
o
m
m
p
p
u
u
t
t
a
a
t
t
i
i
o
o
n
n
o
o
n
n
G
G
r
r
a
a
p
p
h
h
s
s
–
–
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
s
s
A
A
g
g
r
r
a
a
p
p
h
h
p
p
r
r
o
o
b
b
l
l
e
e
m
m
:
:
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
1
8
7
6
5
4
3
2
•
Graph with vertices V = {1,2,…,n}•
A set S of vertices is
independent
if no
two vertices in S are neighbors.
•
An independent set S is
maximal
if it is
impossible to add another vertex and
stay independent
•
An independent set S is
maximum
if no other independent set has more
vertices
•
Finding a
maximum
independent set is
intractably difficult (NP-hard)
•
Finding a
maximal
independent set is
easy, at least on one processor.
The set of red vertices
S = {4, 5} is
independent
and is
maximal
but not
maximum
S
S
e
e
q
q
u
u
e
e
n
n
t
t
i
i
a
a
l
l
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
1
8
7
6
5
4
3
2
1.
S = empty set;
2.
for vertex v = 1 to n {3.
if (v has no neighbor in S) {4.
add v to S
5.
}
6.
}
S
=
{}
S
S
e
e
q
q
u
u
e
e
n
n
t
t
i
i
a
a
l
l
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
1
8
7
6
5
4
3
2
1.
S = empty set;
2.
for vertex v = 1 to n {3.
if (v has no neighbor in S) {4.
add v to S
5.
}
6.
}
S
=
{1
}
S
S
e
e
q
q
u
u
e
e
n
n
t
t
i
i
a
a
l
l
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
1
8
7
6
5
4
3
2
1.
S = empty set;
2.
for vertex v = 1 to n {3.
if (v has no neighbor in S) {4.
add v to S
5.
}
6.
}
S
=
{1
,
5
}
S
S
e
e
q
q
u
u
e
e
n
n
t
t
i
i
a
a
l
l
M
M
a
a
x
x
i
i
m
m
a
a
l
l
I
I
n
n
d
d
e
e
p
p
e
e
n
n
d
d
e
e
n
n
t
t
S
S
e
e
t
t
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
1
8
7
6
5
4
3
2
1.
S = empty set;
2.
for vertex v = 1 to n {3.
if (v has no neighbor in S) {4.
add v to S
5.
}
6.
}
S
=
{1
,
5
,
6
}
w
o
r
k
~
O
(
n
)
,
b
u
t
s
p
a
n
~
O
(
n
)
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
S
=
{}
C
=
{1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
S
=
{}
C
=
{1
,
2
,
3
,
4
,
5
,
6
,
7
,
8
}
2.6
4.1
5.9
3.1
1.2
5.8
9.3
9.7
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
S
=
{1
,
5
}
C
=
{6
,
8
}
2.6
4.1
5.9
3.1
1.2
5.8
9.3
9.7
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
S
=
{1
,
5
}
C
=
{6
,
8
}
2.7
1.8
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
S
=
{1
,
5
,
8
}
C
=
{}
2.7
1.8
P
P
a
a
r
r
a
a
l
l
l
l
e
e
l
l
,
,
R
R
a
a
n
n
d
d
o
o
m
m
i
i
z
z
e
e
d
d
M
M
I
I
S
S
A
A
l
l
g
g
o
o
r
r
i
i
t
t
h
h
m
m
[
[
L
L
u
u
b
b
y
y
]
]
1
8
7
6
5
4
3
2
1.
S
= empty set;
C
= V;
2.
while
C
is not empty {3.
label each v in
C
with a random
r(v);
4.
for all v in
C
in parallel {5.
if
r(v)
< min(
r(neighbors of v)
) {6.
move v from
C
to
S
;
7.
remove neighbors of v from
C
;
8.
}
9.
}
10.
}
T
h
e
o
r
e
m
:
T
h
i
s
a
l
g
o
r
i
t
h
m
“
v
e
r
y
p
r
o
b
a
b
l
y
”
f
i
n
i
s
h
e
s
w
i
t
h
i
n
O
(
l
o
g
n
)
r
o
u
n
d
s
.
w
o
r
k
~
O
(
n
l
o
g
n
)
,
b
u
t
s
p
a
n
~
O
(
l
o
g
n
)
CS267 Lecture 2
The content discusses the concept of maximal independent sets in graph theory. It defines independent, maximal, and maximum sets, highlighting the difficulty in finding a maximum independent set due to its NP-hard nature. Sequential and parallel algorithms for finding maximal independent sets are presented, demonstrating how these sets are generated in graph structures. The visuals aid in understanding the algorithms and the process of identifying independent vertices in a graph.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
CS 140: Computation on Graphs Maximal Independent Sets
A graph problem: Maximal Independent Set Graph with vertices V = {1,2, ,n} 1 2 A set S of vertices is independent if no two vertices in S are neighbors. An independent set S is maximal if it is impossible to add another vertex and stay independent 4 3 6 5 An independent set S is maximum if no other independent set has more vertices 7 8 Finding a maximum independent set is intractably difficult (NP-hard) The set of red vertices S = {4, 5} is independent and is maximal but not maximum Finding a maximal independent set is easy, at least on one processor.
Sequential Maximal Independent Set Algorithm 1 2 1. S = empty set; 2. for vertex v = 1 to n { 3. if (v has no neighbor in S) { 4. add v to S 4 3 6 5 5. } 7 8 6. } S = { }
Sequential Maximal Independent Set Algorithm 1 2 1. S = empty set; 2. for vertex v = 1 to n { 3. if (v has no neighbor in S) { 4. add v to S 4 3 6 5 5. } 7 8 6. } S = { 1 }
Sequential Maximal Independent Set Algorithm 1 2 1. S = empty set; 2. for vertex v = 1 to n { 3. if (v has no neighbor in S) { 4. add v to S 4 3 6 5 5. } 7 8 6. } S = { 1, 5 }
Sequential Maximal Independent Set Algorithm 1 2 1. S = empty set; 2. for vertex v = 1 to n { 3. if (v has no neighbor in S) { 4. add v to S 4 3 6 5 5. } 7 8 6. } S = { 1, 5, 6 } work ~ O(n), but span ~O(n)
Parallel, Randomized MIS Algorithm [Luby] 1 2 1. S = empty set; C = V; 2. while C is not empty { 3. label each v in C with a random r(v); 4 3 4. for all v in C in parallel { 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 7. remove neighbors of v from C; S = { } 8. } C = { 1, 2, 3, 4, 5, 6, 7, 8 } 9. } 10. }
Parallel, Randomized MIS Algorithm [Luby] 2.6 4.1 1 2 1. S = empty set; C = V; 2. while C is not empty { 5.9 3.1 3. label each v in C with a random r(v); 5.8 4 3 4. for all v in C in parallel { 1.2 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 9.7 9.3 7. remove neighbors of v from C; S = { } 8. } C = { 1, 2, 3, 4, 5, 6, 7, 8 } 9. } 10. }
Parallel, Randomized MIS Algorithm [Luby] 2.6 4.1 1 2 1. S = empty set; C = V; 2. while C is not empty { 5.9 3.1 3. label each v in C with a random r(v); 5.8 4 3 4. for all v in C in parallel { 1.2 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 9.7 9.3 7. remove neighbors of v from C; S = { 1, 5 } 8. } C = { 6, 8 } 9. } 10. }
Parallel, Randomized MIS Algorithm [Luby] 1 2 1. S = empty set; C = V; 2. while C is not empty { 3. label each v in C with a random r(v); 2.7 4 3 4. for all v in C in parallel { 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 1.8 7. remove neighbors of v from C; S = { 1, 5 } 8. } C = { 6, 8 } 9. } 10. }
Parallel, Randomized MIS Algorithm [Luby] 1 2 1. S = empty set; C = V; 2. while C is not empty { 3. label each v in C with a random r(v); 2.7 4 3 4. for all v in C in parallel { 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 1.8 7. remove neighbors of v from C; S = { 1, 5, 8 } 8. } C = { } 9. } 10. }
Parallel, Randomized MIS Algorithm [Luby] 1 2 1. S = empty set; C = V; 2. while C is not empty { 3. label each v in C with a random r(v); 4 3 4. for all v in C in parallel { 6 5 7 8 5. if r(v) < min( r(neighbors of v) ) { 6. move v from C to S; 7. remove neighbors of v from C; Theorem: This algorithm very probably finishes within O(log n) rounds. 8. } 9. } 10. } work ~ O(n log n), but span ~O(log n)
