WEBVTT
00:00:00.000 --> 00:00:03.000
So unfortunately the factor-2 approximation that we have found for vertex cover
00:00:03.000 --> 00:00:06.000
does not carry over to clique or independent set.
00:00:06.000 --> 00:00:09.000
Well we've only shown that it doesn't carry over to independent set,
00:00:09.000 --> 00:00:13.000
but since independent set and clique are, again, so closely connected
00:00:13.000 --> 00:00:18.000
you can already see or at least guess why it doesn't carry over here as well.
00:00:18.000 --> 00:00:21.000
And I've actually mentioned a similar thing to you in the last unit
00:00:21.000 --> 00:00:23.000
when we talked about fixed parameter tractability.
00:00:23.000 --> 00:00:29.000
Where it was also the case that if you took the size of the optimum solution as a parameter,
00:00:29.000 --> 00:00:33.000
there is a parameterized algorithm for vertex cover,
00:00:33.000 --> 00:00:37.000
but clique and independent set are both not fixed parameter tractable.
00:00:37.000 --> 00:00:39.000
So the thing here is this.
00:00:39.000 --> 00:00:43.000
A reduction that you use to show NP-completeness
00:00:43.000 --> 00:00:46.000
is, in a way, a very coarse way of reducing problems to each other.
00:00:46.000 --> 00:00:50.000
So coarse that it can destroy approximation factors,
00:00:50.000 --> 00:00:53.000
that it can destroy fixed parameter tractability, and so on.
00:00:53.000 --> 00:00:56.000
So there are special types of reductions
00:00:56.000 --> 00:01:00.000
that will keep approximation factors or fixed parameter tractability.
00:01:00.000 --> 00:01:02.000
Unfortunately we can't go deeper into them in this course,
00:01:02.000 --> 00:01:07.000
but you should just know that just because two problems are closely related,
00:01:07.000 --> 00:01:11.000
that does not mean that algorithmic techniques, such as approximation algorithms,
00:01:11.000 --> 99:59:59.999
easily carry over from one problem to the other as well, unfortunately.