## 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