And so, so in a sense we're going to have two kinds of notes.

We're going to have the notes for the valuables and the notes for the values.

Okay? So, these are the notes for the values,

you see value 1, value 2, value 3, and so on.

You see the set, and then essentially, if a variable can take a value, we are

going to draw a match between the variables and the values.

So, when you see x1 over there, x1 can take the value 1, x1 can take the value

2. Okay?

Now, you look, we look at val, variable two.

You know, variable two can take value two and three, so we going to put an edge

from x2 to 2 and an edge from x2 to 3. And we do that for all the variables.

And then you get this beautiful graph, you know?

Where there is an edge between the variable and the value, if essentially

the value is in the domain of the variable.

Okay? Note so far we hav you know we haven't

done very much, except doing a very nice picture.

Okay? And once again you know, with this

representation, can you see that x4 cannot take the value 2.

Okay? Now, so the first thing that we have to

do is to find out if this constraint is feasible.

Okay? That's always the first step.

You know, we have the constraints, we have a set of domain for the variable,

can we find a feasible solution. Okay?

So, what you see here, this is a feasible solution.

Okay? So you see that the variable x1 here is

assigned a value of 1, you see that the variable x2 is assigned to the value 2

and so on. What is nice here, is that you see these

blue arrow representing the solutions. It's okay, blue arrows.

This is, we're going to do that over and over again in this lecture.

Okay? But essentially what we want is that

every one of the variables on the top, you know, are assigned a blue edge.

Okay? That means that they have assigned a

value. And when you look at the values at the

bottom, we want at most one of the blue arrows to come to them.

Because if there would be two arrows, that basically means that two variables

are assigned to the same value and therefore they are not different, right?

Okay? So that's basically the idea.

Okay? So it's going to be feasible if you have

an arrow going from the top to the bottom and there is one going from, one you

know, leaving every variable and at most one arriving tt every one of the values.

Okay? So this is a feasible solution for

instance. Okay?

So what we did here was just creating a bipartite graph.

And aloso a bipartite graph is a graph with two types of vertices, and edges are

between vertices of different types. Okay?

In the particular case of the all-different constraints, you have one

type of vertices, the, the top ones which are the variables.

And then we have the bottom ones which are the values and there is an edge

between the variable, and the value if the value is in the domain of the

variable. That's what we have done so far.

Okay? So, in a sense you see that this is the

first you know, set in the by product graph, that's the variable, you see the

set of variables at the bottom. Okay?

And once again you have an edge between the variable and value If that value is

in the domain of the variable. Okay?

Now, what we just did when I show you a solution was finding a matching.

What is a matching? That's a basic concept in graph theory.

And, if you have a graph, you know, with a set of vertices V, and a set of edges

E, okay? So, matching is going to be a set of

edge, E such that No two edge in E are sharing a vertex.

Okay? So if you select an edge, you can never

select another edge which is basically using one of the vertices of that edge.

Okay? And then the maximum matching is going to

be the matching where you have the large number, where you have selected the

largest number of edges inside E. Okay?

And so the constraint of course is as soon as you select an edge, you select

two vertices and these vertices can not be selected any other edges.

So you have to select these edges carefully.

Okay? And so why is this interesting?

Because essentially feasibility is the, the basically feasibility amounts to

finding the maximum matching. If you find the maximum matching there

are two cases right? One of the cases is that you know,the,

the maximum matching is a size which is, you know, equal to the number of

variables. That basically means that all the

variables have been assigned. And by definition of the matching they

are assigned a different value. Okay?

And you know at that point that the constraint is feasible.

If the maximum matching is smaller than the number of variables, okay, that

basically means that there is no feasible solution.

There is one or more variables that I cannot assign.

I would have to assign a value which is already taken by another variable.

Okay? So, in a sense, what I'm telling you is,

feasibility here equals matching, okay? So, so now we have, basically, this is an

example. Okay?

So you see, you know, once again, the variable, the value at the top.

You see these blue edges, beautiful. There is a, there is one edge leaving

every variable. You know, most one edge arriving at every

values and know that this constraint is feasible.

This is another example, okay? So you see this is this is essentially,

once again the valuable, the value, this is a different set of domains here.

Okay? And I can try to find the maximum

matching. And this is what I get.

At this point, what you see is this matching is only five edges, and I have

six variable. So, you know, that the constraint isn't

feasible. Okay?

So when you look at the variable X3 over there, you can see that I can't match any

of these edges. I can use, I cannot use any of these

edges because the values there are already taken.

Okay? So essentially the maximum matching here

is of size five, I have six variable, the constraint is not feasible.

Okay, so essentially now I know that if I can find a maximum matching, I will be

able to decide if the constraint is feasible or not.

Okay? So how do I find this beautiful matching?

Okay? So I start with any matching, and then

I'm going to try to improve that. Okay?

So and when no improvement is, is going to be possible, that basically

means that I have a maximum matching. So it's a simple improvement algorithm.

I start from any matching. Maybe a matching with nothing in it, and

then I improve it. And when I'm stuck, I can't improve it, I

know that I have a feasible matching. Of course, I haven't defined what it

means to improve a matching, but I'm going to do that in the next slide.

Okay? So, here, this is a, this is a matching.

Okay? So you see that the variable x3, x4, x5,

and x6 are basically matched. The variable x1 and x2 are not.

Okay? So what I want to do now is improve this

matching. Okay?

So I can do, I can essentially, we place the edges x4, which is assigned to 2, and

the edge x2 to 2. Okay?

I can replace the x, sorry, I can replace the, the edge x4 to 2 by the x, the edges

X2 to 2 and X4 to 4. Okay.

If I do that, I remove one edge, and I have two new edges.

Okay? And what I get is a better matching.

Now five of the variables are matched. Okay.

I can keep on improving this matching. Okay?

I can essentially replace the the edge x3 as assigned to 1 by three new edges.

Okay? actually I also ought to remove x5 to 3

and I replace them by (x1,1), (X3,3) and (x5, 5).

Okay? So I remove two edges and I replace them

by three new ones. And then I get this beautiful matching

[UNKNOWN], where essentially all the variables are matched.

I have a maximum matching, and I will know that this constraint is feasible.

So what I basically did was always selecting one edge and replacing by two,

or selecting two edges and replacing by three.

And that's how I improve the matching. Okay?

Now, this is not precise enough, and I'm going to go into more details now.

Okay? So once again, what we're going to do,

start with a matching, improve the matching.

How do we improve a matching? Okay?

So what we will do is find a free vertex, and that will be in the particular case

of the all-different, finding a variable which is not assigned a value.

Okay? And now there are two cases.

Okay? The first case is, is the case where I

can find a value, which is unmatched. That basically means that that value is

free, no other variable is assigned to that value.

If I can do that, obviously I can improve the matching.

Okay? And I can put that edge in the matching,

and then start again trying to continue improving that matching.

Now, the more interesting case is when that variable you know, cannot be

assigned to any other values at this point because all these values are taken.

Okay? So what I do in that case is that I take

that value, I assign it to the particular variable.

Now I take the variable which is currently assigned to that value, I

remove the edge between them, and then I start again with that variable.

Okay? And I try to find you know, an assignment

for that variable to a value in the same way as I did for the origin of free

variable. Okay?

Let me illustrate that. Okay?

So we've once again this beautiful matching, we've only you know you know,

variables assigned. Okay?

I'm trying to see how I can improve it. So, I select the variable x2 which is

free, and the value 2. Okay?

So, this is what you see there. You see the variable x2 is free.

No, no, no value, it has no value assigned to it.

I take the value 2, but the value two you can see is assigned to the var, to the

variable x4. Therefore, what I have to do is

essentially remove the edge between x4 and 2.

Okay? And start again with the variable x4.

Okay? So I remove x2 to 2.

Okay? And then I consider variable x4 at this

point. Okay?

And, so I start again, so you see the variable x4 now is free.

Okay? And I look, if I can find a value for

that particular variable. Okay?

Such that I can improve the matching. Okay?

What is nice in this particular case, is that I can assign the value X4 to the

value 4. Okay?

And therefore I even improve matching. So, what I did was essentially adding two

edges, one from x2 to x to 2, and one from x4 to 4.

And I remove only one edge, the edge x4 to 2, which is basic, which was in the

matching before. So I remove one edge from the matching, I

have added two new edge which were not in the matching.

So I improve my matching. Okay?

So, that's the basic idea. So essentially what I'm using here is

what is called an alternating path. Okay?

So, if I have a matching, an alternating path from a free vertex in x, you know

the top set of, the top of vertices, to a vi, to a vi, to a vertex in v okay, as a

set of value. It's going to be a path, you know,

essentially, from, from this variable x to the variable v, where the edge are

going to alternate between being not in the matching and being in the matching.

So I'm going to start from x, take an edge which is not in the matching, go

back to the top of an edge, which is in the matching, and go to the bottom with

an edge, which is not in the matching, and so on.

Okay? Until I fin, I can assign that particle

of variable to a value which is not taken by any other vertices.

Okay? Now, there is an odd number of edges

here, why? Because I start from the top and I end up

at the bottom. Okay?

So to go from the top to the bottom, you know I need one edge.

Every time I go up and down, this is an even number of edges.

So we're basically I will have an odd number of edges.

And this is really important, right? Because if I have an odd number of edges,

and I always start by taking something which is not in the matching, I know that

I will increase you know, the number of edge inside the matching by one.

Okay? So I'm improving essentially the

matching. Okay?

I remove let's say k edge region area inside the matching and I add, k mine, k

plus 1 edges, which are not in the match. Really good.

Okay? So these alternating paths essentially,

are allowing me to improve the matching. Okay?

So, how do I find this alternating path? You can see I'm basically moving step by

step, refining this concept one at a time.

And this is the final step, okay? So, I'm basically telling you what the

algorithm is. You have to create a directed graph.

Okay? given a particular matching.

Okay? Now, the edge of the matching are

going to be oriented top to, from the bottom to the top.

Okay? So these edges are going to allow me to

go to the top. And the edges which are not in the

matching are going to be oriented from the top to the bottom.

I'm basically, we'll be able to assign a value to a particular variable.

Okay? So this is essentially the illustration

for the examples that you've seen. So, you see these blue edges now, you

know, they are oriented to the top. Okay?

And the other edges, the edges which are not in the matching, are oriented from

the top to the bottom. Now I have a derivative graph, right?

And remember, what I want to do is to find a path from a free vertex to another

free vertex, on the top, to a free vertex at the bottom.

So when I'm going to go down, I have to take an edge which is going down and

those edges are basically not in the matching.

And then I can only go up with up with edges which are in the matching.

So I'm going to down, up, down, up. You know?

Not in the matching, in the matching, not in the matching, in the matching.

And now I can follow the direction of these edges.

Okay? So essentially, this is, this is what I

have done. Okay?

So I create a directed graph, I take the edges which are in the matching, I

re-orient it from the bottom to the top. Okay?

And the other edges are oriented from the top to the bottom.

And now essentially an alternating path ,is starting at the top and following

these oriented edges until it reaches a free vertex at the bottom.

Okay? I start at the top in a free vertex.

I'm following these directed edges until I reach a free vertex at the bottom, and

then I'm happy. Okay?

I can find an alternating path, and therefore I can improve my matching.

Okay? so look at this.

Okay? So this again a beautiful graph oriented,

and then I'm basically highlighting the vertex which are free at this point.

You can see that x1 and x2 are free at the level of the values you have 4, 5 and

7, which are free. Okay?

So what do I do? I start from something which is free and

then I try to see, to follow a path until I get to something which is free at the

bottom. Okay?

So I, so this is one of these beautiful path.

Right? So you start from x2, you go to value 3

and then you go up to variable x5 and then you go down to to value 4.

Okay? So once again it's nice, you know, you

start at the top, you, you go to the bottom, with and edge which is not in the

matching, take an edge which is in the matching to go back up, and then go down

again. Okay?

And though, I can't replace these things by the edges which are in the matching,

are going up, the edges are not in the matching are going down.

Okay. And now I have one more variable which

has been assigned, and I have only one free variable here which is the little

x1, which is left alone. Okay.

So now what I do, is I look at this guy, I try to find another an alternating path

for x1. And you're going to see it's a beautiful

path juju going up and down, until it reaches the value 5.

Okay? Once again, you know the edges, the edges

which were going down are going to go up, the edges which were going up are going

to go down and this is my graph at the end.

Okay? And now x1 has been assigned, all the

values at the top now are assigned and almost all the values are assigned.

But we don't really care about the values, because we really care about the

variables and, and be sure they are assigned different values.

Okay? And at this point of course, I have a

feasible solution and this is the matching, essentially that I have.

Okay? So this is essentially what I do.

Okay? So for finding the alternating path.

Okay? I'm basically going from top to the

bottom and until I get to a free vertex at the bottom, which is a free values.

And essentially what I do is I do that interactively.

I take a variable, [SOUND] I look for the spot.

If I can improve, great, I have a better matching.

I take another one, [SOUND] I do the same thing.

Okay? How do I find this path?

I can use traditional depth-first search or best-first search to do that, and I

get a very low polynomial algorithm to do that.

Okay? So this is beautiful because now,

essentially I know how to find a maximum matching, it's a very simple thing.

Okay? You just have to re-orient the graph, you

have just to construct this bipartite graph, or enter it in the right way, and

search for the, for the, for the alternating path inside this directed

graph. So, to summarize, what we do is we build

this bipartite graph, we have a vertex set for the variable on top.

Okay? We have a set of, we have another set of

variable, set of vertices for the values of the bottom, and we have an edge

between a variable and a value if that value's in the domain of the variable.

Okay? Then, essentially, the feasibility.

Okay? So the constraints is going to be

feasible. If we have a maximum matching, which

whose values is the same as the number of variables.

And to do that, the only thing that we have to do is find this alternating path,

which are going to improve the matching one step at a time, until we get the

maximum matching. And when we have it, we just compare it

to the number of variables. Okay?

So we have done part one, which is essentially finding feasibility.

Okay? Now, we have to prune now.

What does it mean to prune is that, if a variable x can take a value v, we have to

see if that particular variable, you know, belongs to a solution.

That means that we can find values for the domain of the other variables.

Okay? Such that, you know, all the variables

are given different values. Okay?

Now, if we translate that in the context of the matching, what it means is that

this edge belong to some matching. Okay?

So there is a very easy algorithm and very naive algorithm to do that.

You basically force this edge in the matching.

Okay? So if we have, we're looking at x,

variable x and value v, we're basically removing all the other parts that have

value for variable x. So if w is a value, remove the edge,

there is only one edge which is left for x.

So if we're finding a maximum matching you know, x will be forced to take this

value v. And then we look if we can you know, find

a maximum match whose values is essentially the number of variables.

If we can do that, we are fine. Now, the problem with this of course, is

that we have to take all these edges and then find a maximum matching.

Take another edge, find another matching, a matching, so it's really tiring.

It takes a lot of time. Okay?

So we can do better. And there is this basic property, crazy

property by Berge, in 1970, which was found by [UNKNOWN].

And so what is interesting here is that this property seems to come out of no

where. Okay?

But I'm going to read it to you and, and tell you why it's relevant.

Okay? Basically this property is basically

saying that an edge belong to some, but not all, okay, some, not all, okay,

matching. If given a maximum matching, it belongs

to other two things. Okay?

An even alternating cycle. Okay?

So that's a cycle which has length or or length which is even.

Okay? Or an even alternating path which starts

at a free vertex. Okay?

So it's crazy, right? This property is crazy.

First, you know, we are looking at some but not all the matching, and then we

have these two, you know, crazy properties.

But why is it so relevant to us? Well, you know, the edges in the

matching, we really don't care about that, right?

Because we know they are in the matching, so we know we can't remove them from the

domain of the variables. So what we are really looking at here,

are edges which are not in the matching. So we know that in the best case, they

belong to some matching but they won't be long to all.

And this is what really this property is about.

So this is like magic, right? So this is just the property that we

need. So the only thing that we have to do, is

for all these edges which we are not in matching, we have to look at two things.

Do they belong to even alternating cycle, or do they belong to an even alternating

path which starts with a free vertex? Okay?

So essentially this property is telling us really what we want to do, and it

basically boils down to looking at these two things.

Okay? Which is much easier essentially, than

looking at all of the things we had to do before.

So what are the free vertices in this particular case?

The free vertices are of, where are they? Are they the variables or the values?

Well, we know that the constraint is feasible, so all the variables are

matched. So the only you know, free vertices are

really the values. And that's where we're going to start,

essentially, when we search for this even alternating path.

Okay? So essentially what we're going to do is

the same thing as is for feasibility, except that it's the opposite.

Okay? So we create a directed graph, but this

time around the edges are oriented in the different way.

Why, because before we were looking to assign the variables.

Here we are going to look at alternating pump that are starting at the three

vertices, and these guys are the values now.

Okay? So we start at the bottom and then we can

go up, if the edges don't belong to the matching.

And, and edges belong to the matching go from top to the bottom.

Okay? So this is, once again, an illustration.

It's essentially the same thing as we have seen before, except the edges are

the other re-direction. So you see this guy here, this seven,

this is a free variable. Okay?

This is a free value. Okay?

And then it can go up you know, to some of the variables and then the edges in

the matching, the blue edges are going from top to the bottom down.