English subtitles

← 16-06 Carrying Properties Over Reductions

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. So unfortunately the factor-2 approximation that we have found for vertex cover
  2. does not carry over to clique or independent set.
  3. Well we've only shown that it doesn't carry over to independent set,
  4. but since independent set and clique are, again, so closely connected
  5. you can already see or at least guess why it doesn't carry over here as well.
  6. And I've actually mentioned a similar thing to you in the last unit
  7. when we talked about fixed parameter tractability.
  8. Where it was also the case that if you took the size of the optimum solution as a parameter,
  9. there is a parameterized algorithm for vertex cover,
  10. but clique and independent set are both not fixed parameter tractable.
  11. So the thing here is this.
  12. A reduction that you use to show NP-completeness
  13. is, in a way, a very coarse way of reducing problems to each other.
  14. So coarse that it can destroy approximation factors,
  15. that it can destroy fixed parameter tractability, and so on.
  16. So there are special types of reductions
  17. that will keep approximation factors or fixed parameter tractability.
  18. Unfortunately we can't go deeper into them in this course,
  19. but you should just know that just because two problems are closely related,
  20. that does not mean that algorithmic techniques, such as approximation algorithms,
  21. easily carry over from one problem to the other as well, unfortunately.