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.