﻿[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.