English subtitles

← 13ps-12 Reduction Power 2 Solution

Get Embed Code
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.