Complex Networks

42 

Complex Networks: An Algorithmic Perspective

Algorithm 3.9 VC Cert

1: Input : G(V,E), V

′

⊲ V

′

is the instance with k vertices

2: Output : YES or NO

3:

4: S ←V

′

; P ← E

5: while S 6= Ø do

6: select u ∈ S arbitrarily

7: for all (u,v) ∈ E do

8: P ← P\{(u,v)}

9: S ←S \{u}

10: end for

11: end while

12: if P = Ø then ⊲ decide whether V

′

is a solution

13: return YES

14: else return NO

15: end if



Optimization Problem: Find an IS with the maximum size (MaxIS) in

G.



Decision Problem: Is there an IS of size at least k in G where k < n?



Dominating Set Problem (DOM): Given a simple, undirected graph G(V,E),

a set of vertices D is a dominating set (DS) if any vertex is either ...