Return to Video

13ps-11 Reduction Power 2

  • 0:00 - 0:02
    Let's build off this a little bit.
  • 0:02 - 0:09
    Let's do that by taking all of these vertices that have k+1 edges or more and actually putting them
  • 0:09 - 0:14
    in the cover and that's because we already said it has to be in the cover.
  • 0:14 - 0:20
    Now, what we can do is actually remove these vertices from the graph and any edges
  • 0:20 - 0:23
    connected to them because those edges are automatically covered
  • 0:23 - 0:25
    so we don't have to worry about them anymore.
  • 0:25 - 0:31
    We automatically are dealing with a much smaller graph or potentially much smaller graph.
  • 0:31 - 0:38
    What this tells us is that after removing these vertices, each remaining vertex can cover
  • 0:38 - 0:43
    at most a certain number of edges if it's put in a cover, and this could either be--
  • 0:43 - 0:49
    k-1, k, k+1, 2k, or k² edges.
  • 0:49 - 0:53
    What this would then mean is that the remaining graph can't have no more than a
  • 0:53 - 0:59
    certain number of edges if G is a "Yes" instance of the vertex cover decision problem,
  • 0:59 - 1:08
    which is the original assumption that we made, and this can either be k-1, k, k+1, 2k, or k².
  • 1:08 -
    So please check whichever is appropriate for both of these questions.
Title:
13ps-11 Reduction Power 2
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
01:13
Amara Bot added a translation

English subtitles

Revisions