Follow US:

Practice English Speaking&Listening with: Lecture - 23 Bipartite Maximum Matching

Normal
(0)
Difficulty: 0

Bipartite Graph Matching in the course on Design and Analysis of Algorithms. Let me

begin with a motivating example.

So, in this example we have some j jobs and some C candidates. The idea is that the each

candidate we have given we have been given the list of jobs that they candidate can do.

And we also have been given a constraint. The constraint says that, each candidate must

be given at most one job. And also each job must be assigned to at most one candidate.

The goal is our obvious goal. Assign candidates to jobs such that, maximum

number of jobs are filled. The bipartite maximum matching problem is exactly this, in more

mathematical terms. So, I am going to first define this problem. And then, I will relate

it to this job and candidate problem.

In this problem, our input is a bipartite graph. So, let us call it G. G is composed

of two vertex sets U and V. And the cardinality of U says n 1. And the cardinality of V is

n 2 and E is the set of edges. Let me remind you, what a bipartite graph is. A bipartite

graph is simply the graph, in which the vertex set is in two parts U and V. And the edges

only go between U and V.

Here for example, is a bipartite graph. So, this forms this set of vertices forms U. This

set of vertices forms V. And as you can see the edges, only go from some vertex in V to

some vertex in U to some vertex in V. Specifically, there are no edges which connect our text

in U to another vertex in U or our text is V to another vertex in V.

So, let me now define what a matching is. A matching is a subset of the edges such that,

at most one edge is incident on any vertex either in U or in V.

So, in this graph for example, the set of blue edges would be a matching. If I add one

more blue edge as here, this would not be a matching, because we would have a conflict

at this vertex 7. So, here we would have been having two edges of the matching, of the so

called matching being incident and that is not allowed.

So, now let me tell you, what the goal in this problem is or what we require to output.

So, we are required to output a matching of maximum possible size. A size of the matching

is defined as the number of edges in it.

In this graph for example, we have this blue matching which consists of three edges. So,

its size is 3. This however, is not the maximum sized matching.

This red matching for example is the maximum size matching. And in fact, it contains 1

2 and 3 and 4 edges. Maximum matchings are not unique, in this graph itself. For example,

this is another maximum matching.

Let me now relate, this matching problem to that of our candidates and jobs problem. So,

this first set of vertices which we call U, can be thought of as the candidates. So, think

of 1 2 3 4 5 as being the candidates. And the jobs are represented by this second set,

which we call V. We draw an edge from a vertex over here to a vertex over here, if the corresponding

candidate over here can do this job. So, these two edges for example, represent the fact

that candidate 1 can do job 6 as well as job 7. So, in fact the list ally that I have mentioned

will contain 6 and 7 in the list of candidate 1.

A matching now is simply, an assignment of jobs to candidates. So, for example here is

a matching which says. Let us assign to candidate 1 job 6 to candidate 3 job 7 to candidate

5 job 9. Of course, we would like to maximize the number of jobs assigned. So in fact, instead

of this we should really be taking one of the red matchings that, we saw earlier.

Here is the outline of my lecture. So, I am going to begin with an algorithm design idea.

And we will see few more ideas and refine them. Then, we will come to the notion of

augmenting paths. This turns out to be a very important concept, in this whole matching

area. That will understanding augmenting paths, will lead us to reasonably clean simple high

level algorithm. It is correctness depends upon something called Berges theorem. So,

we will state and prove that theorem next. And then, finally we talk about how to efficiently

implement this algorithm. And we will estimate its time.

So, let us start with a really simple winded idea. How would you find the largest size

matching? The moment you talk about larger size perhaps, the most natural thing to consider

is the greedy idea. So, here is the strategy. So, we look at all the edges and maintain

a set called M. And we keep on adding edges into M, till no more edges can be added. Of

course, as we add edges into M you have to make sure that there are no conflicts or there

are no two edges which ever are incident on the same vertex, which are placed in our set

M.

In this case for example, if we tried this idea what would happen? Well, we would start

with this edge and add it no problem. Then maybe we will try to add an edge going out

of 2, but this edge cannot be added because it would produce a conflict at 6. So, we take

the next edge. So, we add that one. Then, we try that this edge over here this edge

also cannot be added because, it will produce a conflict over here. Then, we try adding

this edge. That also cannot be added, because it would

produce conflict over here. And then, we try to add an edge out of 5. And say for example,

we end up adding this edge. After this, you can see that no more additions are possible.

Have you reached the best possible matching? No, because we know that there exists a matching.

In fact, any one of those red matchings which we saw earlier which have four edges in them

rather than just the three edges, which we have found over here.

So, we clearly need something better than the greedy idea. So, here is what I call the

kho kho idea. So, if you have played this game of kho kho, you might remember that in

that game there is a chaser who keeps running. But, who occasionally goes and knocks on the

back of a person, who is sitting down. And then, that the person who was originally sitting

down starts running and starts chasing the members of the opposing team.

Until he or she again goes behind and knocks in the back of another person, who is sitting

and who takes over. So, this is the idea that we are going to explore. So, I need a definition

for that. The definition is that of a free vertex. So, given a matching M I will say

that the vertex is free, if it is not an end point of any edge in that matching. So, we

will take an example on this shortly. But, let me state that idea first. So, the idea

is something like this. So, suppose we have a free edge then, that

indicates that maybe we can augment or we can increase the size of our matching. May

be by throwing an edge by considering an edge out of that vertex, and may be trying to include

that edge include that matching that we have found so far. This may succeed if it succeeds

great then, we have a bigger matching. If it does not succeed, well how will it not

succeed? It will not succeed because, may be it conflicts with another edge which is

already present. So, this is where the kho kho idea comes.

So, this new edge that is present. The old edge that is present will get knocked up.

And the new edge will sort of set in our matching. But, now once we knock out an old edge, what

will happen? Well, the other end point of that will become free. And now we will try

to match that. And we will try to do on this, until we find that there is no conflict. And

if we succeed then, maybe we have increased the size of our matching a little bit. So,

let us try it out.

So, the first thing to check is which are the free vertices? So, in this case vertex

2 vertex 4 and vertex 8 are free. Because, they do not contain incident on the any edge

in the matching, edges in the matching are shown in blue over here. So, let us start

with vertex 4. And let us try to see, what happens if we try to match it somewhere. Well,

4 can only be matched to 7. So, I have indicated that this is our candidate for inclusion into

our old matching. If we try to include this, what will happen?

Well, that will have there will be two vertices two edges incident at 7. So, essentially we

will have a conflict. Conflict just means that, there are two edges incident in a matching.

We just want one edge to be incident or at most one edge to be incident. Well, if there

is a conflict what do we do? Well, we are going to remove this edge.

So, let us do that. So, I am going to use the color code green, the color green to show

edges, which were in the matching before we started this entire procedure, but which we

have just removed. Remember that yellow edges are the ones which we just added. So, they

were not in the matching before, we started this procedure. But, they have just come into

the matching. Green edges are the edges, which were in the matching earlier. But, now they

have gone out of the matching. If this edge from 3 to 7 goes out, what happens?

Well, vertex 3 becomes free. Vertex 3 does not have an edge in the matching attached

to it in longer. Remember this edge is just gone out of the matching. So, now we try to

match 3. Well, we could try and match it back again to 7, but that seems foolish. We just

removed this edge. So, we should not try to put it back again. So, let us try to do something

else. So, the only else the only other thing that we can do is add an edge 3 to 9.

So, let us try doing that. So, now this yellow edge this yellow color says that, this edge

has entered our matching and it was not there originally. Well, what does this do? It produces

a conflict of time. How do we eliminate that conflict? Well, we remove this edge. So, this

edge goes out of the matching. And therefore, we color it green. Now, it happens. Now, vertex

5 is free. So, we try to match it.

When we do match it, we match it to 8 and interestingly there is no conflict. So, this

is the basic step that I mentioned. This is the kho kho sort that, I mentioned. Let us

see, what it is accomplished.

So, we ended adding three edges. Which are the three edges we added? Well, these three

this yellow edge, this yellow edge and this yellow edge. So, these three edges we added.

So, now you know why I color those edges very, very carefully. So, that I can keep track

of what exactly happen? What happened to the edges earlier in the matching? Well, some

of them stayed. This edge was there in the matching earlier it state.

But, this edge which was there in the matching earlier went away. This edge which was there

earlier in the matching, that also went away. But, two edges went away and three edges came

in. So, now we have a better matching which consists of this edge, this edge, this edge

and this edge. So, earlier we had three edges in the matching. Now, we have four edges in

the matching. Now, the colors are going to tell us something more interesting, about

what exactly happened. And in fact, it makes sense to ask exactly

how we traverse this graph in this entire process. So, as we executed this process we

really traversed a path in the graph. So, we started at vertex 7. Then, we added edge

4 7. Then, we removed edge 7 3. Then, we added edge 3 9. Then, we added then, we removed

edge 9 5 and added edge 5 8. So, that is exactly what happened? This, this, this, this, and

this. In fact, there is more interesting pattern out here. So, let me show what that pattern

is.

Let me take this vertex 3 and let me drag it over here. So, now you should be able to

see, what that pattern is even more clearly. So, if I look at the first edge on this graph,

it is yellow. The second edge on this path is green, the next edge on this path is yellow

again its green again it is yellow. So, in fact the colors of the edges alternate along

this path. And that is of course, to be expected why, because we alternately added and removed

edges. In fact, there is one more interesting thing.

So, whenever we were adding edges we were going forward in the graph and we were following

edges which were originally not in the matching. When we removed edges, we were following edges

which were originally in the matching. But, we were going backwards in the graph. And

similarly, again we go forward backward and finally forward again.

So, you see that what we did, the path we traced at this entire procedure has lots of

interest in properties. And in fact, this path that we traced is so important that it

is given a name, it is called an augmenting path.

So, given a matching there is a notion of an augmenting path. An augmenting path is

a sequence of vertices v 1 v 2 v k. Such that the first vertex is in the set u in the graph,

the left the set of vertices on the left corresponding to the vertex 4 that we started off with and

it is a free vertex. That is exactly, how we started out the construction. The last

vertex is also free because, that is what enabled us to discover an extra edge.

And then, the intermediate vertices well the vertex from v 1 to v 2 was originally in the

graph, but not in the matching. And that is exactly, what this set E minus M supposed

to denote. E is the set of edges from that, I remove the set of edges which were in the

matching earlier. So, this edge v 1 v 2 is now was supposed to be in this set E minus

M. The next edge on the path however, v 2 v 3 is a backward edge and it belongs to the

matching. And this edge is the forward edge. So, we

go forward then, we go backward then we go forward again potentially. Again we follow

an edge, which is not in the matching and we go forward. And maybe we go backward again.

And we do this several times, until we end with this set v that is what a augmenting

path is. The operation of taking an augmenting path p and a matching m and generating a new

bigger matching which we just did, we will abbreviate as M symmetric difference P. Why

is this called symmetric difference? Well, here is the definition of this circle

plus operator. We will define Q circle plus R or Q symmetric difference R, as the set

of elements in Q or in R, but not in both. So, in that sense it is the symmetric difference.

So, it is the sense in which Q and R are different from each other, not their similarity, but

there is difference. So, in fact you can see that the new matching is the symmetric matching

is the symmetric difference of the old matching and the path. So, let us take a look at that

quickly.

So, the old matching was this matching 1 6 3 7 and 5 9. So, the old matching is the blue

edges and the green edges. The path is this. So, the path is the yellow edges and the green

edges. So, as you can see the green edges form the intersection between the path and

the old matching. And therefore, they have been removed. And what has included in the

new matching is just the difference, the symmetric difference between the path and the old matching.

So, these are edges which were in the path, but not in the matching. This is also an edge

this is an edge which is in the matching, but not in the path. And so, the new matching

will just contain this and these.

So, augmenting paths play a big role seem to play a big role when we want to increase

the size of our matchings. In fact, Edmonds who was a eminent computer scientist from,

Ii guess from the previous century who is one of the who could even be called as one

of the founders in some sense of analysis of algorithms. So, I am going to describe

an algorithm which is credited to Edmonds. So, the algorithm is essentially based on

this idea of augmenting paths. So, we start off with M which is an empty matching which

is an empty set. So, there is nothing in it. And then, we keep

on finding the augmenting path. So, we check if there is an augmenting path P for this

M, defined in this sense. If there is then, we perform this operation and set M to the

result. We keep on doing this, until we discover that we cannot augment our current matching.

The moment that happens, we stop and we output M. So, this is the algorithm. Does it seem

reasonable? Well, yes it seems reasonable. We seem to be adding edges if possible, but

there is a old problem which we had with our greedy idea as well. What if we discover that

there is no augmenting path. Can we stop then really or it is possible that there is some

bigger matching which we will find using this idea. So, this possibility can be ruled out

and this is done by a theorem attributed to Berge.

So here is what Berges theorem says. Berges theorem says that a matching M in a bipartite

graph is maximum, if and only if there does not exist a augmenting path for M. We will

prove this in a minute, but I just want to persuade you that, this is exactly the theorem

that we wanted. So, this theorem says that if ever we come to a point at which we cannot

find an augmenting path. Then, we must have in our hands a maximum sized matching.

So, this theorem justifies or proves the correctness of Edmonds algorithm. So, let us now prove

this theorem. The proof is in two parts. Since, this is a if and only if theorem. The first

part is the only if. So, what are we required to prove over here? If a matching in a bipartite

graph is maximum then, there cannot exist an augmenting path. This should be quite obvious.

If there existed an augmenting path, what would happen?

Well, we could add we could augment that path with our matching. We could compute M circle

plus P and we would get a bigger matching. Is if that possible? No, because we said that

M is already maximum. And therefore, the only if case is obvious. The interesting case is

the, if case. We are going to prove this case by contradiction. So, how does this work?

Well. So, let us assume the contrary. So, let us suppose that M has no augmenting

path. So, M has no augmenting path that of course, by itself does not make up the contradiction.

So, we are going to assume that M has no augmenting path. And there exists a matching M such that,

N is larger than M. So, this is the case that we really wanted to watch out with. We cannot

find an augmenting path, neither have we got the best matching. So, this is the if case.

And this is the case that we really want to rule out.

So, we are worried about such M. We have in our hands matching M. And we know that there

is, we are assuming that there is a bigger matching N somewhere out there. Well, at this

point it is natural to ask, what is the difference between M and N? So, that is exactly what

we do. So, we will ask will say, let R be the symmetric difference of M and N. And then,

let us investigate what this, what the properties of the symmetric difference are.

I claim that, so we are going to look at this symmetric difference R. My first claim is

that this R must be composed of paths and cycles. Why is that? Well, before saying why

that is, let me just say that the claim is equivalent to stating that the degree of every

vertex in R is at most 2. Remember M and N are sets of edges. R is also a set of edges.

And it is over the same vertex set u and v. So, I can talk about the degree.

So, I claim that if R is made up of paths and cycles, it is the same thing that saying

the degree of every vertex in R is at most 2 obviously. The degree of any vertex in a

path is 2, the degree of any vertex in a cycle is also 2. So, if I can prove this I would

have proved this. Well, why is this true? Well, just examine how we constructed R? We

constructed R by taking some edges of M and some edges of N. But, note that the degree

of every vertex in M and N is at most 1. The edges of M and N are such that, on every

vertex at most 1 edge from either M or N is an incident. So, even if I take the union

forget the symmetric difference, even if I take the union the degree of every vertex

in M and N will be at most. Since the degree of M and N in every vertex is at most 1, the

degree of the union will be at most 2. So, from this it follow that this is true. Therefore,

this is same as this. Here is an interesting fact about R.

So, it consists of paths and cycles, but the edges in R alternate between M and N. Why

is that? Well, could there be two consecutive edges in R coming from M. No, because M has

been defined to consist of edges which are incident on vertices. But, at most one edge

is incident on any vertex. So, in M itself two edges are never incident on the same vertex

and therefore, when those edges going to R this property will stay around and similarly

for N. And therefore, we know that the paths and cycles inside R consist of alternate edges

of M and N. Some more properties, what is R? Well R is

the symmetric difference. So, that is as good as saying that, we take the union and then

we remove the intersection. So, the size of R is size of N plus the size of M minus the

size of the intersection. But note that, N has bigger size than M. So, we subtract something,

but in the end we subtract something we just common to both M and N. So, in the end R must

have more edges in it from M rather than from N. So, we just how to examine the implications

of this.

Let us look at cycles first. Each cycle consists of an equal number of edges from both M and

N. So, if we just look at the cycles this fact cannot be explained. So, what first happen?

There has to exist a path, which must contain more edges from N. If it contains more edges

from N, what do we know about such a path? Well, let us take a picture.

Let us draw a picture over here. So, here is this path. It contains more edges from

N. So, let us say N edges are in black. So, if it contains more edges from N clearly,

the first edge has to be from N then, from M then, from N then from M. And finally, the

last edge must be from N. So, now what do we know about these vertices? So, will these

vertices have an additional edge either from M or N going out.

Well, if there was a red edge going out then, this could be a path which have been continued.

We could have considered that itself, but this is the maximal path that we are considering.

So, there cannot be a red edge going out of here. There cannot be a black edge going out

over here, similarly over here. So, that means that the first and the last end points of

P must also be free in M and what is this. This is simply the definition of an augmenting

path. So, this path p is an augmenting path for this matching M. So, we have proved that

an augmenting path exists and in other words, this you can improve your path. And we started

off by saying that, M has no augmenting path. So, we have got to a contradiction. So, this

proves Berges theorem. So, we have proved Berges theorem.

So, we know that augmenting paths are useful and not only useful, but they are sufficient.

So, the only question that, remains is can we find augmenting paths quickly? So, what

are the properties that we know about augmenting paths? Well, an augmenting path starts and

ends at a free vertex. It starts at a vertex, say U and ends in a vertex V. So, without

loss of generality or vice versa, so without loss of generality we can assume that the

starting point is U. So, we are given a graph and we want to start

an augmenting path. We want to check whether there exists a augmenting path, starting at

some vertex in U. If we knew where the path started, we could just try growing the path

out of that vertex. So, we could try something like depth first search or something like

that. And try going out from that vertex into the rest of the graph. But, we do not know

where it starts. So, here is an interesting idea.

So, since we do not know where it starts, we are going to start growing from all the

free vertices in U. Now, we know something more about augmenting paths, which is that

the paths have to grow forward using only edges in E minus M. E difference the edges

which are in E, but not in the matching E minus M. And the path must grow backwards

using edges, which are in the matching. You may do this several times.

It may go forward and go backward and then, forward again several times, but every time

it goes forward. It must use an edge which is not in the matching. And every time it

goes backwards, it must use an edge which is in the matching. Finally, if we reach a

free node or a free vertex in the set V, which is the set on the right side through any paths,

whatever we are done. So, that is how we are going to grow these

parts. And if we reach a free vertex, great we are done. We would have discovered a path.

Now, it turns out that you can package this set of ideas very nicely as a breadth first

search on a new graph. Well, on a slightly a graph which has been derived from this M

and G. This graph is going to be very similar to G, but it is going to be crucially and

slightly different. So, let us take a look at this. But let us first take an example

first of, how we can do this?

So, here is our old graph and here is our old matching. So, let me try to see how this

idea will work out, on this graph. So, the first point was to look for a free vertex,

actually a free vertex on the U side. We say here two vertices are free, vertex.2 and vertex

4. These are the free vertices. So, these are the vertices from which we can start the

paths. So, we could say for example, that let us grow paths from 2 and 4 going in the

forward direction and backward direction as we just described.

Instead of that, just to make our description nice and compact. We are going to throw in

a new vertex, we will call S. We will also throw in two edges, going out of S to both

the free vertices or to all the free vertices, whatever free vertices there are. And in fact,

we are going to direct these edges. So, earlier graph was an undirected graph. this new graph

is going to be a directed graph. We can do breadth first search or any kind

of search on an undirected graph, just as well as on a directed graph. So, here we are

going to do it in a directed graph. So, now instead of saying that we go upon paths 2

and 4, notice that we can just say grow paths out of S, just a single vertex S. So, we want

to grow out of S. And once we do and if we do that, we will naturally hit 2 and 4 which

is where you want to go anyway. What do we next? Well, we want to grow the

path itself. And for growing the path, we need to use edges which do not belong to the

matching. And furthermore, we know that these edges will be used only in the forward direction.

So, a natural way to enforce this constraint is to say, this is the constraint that we

want to enforce. So, the natural way of doing that is to direct these edges in the forward

direction. So, every time we grow the paths. We know that the edges which are not in the

matching will be used, only in the forward direction. So, we put a direction on them.

So, that forces the search to use them, only in the forward direction.

Now, what happens when the path the augmented path goes backwards? Well, it uses edges,

which are in the matching. If it uses edges which are in the matching, it only uses them

going backwards. So, we put backward arrows on this. So, the idea now is, we start over

here we keep we go forward we are allowed to go forward. Then, we are allowed to go

forward using edges, is not in the matching. We can come back, we can go forward we can

come back, every time we come back we need to use edges in the matching. Every time we

go forward. We are supposed to use edges, which are not in the matching. And finally,

we would like to end up with a free vertex in this set V. Again there could be many free

vertices over here. And instead of saying, let us end up saying free vertex in this set

V. Here is what we will do?

Instead of saying that, the path must end at any free vertex we will put a vertex t

out here. And all the free vertices we will connect it to t. In this case, there is one

free vertex. So, this is what we will connect to t. So, now what is the problem that we

want to solve? While we want to ask the question, does there exist a path from s to t in this

directed graph. Notice that by putting directions, we have essentially enforced all the constraints

that we wanted on that augmenting path.

So, let us formalize this. Let us state this algebraically. So, we will define this directed

graph and we will call it the auxiliary graph, for G and M. So, what does this graph look

like? First of all, we will get symbol G prime. It is going to consist of vertex set V prime,

which I will define in a minute and edge set. So, these edges are actually directed. So,

this edge set is E prime. So, what is the vertex set?

V prime is the union of set U in the original graph, the set V in the original graph and

these two vertices, which we added the s vertex and the t vertex. Let us define the edge set

E prime consists of these edges, which goes out of s. So, just to remind you. So, these

are the edges which are E s edges. E f is the edges, which are the forward edges. So,

let us go over them step by step. E f are the set of edges in the forward direction

that is, what this f is supposed to end up. So, they consist of the arcs of the form u

v, where u belongs to the left hand set of vertices, v belongs to little v belongs to

the right hand side vertices of capital V and u v is not in the matching, but it is

in the edge set. E sub b are the backward edges, the edges which we directed backwards.

And these are simply all the edges in the matching. So, these are all the edges which

were not in the matching which we directed forward.

These are all the edges which in the matching, which we directed backwards. So, notice that

this is u to v whereas, this is v to u. And finally, we are going to put edges out of

every vertex, every free vertex in V to the vertex t. So, this defines our auxiliary graph.

So, now comes our main claim. Our main claim says that, G has an augmenting path for this

matching M if and only if, G prime has a directed path from s to t. We will prove this, we just

point out why this claim is important. Notice that, we did not have any specific

way of finding augmenting paths. However, given a graph G prime does it have a directed

path from s to t. That we know how to find it completely? That is just simple, breadth

first search, depth first search or whatever you like. So, this claim would enable us to

find augmented paths very quickly. And that is why, it is a very significant claim. So,

let us prove it. The proof really goes along. Pretty much along the lines of the construction,

as I explained it in a minute ago, but I will try to explain it formally right now, without

reference to a specific graph. So, let us look at the only if part first. So, the only

if part says that suppose G has an augmenting path then, G prime must have a directed path

from s to t. So, the only part says that let A be an augmenting path for G M then, we will

show we must show that s v 1 v k the same path, but in the new in the graph G prime,

must be a directed s t path. So, I hope there is no confusion. Because,

we are using the same set of vertices, but we have carefully defined everything in this

definition. And also in the previous graph in the previous picture, we actually use the

same set of vertices. And we just transformed our original G to G prime. By context you

should know, when I refer to over vertex whether I am referring to it inside G prime or inside

G. So, we had given this augmenting path v 1 to v k. And we want to show that, this must

be a directed path in G prime.

What do we know about augmenting paths? It starts at a free vertex in U, goes forward

and backward several times and terminates at a free vertex in V. So, v 1 is a free vertex

and the path goes forward from v 1. When it goes forward, we must have an analogous edge

in G prime. So, all that you need to do is that, analogous edge is present in G prime.

Note that in the forward direction, the path users edges in E minus M. This is inside G.

An augmenting path in the forward direction, uses edges which are not in the matching.

The path is moving forward, but it is using edges which are not in the matching. Now,

these edges are in fact present in G prime. These are exactly the edges. They are present

in G prime and in fact, they are directed in the forward direction. So, if we look at

the forward going edges in this, they are all present in G prime and they are all oriented

properly. They are oriented as per the movement of the

direction, movement of the path direction. What does the path do? Well, the path can

go backward. When it goes backward, it uses the edges of M. But, these edges are also

present in G prime and they are directed backwards. So, again this is exactly what we wanted.

Well, there is no coincidence over here, because we arranged it to be this. So, in some sense

if you followed that example then, this should not be surprise to you at all.

So, again going back to this, v u is an edge going from v to u and that is how we have

oriented it. If for all such edges which belong to the matching. So, what have we proved then?

We have proved that, this portion which is an augmenting path which is also present in

G prime and it has proper orientation. So, all that we need to argue is the s to v 1

connection and v k to t connection. So, what do we know about s to v 1.

So, s has a directed edge to every free vertex in U. And of course, v 1 must be a free vertex.

So, this since it is an augmenting path. So, s to v 1 must be an edge in G prime. Similarly,

v k to t also is an edge, because every free vertex has an edge s to t. So, that is also

present in G prime and thus we have a path in G prime also. So, this entire thing is

a path in G prime exactly as we wanted.

The if part, the if part says that if G prime has a directed path from s to t

then, G must have an augmenting path. So in fact, you will see that exactly the reverse

of this reasoning will accomplish the, if part also. So, let us summarize what we have

done. So, we have defined this auxiliary graph. And using the auxiliary graph, all we have

to do is just find the path in it. And we get an augmenting path. So, we find a path

from s to t and we get an augmenting path.

So, now that brings us back to our algorithm. So, that brings us back to the algorithm.

So, we just have to build up on this step of finding an augmenting path, but we know

how to do that. So, here is our augmenting path procedure. So, we construct G prime just

as we defined a minute ago then, we find p the path from s to t. We can use breadth first

search for it or we can use depth first search, it does not matter.

But, somehow we do it. And then, if p is not null then, we delete that as t and return

the augmenting path. This return path will be used over here to augment the matching.

So, let us now analyze this. So, let us say n denotes the cardinality of U plus the cardinality

of V or the total number of vertices. Let m denote the cardinality of the edge set of

the original graph. And let us assume that, the graphs are represented in the adjacency

list representation. In fact, we will keep m also in some adjacency

list representation. Just for the purpose of simplicity of thinking about this whole

thing. So, what do we know now? Well, we have to analyze what the time for constructing

G prime? And G prime is and then, doing the breadth first search and so on. So, here we

construct this graph G prime. So, how did we do that? We took G and we took the matching

and we took its union, we oriented the edges. So, in any case that can be done in time proportional

to the sizes of two graphs, which is O of m plus n. The next step over here is to find

the path from s to t using BFS. BFS Breadth First Search takes time again O of m plus

n. So, this step also takes time O of m plus 1. So, both of these steps take time m plus

n. Time for this entire procedure, I claim this is going to be O of m plus n, this entire

procedure augmenting path. That is, because this part deleting s and

t can be done in constant time. And therefore, this entire thing is just the sum of this

plus this, which is O of m plus n. So, this takes O of m plus n time. So, the only question

that remains is, how many times do we augment? Well and how do we do this augmentation itself?

In fact, in m plus n time you can compute M augmented with P also. Because, that is

just going over the graph completely once even that, will take time O of m plus n. How

many augmentations do we do?

Well, what do you know about matching size? The matching size is at most n by 2, since

the number of vertices is n. And so, the number of augmentations is going to be at most n

by 2. So, now we know what the total time is, the total time is n by 2 multiplied by

this or in other words, it is O f n times m plus n m is typically larger than n and

so, we can write it as O of m n. So, that completes the analysis of the algorithm, the

description and the analysis of this algorithm.

So, let me make a few concluding remarks. We can actually think of this algorithm, as

an iterative refinement. What does that mean? Well, we have a matching currently and then,

can we improve it by making the small change. So, an augmenting path essentially allowed

us to determine if a small change can be made. This is not the fastest algorithm. In fact,

an m root n algorithm is known not just m n. So, m root n algorithm is known.

And in fact, we can define this problem for non bipartite graphs. So, that also turns

out to be useful very often. And as it turns out that, similar bounds can be found for

the non bipartite case. So, maximum matching can also be found in non bipartite graphs.

In the same time as above, but the algorithm is much, much more complicated. And I will

stop here.

The Description of Lecture - 23 Bipartite Maximum Matching