1 00:00:00,000 --> 00:00:04,430 The first answer I hope wasn't that difficult to find. This one is true. 2 00:00:04,430 --> 00:00:09,260 The rules of an independent set are that 2 vertices cannot be connected by an edge 3 00:00:09,260 --> 00:00:12,950 if they are part of the independent set, and that means if we were to put this one 4 00:00:12,950 --> 00:00:16,810 into the independent set as well as this one here, then we would have an error here, 5 00:00:16,810 --> 00:00:19,400 which automatically also answers the second question. 6 00:00:19,400 --> 00:00:22,630 It's not the case that both vertices can be in the independent set 7 00:00:22,630 --> 00:00:24,480 because they are connected to each other. 8 00:00:24,480 --> 00:00:26,560 This one here might have been a little bit more tricky. 9 00:00:26,560 --> 00:00:30,380 So at least 1 of the 2 vertices must be in the independent set. 10 00:00:30,380 --> 00:00:32,100 You might be inclined to think that 11 00:00:32,100 --> 00:00:36,050 because we are looking for a maximum size independent set. 12 00:00:36,050 --> 00:00:39,500 But actually, that is not the case, and I will give you a little example for that. 13 00:00:39,500 --> 00:00:42,630 Say we have a very small network like this one here, 14 00:00:42,630 --> 00:00:44,620 and here you have v, here you have u. 15 00:00:44,620 --> 00:00:48,540 Then this network here has an independent set of size 2. 16 00:00:48,540 --> 00:00:51,180 Actually, it has a number of independent sets of size 2, 17 00:00:51,180 --> 00:00:57,850 but there is also 1 independent set of size 2 where v and u are both excluded. 18 00:00:57,850 --> 00:01:01,540 This is a bit different from vertex cover because you can actually have the case 19 00:01:01,540 --> 00:01:06,120 that both vertices are not part of the set even though they are connected by an edge. 20 00:01:06,120 --> 00:01:07,710 So this is false. 21 00:01:07,710 --> 00:01:09,160 Both v and u could be 0. 22 00:01:09,160 --> 00:01:11,970 Yes, this is exactly what is also shown by this example. 23 00:01:11,970 --> 00:01:14,380 You can have the case that both are not part of the independent set, 24 00:01:14,380 --> 00:01:16,550 so this is definitely a yes here. 25 00:01:16,550 --> 00:01:19,780 Do we have to set both vertices to 0? No. 26 00:01:19,780 --> 00:01:23,500 This is also not the case because, for example, you could also have an independent set here 27 00:01:23,500 --> 00:01:25,190 that you construct in this way. 28 00:01:25,190 --> 00:01:27,590 You put u in and this one out. 29 00:01:27,590 --> 00:01:30,290 So now we have also found a maximum size independent set, 30 00:01:30,290 --> 00:01:33,160 but we have included 1 of the 2 vertices. 31 00:01:33,160 --> 00:01:35,090 So this one here is clearly also not true. 32 00:01:35,090 --> 00:01:37,720 If you take all of those observations together, it's pretty cool 33 00:01:37,720 --> 00:01:40,490 because this now gives us a new search tree strategy 34 00:01:40,490 --> 00:01:42,380 that is actually quite similar to vertex cover. 35 00:01:42,380 --> 00:01:45,000 So we have our 2 vertices, v and u, here. 36 00:01:45,000 --> 00:01:49,940 Just as we did with vertex cover, we can spread into 3 different possibilities. 37 00:01:49,940 --> 00:01:54,160 The first one is we take v into the independent set but not u. 38 00:01:54,160 --> 00:01:56,790 The second one is exactly the other way around. 39 00:01:56,790 --> 00:01:58,330 We do not take v but we take u. 40 00:01:58,330 --> 00:02:01,170 And finally, it is possible that both are excluded. 41 00:02:01,170 --> 00:02:03,920 As long as we find an edge between 2 vertices, v and u, 42 00:02:03,920 --> 00:02:08,070 for which v has no assignment yet and u has no assignment yet, 43 00:02:08,070 --> 00:02:11,690 then we can branch into exactly 3 possibilities. 44 00:02:11,690 --> 00:02:16,800 Now, what happens if either v or u already has an assignment? 45 00:02:16,800 --> 00:02:19,280 For vertex cover I told you what would happen then. 46 00:02:19,280 --> 99:59:59,999 This time I will let you figure this out.