• Managing your videos in Amara teams just got easier! Read about it in our latest blog post. Hide

## ← 06-05 Vertex Cover With if-better

• 1 Follower
• 14 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=qRJiqgWLCdY" data-team="udacity"></div> ``` 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.