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.
