I'm aware that Vertex Cover and Independent Set are complements of eachother, but I've also heard Independent Set referred to something in relation to Clique; I just don't recall what. It can't be the complement, because if it is, then Clique and Vertex cover would be the same, wouldn't it?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
A set of vertices in a graph $\Gamma$ form a clique iff they form an independent set in the complement of $\Gamma$. Is that what you were looking for?
In response to your comment below: Cliques and independent sets are sets of vertices rather than graphs, so they technically can't be complementary graphs. However, the induced subgraph spanned by a clique is the complement of the induced subgraph spanned by an independent set of the same size.
If I remember correctly they are all Np-complete problems meaning they can be transformed into each other in polynomial amount of time. That is, if you can solve the clique problem efficiently, then you can solve the Vertex cover efficiently. The clique problem is usually transformed into the 3-sat problem.