WEBVTT

00:00:00.000 --> 00:00:04.000
Most of this problem is that it's going to involve building an improved search tree

00:00:04.000 --> 00:00:06.000
for the vertex cover problem.

00:00:06.000 --> 00:00:11.500
So in order to start off with that, let's go ahead and try building the naive approach

00:00:11.500 --> 00:00:15.000
which is very similar to what you did in problem set 1, if you'd like to

00:00:15.000 --> 00:00:17.000
take a look back at that very quickly.

00:00:17.000 --> 00:00:19.000
Let's take a look at this.

00:00:19.000 --> 00:00:23.500
I'd like you to fill in a function, recursive vertex cover, that takes an input graph,

00:00:23.500 --> 00:00:29.000
which is a list of lists, and an assignment, which is a list of vertices that we cover

00:00:29.000 --> 00:00:33.000
and then builds the search tree from that.

00:00:33.000 --> 00:00:37.000
So what your code should do--first, it should check if it's still possible

00:00:37.000 --> 00:00:39.000
to construct a valid vertex cover.

00:00:39.000 --> 00:00:44.000
If not, you should return float inf, the Python expression for infinity.

00:00:44.000 --> 00:00:48.000
If the assignment is a valid vertex cover, then you return the size of that cover.

00:00:48.000 --> 00:00:53.000
Otherwise, I want you to find a vertex v that does not have an assignment.

00:00:53.000 --> 00:00:57.000
And, once again, I'd recommend checking out the naive algorithm

00:00:57.000 --> 00:00:59.000
you implemented in problem set 1

00:00:59.000 --> 99:59:59.999
for a different NP problem that is very similar to this one.