Largest Independent Set
INDEPENDENT SET: Given a graph G = (V, E) what is the largest subset
of vertices S  V such that each edge of E has
Ex. Is there an independent set of size  6? Yes.
Ex. Is there an independent set of size  7? No.
independent set
1
Largest Independent Set
•
Intractable problem for general graphs
•
What happens when the graph G is a
tree T=(V,E)?
11-2
Largest Independent Set
•
•
Select a root r for T
For a node v in T, let T(v) be the subtree
of T rooted at node v
r
r
v
11-3
Dynamic Programming
Equation
•
•
OPT(v): Largest independent set forT(v)
We are interested in OPT(r)
1, T (v)has one node

OPT (v)  


OPT (w),
OPT (w)


max1 
w is a child of v
 w is a grandchild of v


11-4
Algorithm
IS(v)
If v has no children
M[v]=1
ElseIf M[v] is empty
SomaFilhos0;SomaNetos1
Para todo filho w de v
SomaFilhos <= SomaFilhos+ IS(w)
Para todo neto w de v
SomaNetos <= SomaNetos+ IS(w)
M[v] max(SomaFilhos,SomaNetos)
End if
Return M[v]
11-5
Análise
•
Cada nó é chamado no máximo duas vezes, uma vez
por seu pai e outra por seu avô.
•
A primeira chamada tem custo proporcional ao
número de filhos mais o número de netos e a segunda
chamada custa O(1) . Somando o custo de todas as
chamadas obtemos O(|V|)
11-6