0:00

Well, I'm really happy to see you because if you made it that far, it basically

Â means that you have successfully, you know, done the knapsack, you know,

Â assignments and you are still willing to continue in the class.

Â So, this is about coloring, and this is when things get more difficult.

Â This is a very fantastic, amazingly beautiful assignment.

Â You'll see that, okay. Conceptually, it's amazingly simple,

Â right? So, we saw in the lecture, you have

Â notes, you have edges between the notes. You want to color these things with as

Â few colors as possible, okay. Such that two adjacent vertices are given

Â a different color, okay. So, this is a beautiful graph.

Â We've actually four nodes. It's a tree, so we could so optimal

Â solutions very quickly, okay. And this is a particular solution.

Â We've one node which is blue, another node red.

Â Two green nodes, okay. And so we are using three colors, okay.

Â So, this is what we will have to solve, okay.

Â So this is the formalization of the problem, okay.

Â You can look at it, okay. But, essentially the important things

Â here is that we have a certain number of node and we have a certain number of

Â edges, you know E. And that's what's going to drive the

Â input of this assignment, okay. And we'll have a long, long, long list of

Â edges because some of the problems we'll solve here are going to be pretty, pretty

Â interesting in some societies, okay. So, we have a decision variable for

Â everyone of the nodes and that's going to be the color of that node.

Â That's going to be the output of this assignment, okay.

Â So the assignment itself is basically minimizing the largest color that you are

Â using. We are using numbers here, okay.

Â So, you know, mini-, max, minimizing the maximum color that we are using, okay.

Â And then we have only a single constraint which is reasonably easy.

Â You know, two different, two adjacent vertices have to be given a different

Â color, okay. So, when you look at this, you have to

Â know what the input and the output are going to be, okay.

Â So, the input here is going to have basically two ints, okay.

Â The beginning that will tell you the size of the number of vertices, and then the

Â number of edges, that's the two things that you will see there, okay.

Â Number of vertices, number of number of edges.

Â And then what you will have is a long list of edges, okay.

Â Now an edge is basically defined by what? By essentially two vertices, okay.

Â So, every line here that you see, the input is going to be basically telling

Â you that there is an edge between, you know, the first vertex and the second

Â vertex, okay. And, so that's basically going to be the

Â input. So, the input is basically how many

Â nodes, you know, how many, how many vertex, how many edges between these

Â vertices. And then a long list of what these edges

Â are. And that's just basically two, two

Â vertices, okay. Now the output is going to be as usual,

Â okay. So, what is the optimal solutions that

Â you, or the best solutions that you have found?

Â And whether it's optimal or not, okay. And then you will have also the colors of

Â all these vertices, okay. So, for everyone of the vertex, you know,

Â you will basically specify its color in the optimal well or the best form

Â solution, okay. So, that's the basic idea, okay.

Â This is a particular example, okay. So, you see that we have basically three

Â vertices we have four vertices and three edges, okay.

Â Those what you see there. And these are the various edges.

Â We have an edge between node zero and node one, vertex zero, vertex one.

Â We have another edge between vertex one and vertex two, and so on and so forth,

Â that's what you see, okay. And then you see a particular of

Â solutions there, which has basically three colors.

Â And it's not proven optimal, and you see the various colors of these things 0122,

Â okay. So, that's basically input.

Â Very simple, long list essentially of edges and then the output, which is

Â basically the color of every one of these vertices, okay.

Â So, input output is very simple in this problem, okay.

Â It's conceptually a very simple problem. But graph coloring is this beautiful

Â property that is very very difficult to solve, okay.

Â yeah, and this is an illustration of actually the two solution, the solutions

Â that we just produce here. so let me give you some assignment tips

Â here, okay. So, one other thing which is important

Â whatever the, whatever the approach that you're actually using.

Â Is that, you know, the degree of a node is important.

Â The higher the degree of a node, you know, the more difficult it is, the more

Â constrained that node is in a sense. You know, what the color that node can

Â take is basically limited by all it's neighbors, okay.

Â So, think about how that information can be exploited, okay.

Â So, other things that you have to think about is that there are a lot and lot of

Â symmetries in these problems, okay. So, we had a lot of lectures on

Â symmetries inside the constrained programming lecture.

Â Think about them, and think how they can be exploited inside this particular

Â assignment, okay. So, what you see there is the solution

Â there, okay. So, this is a solution, this is a

Â solution which is completely symmetric, okay.

Â You know, think about why these two things are symmetric.

Â There is a very simple rule and, you know, this is essentially some of the

Â techniques that we have seen in constrain programming there, for telling you what

Â kind of symmetry this is. But, this can be exploited and if want or

Â find actually, you know, very good solution and improve optimality, you will

Â have to use things like this, okay. And then, there are other things that you

Â want to do if, you know, if you want to improve optimality or if you want to

Â find, you know, to get a, a sense of what your solution is.

Â Try to find if they are easy lower bound that you can compute.

Â There is one very simple conceptual lower bound that you can take, and that will

Â tell you the best you can ever achieve, okay.

Â So, you know, there are lot of structure here, although the problem is very simp-,

Â you know it's very simple conceptually but there are lot of things that you can

Â exploit and that's why I love this problem, okay.

Â Now this is a beautiful graph here, you know, this is 250 vertices, it's about

Â 3000 edges, okay. Which basically means that the density

Â here the den, you know, the density of the edges is 0.1% compared to the full

Â graph, okay. It's a reasonably easy answer.

Â I mean it's medium difficulty. It's still hard to prove optimality, but

Â this is not some of the most difficult, this is not one of the most difficult

Â instance. Now you can imagine a bushy, you know, it

Â becomes when you have 50% density, okay. So, that's much more complex and much

Â more difficult to solve, okay. So, so, this is essentially, you know,

Â what I wanted to tell you about the graph coloring assignment.

Â You can be really, really creative on this assignment.

Â It's a fantastic assignment, okay. And I look forward to see you compete in

Â finding a high-quality solution and proving optimality on some of these

Â instances. Okay, have fun, it's going to be really

Â interesting.

Â