Saturday, February 09, 2013
Clique, Independent Set and Vertex Cover
Compute a clique (ie fully connected subgraph) from a given graph G, and then invert the original graph into G′, the vertexes of the clique form an Independent Set in G′ !
Complement the Independent Set of G′, we get the Vertex Cover of G′ !
See Unit 1.4 at Intro to Theoretical Computer Science.
