[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:05.53,Default,,0000,0000,0000,,So the answer to this first question is k and that's because--well, we've already gotten rid
Dialogue: 0,0:00:05.53,0:00:10.79,Default,,0000,0000,0000,,of any vertices that have k+1 edges or more, so all the remaining vertices
Dialogue: 0,0:00:10.79,0:00:13.84,Default,,0000,0000,0000,,can have at most k edges connected to them.
Dialogue: 0,0:00:13.84,0:00:19.23,Default,,0000,0000,0000,,Now, to answer this final problem, we have to remember that we said earlier
Dialogue: 0,0:00:19.23,0:00:24.90,Default,,0000,0000,0000,,that at most k vertices are needed to cover the entire graph.
Dialogue: 0,0:00:24.90,0:00:31.80,Default,,0000,0000,0000,,Well, if there are k vertices necessary to cover the graph and each vertex has at most
Dialogue: 0,0:00:31.80,0:00:37.92,Default,,0000,0000,0000,,k edges attached to it, then the remaining graph can have no more than
Dialogue: 0,0:00:37.92,0:00:41.24,Default,,0000,0000,0000,,k² edges since we have to cover all of them.
Dialogue: 0,0:00:41.24,0:00:46.04,Default,,0000,0000,0000,,Now, this might have seem that we were involved, but there's actually something powerful here.
Dialogue: 0,0:00:46.04,0:00:51.60,Default,,0000,0000,0000,,What this means is that after doing all of these little pre-processing steps, then we either know
Dialogue: 0,0:00:51.60,0:00:57.80,Default,,0000,0000,0000,,that the graph G is not a "Yes" instance of the vertex cover decision problem--
Dialogue: 0,0:00:57.80,0:01:04.20,Default,,0000,0000,0000,,in other words, it's a "No" instance or we know that the size of the resulting graph is bounded
Dialogue: 0,0:01:04.20,0:01:09.80,Default,,0000,0000,0000,,not as a function of n, which it was originally, but rather as a function of k,
Dialogue: 0,0:01:09.80,0:01:15.46,Default,,0000,0000,0000,,and remember what we said earlier that very often k is far less than n.
Dialogue: 0,0:01:15.46,9:59:59.99,Default,,0000,0000,0000,,So this is potentially a very big win for us.