## ← 13ps-12 Reduction Power 2 Solution

• 1 Follower
• 15 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=pn71AXKpFB8" data-team="udacity"></div> ``` 1 Language

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

1. So the answer to this first question is k and that's because--well, we've already gotten rid

2. of any vertices that have k+1 edges or more, so all the remaining vertices
3. can have at most k edges connected to them.
4. Now, to answer this final problem, we have to remember that we said earlier
5. that at most k vertices are needed to cover the entire graph.
6. Well, if there are k vertices necessary to cover the graph and each vertex has at most
7. k edges attached to it, then the remaining graph can have no more than
8. k² edges since we have to cover all of them.
9. Now, this might have seem that we were involved, but there's actually something powerful here.
10. What this means is that after doing all of these little pre-processing steps, then we either know
11. that the graph G is not a "Yes" instance of the vertex cover decision problem--
12. in other words, it's a "No" instance or we know that the size of the resulting graph is bounded
13. not as a function of n, which it was originally, but rather as a function of k,
14. and remember what we said earlier that very often k is far less than n.
15. So this is potentially a very big win for us.