# R7. Network Flow and Matching

**Channel:** MIT OpenCourseWare
**Source:** https://www.youtube.com/watch?v=0CdxkgAjsDA
**Transcript page:** https://www.withtranscript.ai/video/0CdxkgAjsDA

## Chapters

- 0:00 — Chapter 1 (0:00)
- 1:23 — Chapter 2 (1:23)
- 2:52 — Chapter 3 (2:52)
- 4:38 — Chapter 4 (4:38)
- 5:49 — Chapter 5 (5:49)
- 7:28 — Chapter 6 (7:28)
- 9:20 — Chapter 7 (9:20)
- 9:47 — Chapter 8 (9:47)
- 10:26 — Chapter 9 (10:26)
- 11:35 — Chapter 10 (11:35)
- 12:21 — Chapter 11 (12:21)
- 13:20 — Chapter 12 (13:20)
- 14:20 — Chapter 13 (14:20)
- 15:34 — Chapter 14 (15:34)
- 16:21 — Chapter 15 (16:21)
- 19:07 — Chapter 16 (19:07)
- 21:22 — Chapter 17 (21:22)
- 23:56 — Chapter 18 (23:56)
- 26:05 — Chapter 19 (26:05)
- 26:33 — Chapter 20 (26:33)
- 27:43 — Chapter 21 (27:43)
- 28:26 — Chapter 22 (28:26)
- 29:26 — Chapter 23 (29:26)
- 31:52 — Chapter 24 (31:52)
- 32:56 — Chapter 25 (32:56)
- 33:44 — Chapter 26 (33:44)
- 35:49 — Chapter 27 (35:49)
- 37:35 — Chapter 28 (37:35)
- 39:01 — Chapter 29 (39:01)
- 40:04 — Chapter 30 (40:04)
- 41:17 — Chapter 31 (41:17)
- 42:00 — Chapter 32 (42:00)
- 44:44 — Chapter 33 (44:44)
- 46:54 — Chapter 34 (46:54)
- 47:24 — Chapter 35 (47:24)
- 49:47 — Chapter 36 (49:47)

## Transcript

**[0:00]:** the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT open courseware at

**[0:21]:** ocw.mit.edu all right morning everyone I hope you all had a great spring break and during which I hope you can have more of six over six today we're going to look at Network flow and two things in network

**[0:43]:** flow the first one is Atmos carp algorithm and uh after that we're going to look at some two applications and in particular they are called bipartite

**[1:02]:** matching and

**[1:08]:** cover okay so uh we'll start with uh simpler algorithm which is for

**[1:23]:** Focus uh can someone remind us what F fusen does

**[1:41]:** go ahead every time you have get it it gets rid of it yep uh what's your name by Mish uh okay so well Misha gave a very brief description but let's be a little more bit more detailed so we have a graph gra Network flow uh G and the first thing it go going to do is that given the flow it will transform G from a resue graph everyone remembers that then uh FF algorithm will find the

**[2:19]:** path of going from source to sync in this resue graph and then

**[2:36]:** augment this path uh augment just means augmenting just means uh increasing the flow on that path by how

**[2:52]:** much yeah the minimum Edge on the path uh let me just Define that to be the capacity of the path which which is the capacity of the weakest link okay then uh what's the last step we're missing

**[3:15]:** here so after argumenting our flow changed from F to F Prime and then we're going to loop back we have a f Prime then GF F Prime find find the path in GF Prime and uh continue from there so this algorithm in some sense is not even a very detailed algorithm because it doesn't say how to find a path in the second step and that's indeed a problem because we have seen uh pathologically Bad

**[3:58]:** Case where um each capacity is a billion and the correct way to do it is simply like augmenting this path and then that path oh sorry there's a edge one right then we'll be done but uh the pathologically bad case is we keep going through this middle Edge okay so admon C is a Improvement to this algor let me just write it

**[4:38]:** here it's uh it's first step third and fourth steps are actually exactly the same no change from for focuson the only thing it does is that it finds a special path um did really cover this in the lecture that what path uh ATM car finds I see some people noding okay go ahead run search from the source to the sink GF take the shortest okay does everyone agree with that so admon carp finds the shortest

**[5:22]:** path

**[5:25]:** from I guess can you see that part nope oh sorry about

**[5:49]:** that find the shortest path uh here shortest just means least number of hops here uh in this pathologically bad example at cup will do much better because it would find this path instead of this weird path right because that path is distance is two and the one going across the middle is three okay now we are going to prove that this algorithm runs in order

**[6:23]:** v² so okay uh so one step back do we have to prove that it's correct that it indeed finds the uh maximum

**[6:41]:** flow MH yeah I don't I claim I don't have to do that because it's the same thing as uh for focusing you can find any path now we want to show we want to bound this runtime uh so any idea high level idea how we are going to do that in which several

**[7:28]:** steps

**[7:35]:** okay so uh okay a simpler question what's the what's the complexity of this second step find the shortest path from source to sync go ahead uh o plus e o plus e and uh in this case actually V is always less than e right so I can simply say o now how long does it take to augment that path if we have found it o that's

**[8:16]:** correct but I claim I we can say we can also say it's all V right because the shortest path uh at least have at most has v Hops and then from F to F Prime okay so I think in some sense these two are the same steps and also of v and then updating the rescue graph is also of V so one of this iteration each iteration takes how long or V right this is the uh most expensive step in one iteration okay so what else do we have to do to prove this bound number we need to show that the number of iterations is O of V * e if we can show

**[9:20]:** that then we are pretty much done

**[9:28]:** okay

**[9:35]:** okay now to prove that bound uh we first need a LMA which uh we call

**[9:47]:** monotonic so let me Define delta

**[9:57]:** FV this is the length of the shortest path from s from the source to V which is a Noe in the graph the length of that in residue graph of

**[10:19]:** f okay is that definition

**[10:26]:** clear and this says Delta FV for any vertex V does not decrease okay so it can only uh monotonically in uh increases okay we're going to prove

**[10:58]:** that

**[11:01]:** so we'll prove by contradiction assume this is not the case that means um there is some V that in F Prime which is the uh new Rescue graph is shortest path the uh from The Source in the new residue graph is less than the old one right that's

**[11:35]:** uh we are going to derive a contradiction to

**[11:46]:** that but uh so there may be many such vertices that drop but I'm uh but if there if there's any I'm going to Define V to be the

**[12:04]:** one

**[12:09]:** with smallest Delta in F

**[12:21]:** Prime okay any questions about this

**[12:27]:** step so there could be like V1 V2 V3 that or I make this happen I'm going to choose the one among those that has the smallest distance from The

**[12:47]:** Source

**[12:50]:** okay now here is my source uh we have a path to V in in graph uh GF

**[13:06]:** Prime okay so this is a path then I can always find the predecessor which will call which I'll call you

**[13:20]:** here right if this is the shortest path to V uh what can I say about datta of v and datta of U what can I say about these two

**[13:47]:** quantities can decreas mhm can can we decrease one of them this one is greater than that one of them is greater than the other that's always true right for any

**[14:06]:** two U one okay Misha said V is u+ one does that make sense to

**[14:20]:** everyone cuz that's the shortest path Tov it goes through U okay that's

**[14:35]:** correct so because I okay maybe I wasn't clear about that I defined U to be V's predecessor on the shortest path okay then definitely uh Delta fime of V is Delta fime Delta F Prime U + one okay now I'll use U to be my steps St back to the original graph F I want to say something about this quantity and Delta u in graph F what can I say about

**[15:27]:** that

**[15:34]:** this is a tricky part this one is greater than that or the entire thing is greater than

**[15:46]:** that okay I'm going to claim this one is greater than Delta F + one uh by which I'm I'm claiming this quantity is larger than that can anyone give a reason why I can claim

**[16:09]:** that so recall how I defined

**[16:21]:** V can you good question so V uh so there there are several probably several V's that have uh Delta F Prime less than Delta F right I'm going to Define V to be the be the one with smallest Delta F okay among all those nodes that have a job in Delta F in

**[16:50]:** Delta right this is probably a tricky part then by definition since Delta fu is less than Delta of V right and I defined V to be the to be the one with the smallest Delta that satisfy that so all the 's so U is a pressor of V so U shouldn't be one of those SES who that have a job in delta in Delta right so I I know this is probably a tricky part and uh yeah I'll stop for questions and yeah make sure we resolve this part before we move

**[17:34]:** on how many people get it okay only two that's not good okay I'm confused about how B can be the one with the small Delta F if we have a predecessor with a smaller Delta F okay so uh okay may v to be the smallest the one with smallest F such that Delta F Prime is less than Delta F okay okay maybe yeah that's that's why uh yeah I confused you guys sorry about that so we have a bunch of nodes who have a job in Delta and I Define V to be the one among them that has the smallest Delta F Prime question sorry I'm l what Delta f is versus delta okay Delta F uh of a node is the shortest path from source to that Noe in G of f which is the rescue graph given a flow right so f is uh well some flow and F

**[18:48]:** Prime is the flow after we augmenting a certain path so F Prime is one step after F okay how many people get that now right still not

**[19:07]:** everyone okay any questions about that how how many people like still haven't got that H okay so some people it's like shers cut it's in the middle state

**[19:35]:** well then I'll have to move on and I'll assume you all get this I'll get that one now as the last step so of course we'll ask what's the relation between this guy and Delta F of V right cuz final because in the end we want to show we want to show contradiction that Delta FV is probably greater or equal to Delta F of V this is another tricky part uh so let me ask uh maybe simpler question now so that is our G of f Prime so we also have G of f right it has the source some U here V there sync there uh does this Edge exist in this graph so I know it that edge exists because I defined U to be the predecessor of V right but UV is in that graph doesn't necessarily mean UV is in the old graph so it

**[20:53]:** could certainly exist but is it possible that this Edge didn't exist how many people would say uh that edge definitely exists how many people would say maybe it doesn't

**[21:22]:** exist okay it doesn't matter because we can prove both cases so let's say case one uh UV is indeed in the original graph GFF okay in that case can I say something about that last

**[21:57]:** step

**[22:03]:** greater or equal to Del V okay why is that um because V was on the shortest

**[22:18]:** path yeah so the shortest path either yeah the the shortest path from V either pass correct does everyone get that so the shortest path in this graph to V is not necessarily this one right but if it's some other one okay so in case one I'm assuming this Edge exists right then no matter what the shortest path is it's definitely shorter than I first go to from s to U and then U to V right the shortest path between s to V is definitely short shorter then I first go from s to U and then U to V make sense okay so case one are done it's a contradiction because we showed that Delta F Prime of V is greater or equal to Delta F of V any questions about

**[23:26]:** that okay okaye

**[23:31]:** to UV is not in G GF okay so how can that even happen is it possible and that this Edge didn't

**[23:56]:** exist backwards faing Edge that you add okay great Point that's exactly right so it it is possible that this Edge didn't exist but only appeared after we go from F to F Prime how can that happen that must mean we are augmenting a path that goes right through it right but this Edge doesn't exist so we cannot be augmenting a path that cross this way we must be augmenting a path that goes like that right first from s to V and then V to U and then U to T if we are augmenting such a path then we're going to remove this Edge from V to U but we will add uh u2v to the next graph

**[25:07]:** okay did everyone get

**[25:21]:** that so now uh here more formally I'm going to claims if we assume you u v is not in GF F and we also know UV is in GF Prime what does that mean these two can only be caused by the fact that UV is in GFF G uh G of f not only in that graph it must be on the uh it must be on the path we are augmenting

**[26:05]:** makes

**[26:15]:** sense okay so given that can we say something about Delta F of U and do of

**[26:26]:** ofv

**[26:33]:** so here is our P right this this entire thing

**[26:47]:** here and P is the augmenting

**[26:55]:** path correct right so so if that is the augmenting path in admon car we are looking for the shortest path right so V is the predecessor of U then Delta of U is Delta of V + one that means that quantity

**[27:20]:** here is Delta F of V + 2

**[27:43]:** okay so it's also a contradiction to what we

**[27:56]:** assumed

**[28:02]:** okay so that proves the our LMA of uh every node Delta monotonically increases now here I'm going to show that uh our final theorem that we have at most V number of

**[28:26]:** iterations so the way we're going to show that is

**[28:33]:** uh we're going to show we're going to Define uh a capacity of the path it must be the capacity of its weakest link we're going to Define is weakest link is UV okay and we are going to show that UV uh we'll call that critical Edge we we're going to show UV can be

**[29:03]:** critical only of V times if that if that holds for every Edge then I claim uh all the edges combined can only be augmented of V

**[29:26]:** times now uh how do we show that so

**[29:37]:** again let's assume we are augmenting a path from that goes through U Tov if we do that by our algorithm we will get rid of this path right and have a edge backwards when we go from F to some other F Prime now when can I augment UV again it can only happen if at some point I come back to augment the path going from V to U right and because that will eliminates this back uh back Edge and and adds back our Ed UV okay let's see what happens there uh now let I'll call this graph F this graph F

**[30:48]:** Prime so in F Prime we know we are argumenting the path from V to U by the same argument Delta U is Delta V + 1 in Fr Prime correct and we know this one doesn't drop right so it's greater or equal than Delta F of V + one okay and we also know in f v is the predecessor of U so this one is equal to Delta F of u+ 2 what does that mean it means in between uh two times UV is Argent is augmented Delta of U must increase by at least

**[31:52]:** two then how large can datta of a certain node possibly be is definitely bounded by of V right bounded by V so then I claim this particular Edge UV can only be involved can only be critical P edge of V times actually half of V times strictly so then every Edge combined there can only be half of V * e number of

**[32:26]:** augmentation

**[32:30]:** okay any questions about that part about the entire

**[32:56]:** proof

**[33:11]:** if not we'll move

**[33:18]:** on okay this is not part of the uh required in the recitation but I'll quickly say a few words about uh even better algorithm DC which runs in of V squ * e so this is a Improvement to admon carp and its idea is that I'm going to

**[33:44]:** find all the shortest path in one goal from s to T okay I'm going to augment all of them at the same time time then because they are all shortest path when I augment that each path will be broken right maybe I'll get rid this Edge this Edge and that edge and the thesis is that the shortest path uh will increase right here the shortest path is three but I have destroyed all the shortest path of length three so I'm going to show this part of four if they do that you can bound the number of iterations to all V because your shortest path can no long can be at most V but uh each iteration is slightly more complicated because you need to find all the TR path and it happens that they can show you can find it in V * e that gives the V Square V okay that's not the important

**[34:43]:** part and the more interesting part is that actually the author of this algorithm is his name is Denis but his algorithm is very hard to understand that what well nobody yeah nobody got that and there is some other guy who whose name is I think is Ian uh he he understood the problem and started advertising to people and giving lectures uh on Denis algorithm so he popular popularized the algorithm but unfortunately he got the name of the author wrong and so that's why this algorithm is henceforth called denx algorithm this is useful to know why because you can tell this story to other people so they will assume that you know a lot about DX algorithm well in fact you probably don't and that's exactly what I'm doing here uh

**[35:41]:** okay now let's look at one

**[35:49]:** application uh by partite

**[35:55]:** matching uh okay so the problem is that we have like several person and several tasks uh let me get rid of one person because I don't want to do that many stuff so we have a graph like that and each Edge if there's an edge that means this person is capable of Performing that task and the problem is is that uh find the matching which means the assignment from people to tasks such that we get as many tasks done as possible okay so one person can only do one task and one task only needs one person so here you can see a bad uh matching which is I assign this first guy to task one then no one can do task two right so if I'm smarter I'll assign one of these guys to that task and have this uh person handle the other task is the problem

**[37:05]:** clear so uh this is called bip partal graph because uh well which means you can partition the graph into two parts and within each part there is no Edge connecting any pair of vertices and you can also Define this problem for General

**[37:25]:** graph the goal is the same that find a subset of

**[37:35]:** edges uh such that no two edges are connected to the same vertex okay but we are going to look at uh bipartite uh graph and we claim in bipot graph this can be solved using Max flow okay I'll give you one minute to think about that how to transform that problem to a Max flow

**[38:25]:** problem

**[38:55]:** for

**[39:01]:** any

**[39:25]:** ideas

**[39:52]:** okay a hint uh I will add a source here and the sync there

**[39:59]:** and I'll have create these

**[40:04]:** edges okay how do I restrict the capacity of all the edges such that I can guarantee uh no like each person is no person is taking two tasks and no task is assigned to two

**[40:25]:** people make all of them weight one okay make all of them weight one okay if I we do that one one one one one and everything here is weight one then that's definitely correct what's your name c okay uh if we do that then well because each person only has one incoming Edge oh sorry maybe I I should have drawn the arrows here

**[40:59]:** each person only has one incoming Edge so it cannot take care of two tasks at the same time right same thing for each task it's only it only has one outgoing Edge so it cannot be taken care of by multiple

**[41:17]:** people okay so if we find if the max flow is K that means we can find

**[41:31]:** that the max matching is also okay and we can get K tasks done it's very easy to see because we can have a cut here and if the max flow is K that clearly K taxs are taken care

**[41:52]:** of okay any question about that

**[42:00]:** so the question is can we do all these things uh find a assignment from uh people to task to get as many tasks done as possible so how many tasks can we uh

**[42:16]:** handle okay so I'm doing a a different topic from the recitation note in the recitation note uh we are consider ing another problem called bipot cover which is exactly the same thing as that so cover also by partal graph is defin to as uh let's find several vertices in this graph such that each node at least okay let uh let me me color several nodes in this graph such that each Edge uh is connected to at least one dark node okay and this the nodes I colored is called a cover I want to find a minimum cover you can of course you can of course cover all the nodes that's trip hold but we are looking for the minimum cover and the claim is that mean cover is K if and only if Max flow sorry uh Max

**[43:39]:** matching is K why is that because in that matching uh if we have a matching then we have a set of disjoint edges right no two edges are connected to the same node so if we want to cover these edges we at least have to add one of these guy right one of color one of these two and one of these two right so if we have K matching edges then we at least need K nodes to cover them for example I can col cover them like that uh but this is not a fullprof because I also need to show I can indeed find the cover that that is

**[44:44]:** K okay let me think about whether I should prove

**[44:53]:** that okay I'm going to give it a try um uh if you don't get that that's fine um what cover is okay cover cover is a set of nodes such that every Edge in the graph is connected to at least one of the node in a cover okay so this is not a cover because this Edge is not

**[45:24]:** covered now so in this case I probably have to add that as well but clearly there's a better cover even a smaller cover which is those two right yeah so how are we going to transform that matching to cover so uh let me go first give a matching here One Max matching should be something like this I have this Edge and one of those two

**[45:59]:** that is a matching right that is a Max

**[46:07]:** matching no question about that so let me get rid of all these one way to transform this into a cover is that uh I will first color these two guys uh I'll color the nodes on the left where they are connected to a matching Edge right after that I'm going to start from this one and uh jump between noes taking alternating path meaning I'll take a unmatched Edge and then take a matched Edge and then take a unmatched Edge again but there's no such

**[46:54]:** thing

**[47:05]:** okay and if I take this jump I will swap them make that

**[47:17]:** dark okay this graph is a little

**[47:24]:** strange ah okay now I claim this is a cover is that yeah that is one right and uh if there is another like unmatched Edge going out then I'll keep taking that alternate alternating path but I have to stop because there's no such Edge anymore how can I say why can I prove why can I claim this is a cover so clearly this is if this is a cover then it's a cover of size K right so it's we have proved the entire thing uh then we're going to consider several things

**[48:08]:** separately so I I'm going to first claim if I have a match the edge then it's definitely covered because uh one of its end points is dark right we only do a switching between dark and white if it is inde if it's uh matched Edge itself right so I only need to show that there this thing doesn't happen there's a edge that's unmatched and two of its end points are both white okay I'm going to first claim uh this node cannot have a match Edge because if it does then this is alternating path and I'm going to switch that to switch this two okay make sense okay so this doesn't exist so it can only have unmatched Edge now what can I say about this note I claim this note needs at least one matched Edge because if it doesn't right then I should add this guy into my matching right it doesn't violate any

**[49:19]:** constraint right I didn't add that because there is probably a matched Edge connecting to this guy then I'm going to so then this guy has to be dark because this one is not then how did this one become dark it must come from some other guy on the left right so there is alternating path going back and

**[49:47]:** forth something like this there is an alternating path starting from left but ends here right because we showed that this guy is not connecting to any matched edges in that case what I'm going to do is match this Edge match this Edge match this Edge and unmatch these two edges and that's a larger matching I removed the two I added

**[50:24]:** three that means uh uh Max matching of K leads to a minimum cover of K as well which also means U Max flow of K in our Network flow okay so this part this equivalence is not required and you you should know uh this proof the proof of admon carp and know that matching and cover can be solved by Network flow and that din name is spelled not as

**[51:06]:** din okay and that's everything for today
