English subtitles

← 13ps-11 Reduction Power 2

Get Embed Code
1 Language

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

  1. Let's build off this a little bit.
  2. Let's do that by taking all of these vertices that have k+1 edges or more and actually putting them
  3. in the cover and that's because we already said it has to be in the cover.
  4. Now, what we can do is actually remove these vertices from the graph and any edges
  5. connected to them because those edges are automatically covered
  6. so we don't have to worry about them anymore.
  7. We automatically are dealing with a much smaller graph or potentially much smaller graph.
  8. What this tells us is that after removing these vertices, each remaining vertex can cover
  9. at most a certain number of edges if it's put in a cover, and this could either be--
  10. k-1, k, k+1, 2k, or k² edges.
  11. What this would then mean is that the remaining graph can't have no more than a
  12. certain number of edges if G is a "Yes" instance of the vertex cover decision problem,
  13. which is the original assumption that we made, and this can either be k-1, k, k+1, 2k, or k².
  14. So please check whichever is appropriate for both of these questions.