
So now we have factor two approximation algorithms for Alice, who is, of course, very happy about this.

And we've also found a factor two approximation algorithm for the problem that Dave was working on.

So Dave is, of course, equally happy. Now, the question: Since Alice and Dave apparently are working on problems

that can be approximated very well, what about Bob and Carol?

And as you remember, the problems that Bob and Carol are working on are closely related to the one that Alice was working on.

So, Alice was working on Vertex Cover, Bob was working, as you'll remember, on Clique, and Carol was working on Independent Set.

So we already know that we have a factor two approximation algorithm for Vertex Cover.

And from the previous units, you also know how closely Vertex Cover is related to,

well, first of all, Independent Set, but also Clique. Given the close relation, we take this algorithm here and simply

carry over our insight for Vertex Cover to Clique and Independent Set.

So the question now is, given this factor two approximation for Vertex Cover, and given the close relation

of Vertex Cover to Clique and Independent Set, do we now also know that there's a factor two approximation for

Clique and Independent Set? And I'm just writing Independent Set as IS here, to save some space.