WEBVTT
00:00:00.000 --> 00:00:04.430
The first answer I hope wasn't that difficult to find. This one is true.
00:00:04.430 --> 00:00:09.260
The rules of an independent set are that 2 vertices cannot be connected by an edge
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
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,
00:00:16.810 --> 00:00:19.400
which automatically also answers the second question.
00:00:19.400 --> 00:00:22.630
It's not the case that both vertices can be in the independent set
00:00:22.630 --> 00:00:24.480
because they are connected to each other.
00:00:24.480 --> 00:00:26.560
This one here might have been a little bit more tricky.
00:00:26.560 --> 00:00:30.380
So at least 1 of the 2 vertices must be in the independent set.
00:00:30.380 --> 00:00:32.100
You might be inclined to think that
00:00:32.100 --> 00:00:36.050
because we are looking for a maximum size independent set.
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.
00:00:39.500 --> 00:00:42.630
Say we have a very small network like this one here,
00:00:42.630 --> 00:00:44.620
and here you have v, here you have u.
00:00:44.620 --> 00:00:48.540
Then this network here has an independent set of size 2.
00:00:48.540 --> 00:00:51.180
Actually, it has a number of independent sets of size 2,
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.
00:00:57.850 --> 00:01:01.540
This is a bit different from vertex cover because you can actually have the case
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.
00:01:06.120 --> 00:01:07.710
So this is false.
00:01:07.710 --> 00:01:09.160
Both v and u could be 0.
00:01:09.160 --> 00:01:11.970
Yes, this is exactly what is also shown by this example.
00:01:11.970 --> 00:01:14.380
You can have the case that both are not part of the independent set,
00:01:14.380 --> 00:01:16.550
so this is definitely a yes here.
00:01:16.550 --> 00:01:19.780
Do we have to set both vertices to 0? No.
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
00:01:23.500 --> 00:01:25.190
that you construct in this way.
00:01:25.190 --> 00:01:27.590
You put u in and this one out.
00:01:27.590 --> 00:01:30.290
So now we have also found a maximum size independent set,
00:01:30.290 --> 00:01:33.160
but we have included 1 of the 2 vertices.
00:01:33.160 --> 00:01:35.090
So this one here is clearly also not true.
00:01:35.090 --> 00:01:37.720
If you take all of those observations together, it's pretty cool
00:01:37.720 --> 00:01:40.490
because this now gives us a new search tree strategy
00:01:40.490 --> 00:01:42.380
that is actually quite similar to vertex cover.
00:01:42.380 --> 00:01:45.000
So we have our 2 vertices, v and u, here.
00:01:45.000 --> 00:01:49.940
Just as we did with vertex cover, we can spread into 3 different possibilities.
00:01:49.940 --> 00:01:54.160
The first one is we take v into the independent set but not u.
00:01:54.160 --> 00:01:56.790
The second one is exactly the other way around.
00:01:56.790 --> 00:01:58.330
We do not take v but we take u.
00:01:58.330 --> 00:02:01.170
And finally, it is possible that both are excluded.
00:02:01.170 --> 00:02:03.920
As long as we find an edge between 2 vertices, v and u,
00:02:03.920 --> 00:02:08.070
for which v has no assignment yet and u has no assignment yet,
00:02:08.070 --> 00:02:11.690
then we can branch into exactly 3 possibilities.
00:02:11.690 --> 00:02:16.800
Now, what happens if either v or u already has an assignment?
00:02:16.800 --> 00:02:19.280
For vertex cover I told you what would happen then.
00:02:19.280 --> 99:59:59.999
This time I will let you figure this out.