English subtitles

← 06-05 Vertex Cover With if-better

Get Embed Code
1 Language

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

  1. And the solution here is if we have the if_better function available, then we can solve
  2. vertex cover in polynomial time because as we said the if_better function works in polynomial time
  3. and we're calling it once for each vertex in the graph.
  4. So we're calling it n times it works in polynomial time so this part here of finding the
  5. best possible assignment of theirs and once to the vertices that works in polynomial time.
  6. And as you know from before, checking if an assignment is valid and checking the size
  7. of an assignment that's also doable in polynomial time.
  8. So the total running time of the algorithm is polynomial in n the number of vertices,
  9. and the right thing is that, although you shouldn't probably anthropomorphise this,
  10. the if_better function always knows what will help us.
  11. So if we were trying to solve clique or independent set instead of vertex cover,
  12. the if_better function would somehow know this and give us a different assignment
  13. of 0s and 1s to the vertices, which would however still be guaranteed to be optimal,
  14. and that is what make this function so extremely powerful.