[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.00,Default,,0000,0000,0000,,So unfortunately the factor-2 approximation that we have found for vertex cover
Dialogue: 0,0:00:03.00,0:00:06.00,Default,,0000,0000,0000,,does not carry over to clique or independent set.
Dialogue: 0,0:00:06.00,0:00:09.00,Default,,0000,0000,0000,,Well we've only shown that it doesn't carry over to independent set,
Dialogue: 0,0:00:09.00,0:00:13.00,Default,,0000,0000,0000,,but since independent set and clique are, again, so closely connected
Dialogue: 0,0:00:13.00,0:00:18.00,Default,,0000,0000,0000,,you can already see or at least guess why it doesn't carry over here as well.
Dialogue: 0,0:00:18.00,0:00:21.00,Default,,0000,0000,0000,,And I've actually mentioned a similar thing to you in the last unit
Dialogue: 0,0:00:21.00,0:00:23.00,Default,,0000,0000,0000,,when we talked about fixed parameter tractability.
Dialogue: 0,0:00:23.00,0:00:29.00,Default,,0000,0000,0000,,Where it was also the case that if you took the size of the optimum solution as a parameter,
Dialogue: 0,0:00:29.00,0:00:33.00,Default,,0000,0000,0000,,there is a parameterized algorithm for vertex cover,
Dialogue: 0,0:00:33.00,0:00:37.00,Default,,0000,0000,0000,,but clique and independent set are both not fixed parameter tractable.
Dialogue: 0,0:00:37.00,0:00:39.00,Default,,0000,0000,0000,,So the thing here is this.
Dialogue: 0,0:00:39.00,0:00:43.00,Default,,0000,0000,0000,,A reduction that you use to show NP-completeness
Dialogue: 0,0:00:43.00,0:00:46.00,Default,,0000,0000,0000,,is, in a way, a very coarse way of reducing problems to each other.
Dialogue: 0,0:00:46.00,0:00:50.00,Default,,0000,0000,0000,,So coarse that it can destroy approximation factors,
Dialogue: 0,0:00:50.00,0:00:53.00,Default,,0000,0000,0000,,that it can destroy fixed parameter tractability, and so on.
Dialogue: 0,0:00:53.00,0:00:56.00,Default,,0000,0000,0000,,So there are special types of reductions
Dialogue: 0,0:00:56.00,0:01:00.00,Default,,0000,0000,0000,,that will keep approximation factors or fixed parameter tractability.
Dialogue: 0,0:01:00.00,0:01:02.00,Default,,0000,0000,0000,,Unfortunately we can't go deeper into them in this course,
Dialogue: 0,0:01:02.00,0:01:07.00,Default,,0000,0000,0000,,but you should just know that just because two problems are closely related,
Dialogue: 0,0:01:07.00,0:01:11.00,Default,,0000,0000,0000,,that does not mean that algorithmic techniques, such as approximation algorithms,
Dialogue: 0,0:01:11.00,9:59:59.99,Default,,0000,0000,0000,,easily carry over from one problem to the other as well, unfortunately.