Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
That seems to make sense... I heard from my prof something about complementary graphs, but I didn't understand how... clique and independent set are not directly complementary graphs of eachother, but the same set of vertices mean two different things based on the complement of the bigger graph.. – agent154 Feb 20 at 20:09
[I'm not actually sure if 'spanned by' is correct terminology there. Could someone please correct me if I'm wrong?] – Tara B Feb 20 at 23:38
I recently had a refresher on graph terminology, and I think spanned is right. A spanning subgraph G' of G is one that has all the same vertices as G, but not necessarily all the same edges... – agent154 Mar 10 at 0:05
up vote 0 down vote

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.

share|improve this answer
They are, but that's not what I was asking specifically... Independent Set and Vertex Cover are complementary graphs... But what is the relationship between Clique and the other two? A clique is a subset of vertices in graph G whereby every vertex in that subset has an edge between every other vertex. Independent Set is a subset of vertices in G whereby every vertex in that subset are connected to no other vertex in that set. Clearly they're opposite somehow, but they can't be complimentary... – agent154 Feb 20 at 20:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.