[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:04.43,Default,,0000,0000,0000,,The first answer I hope wasn't that difficult to find. This one is true.
Dialogue: 0,0:00:04.43,0:00:09.26,Default,,0000,0000,0000,,The rules of an independent set are that 2 vertices cannot be connected by an edge
Dialogue: 0,0:00:09.26,0:00:12.95,Default,,0000,0000,0000,,if they are part of the independent set, and that means if we were to put this one
Dialogue: 0,0:00:12.95,0:00:16.81,Default,,0000,0000,0000,,into the independent set as well as this one here, then we would have an error here,
Dialogue: 0,0:00:16.81,0:00:19.40,Default,,0000,0000,0000,,which automatically also answers the second question.
Dialogue: 0,0:00:19.40,0:00:22.63,Default,,0000,0000,0000,,It's not the case that both vertices can be in the independent set
Dialogue: 0,0:00:22.63,0:00:24.48,Default,,0000,0000,0000,,because they are connected to each other.
Dialogue: 0,0:00:24.48,0:00:26.56,Default,,0000,0000,0000,,This one here might have been a little bit more tricky.
Dialogue: 0,0:00:26.56,0:00:30.38,Default,,0000,0000,0000,,So at least 1 of the 2 vertices must be in the independent set.
Dialogue: 0,0:00:30.38,0:00:32.10,Default,,0000,0000,0000,,You might be inclined to think that
Dialogue: 0,0:00:32.10,0:00:36.05,Default,,0000,0000,0000,,because we are looking for a maximum size independent set.
Dialogue: 0,0:00:36.05,0:00:39.50,Default,,0000,0000,0000,,But actually, that is not the case, and I will give you a little example for that.
Dialogue: 0,0:00:39.50,0:00:42.63,Default,,0000,0000,0000,,Say we have a very small network like this one here,
Dialogue: 0,0:00:42.63,0:00:44.62,Default,,0000,0000,0000,,and here you have v, here you have u.
Dialogue: 0,0:00:44.62,0:00:48.54,Default,,0000,0000,0000,,Then this network here has an independent set of size 2.
Dialogue: 0,0:00:48.54,0:00:51.18,Default,,0000,0000,0000,,Actually, it has a number of independent sets of size 2,
Dialogue: 0,0:00:51.18,0:00:57.85,Default,,0000,0000,0000,,but there is also 1 independent set of size 2 where v and u are both excluded.
Dialogue: 0,0:00:57.85,0:01:01.54,Default,,0000,0000,0000,,This is a bit different from vertex cover because you can actually have the case
Dialogue: 0,0:01:01.54,0:01:06.12,Default,,0000,0000,0000,,that both vertices are not part of the set even though they are connected by an edge.
Dialogue: 0,0:01:06.12,0:01:07.71,Default,,0000,0000,0000,,So this is false.
Dialogue: 0,0:01:07.71,0:01:09.16,Default,,0000,0000,0000,,Both v and u could be 0.
Dialogue: 0,0:01:09.16,0:01:11.97,Default,,0000,0000,0000,,Yes, this is exactly what is also shown by this example.
Dialogue: 0,0:01:11.97,0:01:14.38,Default,,0000,0000,0000,,You can have the case that both are not part of the independent set,
Dialogue: 0,0:01:14.38,0:01:16.55,Default,,0000,0000,0000,,so this is definitely a yes here.
Dialogue: 0,0:01:16.55,0:01:19.78,Default,,0000,0000,0000,,Do we have to set both vertices to 0? No.
Dialogue: 0,0:01:19.78,0:01:23.50,Default,,0000,0000,0000,,This is also not the case because, for example, you could also have an independent set here
Dialogue: 0,0:01:23.50,0:01:25.19,Default,,0000,0000,0000,,that you construct in this way.
Dialogue: 0,0:01:25.19,0:01:27.59,Default,,0000,0000,0000,,You put u in and this one out.
Dialogue: 0,0:01:27.59,0:01:30.29,Default,,0000,0000,0000,,So now we have also found a maximum size independent set,
Dialogue: 0,0:01:30.29,0:01:33.16,Default,,0000,0000,0000,,but we have included 1 of the 2 vertices.
Dialogue: 0,0:01:33.16,0:01:35.09,Default,,0000,0000,0000,,So this one here is clearly also not true.
Dialogue: 0,0:01:35.09,0:01:37.72,Default,,0000,0000,0000,,If you take all of those observations together, it's pretty cool
Dialogue: 0,0:01:37.72,0:01:40.49,Default,,0000,0000,0000,,because this now gives us a new search tree strategy
Dialogue: 0,0:01:40.49,0:01:42.38,Default,,0000,0000,0000,,that is actually quite similar to vertex cover.
Dialogue: 0,0:01:42.38,0:01:45.00,Default,,0000,0000,0000,,So we have our 2 vertices, v and u, here.
Dialogue: 0,0:01:45.00,0:01:49.94,Default,,0000,0000,0000,,Just as we did with vertex cover, we can spread into 3 different possibilities.
Dialogue: 0,0:01:49.94,0:01:54.16,Default,,0000,0000,0000,,The first one is we take v into the independent set but not u.
Dialogue: 0,0:01:54.16,0:01:56.79,Default,,0000,0000,0000,,The second one is exactly the other way around.
Dialogue: 0,0:01:56.79,0:01:58.33,Default,,0000,0000,0000,,We do not take v but we take u.
Dialogue: 0,0:01:58.33,0:02:01.17,Default,,0000,0000,0000,,And finally, it is possible that both are excluded.
Dialogue: 0,0:02:01.17,0:02:03.92,Default,,0000,0000,0000,,As long as we find an edge between 2 vertices, v and u,
Dialogue: 0,0:02:03.92,0:02:08.07,Default,,0000,0000,0000,,for which v has no assignment yet and u has no assignment yet,
Dialogue: 0,0:02:08.07,0:02:11.69,Default,,0000,0000,0000,,then we can branch into exactly 3 possibilities.
Dialogue: 0,0:02:11.69,0:02:16.80,Default,,0000,0000,0000,,Now, what happens if either v or u already has an assignment?
Dialogue: 0,0:02:16.80,0:02:19.28,Default,,0000,0000,0000,,For vertex cover I told you what would happen then.
Dialogue: 0,0:02:19.28,9:59:59.99,Default,,0000,0000,0000,,This time I will let you figure this out.