Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu. Good morning, everyone. Let's get started. So, part two of uh our two-lecture sequence on network flow. So, all the pain involved in uh the concepts and notation from uh Tuesday uh turns into algorithmic fun today. Uh but we will do a little bit of a review uh just to make sure we're all on the same page uh with respect to all of these notions that uh we talked about on flow networks.

So, we call that a flow network is simply a directed graph GVE and each edge is going to have two numbers associated with it. Uh if you see something like 1:3, this means that this is the flow and that's the capacity. We have a basic constraint that's associated with the flow not exceeding the capacity on any given edge. And we also have the laws of conservation that say that other than the sink and the source which are the two distinguished vertices in GVE you're going to have a situation where for any intermediate vertex all of the flow entering the vertex has to leave the vertex. And with those two constraints you need to find the max flow in your flow network.

Um the flow value corresponding to this potential max flow or some flow is F equaling F of S of uh cap V and so small S is the source. Cap V corresponds to all of the vertices and you're looking at pushing flow from the source vertex to any of the vertices. Uh and that's uh the cap V includes uh T as well. Uh and uh that this is essentially your flow value. And we showed uh this is implicit summation notation. We showed um using a little bit of uh algebra that this equals F of F of V uh T. And that's uh going to hold because of flow conservation primarily. Uh so that was uh not particularly surprising.

Uh something that was a little more surprising or is a little more surprising is that you can have an arbitrary cut in the flow network and a cut corresponds to any partition cap S cap T such that small S belongs to cap S, the source belongs to uh big S and the sink belongs to big T and that's essentially uh a cut. And so obviously there could be uh exponentially many cuts in a given flow network. But the amazing thing is that you can show a lemma that says that regardless of what the actual flow values are in any of these edges um across any cut you're going to see this flow. Uh and this is true for any cut ST.

Um the corollary to this lemma is that the flow is going to be less than or equal to the capacity uh of any cut. And that simply comes from the edge constraints. You know that the flow value corresponding to any particular edge has to be less than the capacity of that edge. So, you um obey that constraint uh and you just look at the uh edges that go from cap S to cap T, sum of those capacities and your uh uh your maximum flow uh or any flow is bounded uh above by that quantity. And that's our CST. Um so you now have a relationship uh between the minimum capacity cut and the max flow. Um we didn't actually exploit that uh in the sense of uh the algorithm itself, the operation of the algorithm.

Uh but uh uh we're going to actually exploit the notion of a cut when we prove this algorithm that I got to late in uh on Tuesday's lecture uh that corresponds to the Ford-Fulkerson algorithm. I showed you the execution of it. In order to prove that it's correct, we're going to need this notion um of the bound on the flow value given any cut in the network. So, the max flow related to min cut. Uh but before we get to that uh just to catch you up on the algorithm that we actually got to, the Ford-Fulkerson algorithm that was based on the notion of a residual graph. This is now a new graph GF which is VEF.

So, it depends on the flow. You compute it based on G based on the given flow F. And um this graph has edges that have strictly positive residual capacities which are defined as CF UV um equals CUV minus FUV and this needs to be strictly greater than zero in order for the edge to exist in G of F. Um so if this is zero, then you don't have an edge between U and V in G of F. If it's one or greater assuming integral flow values, uh you will. And in the residual graph uh two more quick definitions one of which uh you saw last time and another that I just verbalized uh is the notion of an augmenting path and this is any path from S to T in GF.

So, if there is a path from S to T in GF you do not have a maximum flow. Uh there is an augmenting path. You're going to be able to increase the flow corresponding to the F value that gave you your residual network G sub F. And how much can you increase this flow by? How much can you increase F by? That is uh termed the residual capacity and the residual capacity of an augmenting path um is simply CF of P. So, that's what we're going to call it. CF of P equals the minimum value of the residual capacities along the path. So, this would be CF UV. All right. And that's pretty much it. So, add some examples.

Uh it should make this clear. Uh we look at uh what the actual algorithm is and go through a simpler example than we did last time, but it'll give you a sense of uh how uh augmentations are going to change the flow, how augmenting paths appear and eventually disappear as the flow increases and reaches the maximum flow. All right? So, this simply corresponds to as I said, uh walking through the augmenting path, looking at each of the residual capacities and picking the min value. So, the Ford-Fulkerson algorithm which is the first algorithm for max flow continues to be used. Um sets the flow on on each of the edges to be zero.

So, you just set set everything to zero. Clearly satisfies flow conservation. Satisfies all the edge capacities. And you have literally three lines of code here. While an augmenting path in GF exists. So, there's a lot going on here. You have to compute G of F. I mean, it's three lines of code, but uh uh this uh subroutine calls, if you will, which are fairly complicated. Um you have to compute G of F uh given F. Initially, it's all zeros. Uh and then eventually, it's going to change uh or immediately after you discover an augmenting path. And now, you have to discover an augmenting path. Uh so, you have to now do uh either breadth-first search or depth-first search in order to discover whether there's a path from S to T, cuz that's the definition of an augmenting path.

And then, uh the last line of code says um augment F by CF of P. Right? And again, this is fairly involved. Uh you have to take the path in G of F. Um you're going to increase the values of uh the edges that correspond to GFF translating those edges back to G. And there's possibly an inversion in direction that uh is associated with that translation. And so, if you take a really straightforward example, um let's say we have G is S and there's one vertex here, A. And then, you have T. And right now, I have 1 : 2 and 1 : 4. Um I'm now going to compute G of F. Uh so, G of F is going to be I'm just going to write down S A and T, because the vertices are all the same.

The edges are obviously different. Um am I going to have an edge from S to A? Yes. And what number should I put on that edge? One. And then, that's because it's 2 - 1. Right? Not because it's just plain one. It's uh And this edge here is going to have a a a residual capacity of one. And that just comes directly from that one. Right? Um and what that means is, and this is important, uh what that means is that uh in effect, um this residual capacity says, in this direction, you still have a capacity of one. Which means that in this direction, you can reduce by one. Okay? That's the important thing to remember.

And over here, uh I'm going to have I This way, I'm going to have three. And coming back, I'm going to have one. All right? So, straightforward example, but I think um evocative in the sense that it applies the concepts that that we've seen so far uh other than other than cuts. And we'll get to that. And what happens here is is there a path from S to T? Absolutely. And um what is the residual capacity of the path from S to T? It's one, because you got a one here and you got a three here. You got to take the min, and it's one. Right? I guess that's the number of choice today, one. But once you do that and you find that, you say, "Okay, what I'm going to do is uh and this is going to be pretty straightforward, I'm going to look at these edges uh and um I know that I have CFP uh being a one corresponding to this value, and I'm going to go add one to those corresponding edges, cuz this is the These are the edges that I actually chose uh in in terms of the augmenting path.

So, the augmenting path is that. Um and so, this turns into S to A to T. And that becomes uh 2 : 2. This becomes 2 : 4. And that's it. Right? So, so this is uh so so I'm now have G with a new F. So, I can now think about what the the what what is G of F1 correspond to. Um the G is uh uh separate from F. So, in some sense, the G stayed the same, uh but the F changed as you saw here. And now, GF1 looks like S A T. And um what do I do between S and A? Well, I only have something from A to S. Right? I don't have anything from S to A, because the residual capacity in this direction, thanks to the fact that the flow has saturated the edge capacity, is actually zero.

But I do have an edge this way. And what is the value for that edge? It's two. Right? And over here, uh what are the numbers for the top and the bottom? Two and two. Right? And now, I look at GF1, and I go through I've gone through one iteration of this pseudocode, and I now try to find an augmenting path in GF1. And is there a path from S to T? No. Which means I'm done. This is the max flow. Right? Do you believe me? For this example, for this example, you believe me. Do you believe me like for every example? No. Absolutely not. Cuz we haven't done a proof. Right? We haven't done a proof. Okay?

That's why you shouldn't believe me. Um so, we're going to do a proof. Right? So, how is it that we know, given all of this, it's not because I told you so, um that uh when we converge, when we get out of this uh while loop, that we have a max flow? Right? Um looks pretty good. Worked for that example. It's going to work for every example, but that's not a proof. Right? So, so now, we have to sort of taken all the the notions that we've talked about here, including uh primarily the notion of cuts, and uh prove the max-flow min-cut theorem, which uh is going to show this key result that we require, which is that uh when we terminate in the Ford-Fulkerson algorithm, we're going to have a max flow.

Right? And that's the reason why it's it's a maximum flow algorithm. If you don't have that proof, you don't have a max flow algorithm. Okay? So, hopefully all of that is clear. Uh pipe up if you have questions. And let's write out the max-flow min-cut theorem, which uh I mentioned obvious last time, but never really got to even state it. But today, we're going to state it and prove it. So, this is an interesting theorem. I mean, it's a legendary theorem. And uh it's not your usual theorem in the sense that it makes that a simple statement. It actually makes three statements. Um it says the following are equivalent, and it's got three things, which uh are the following.

Um F equals C ST for some cut ST. This says that some cut is saturated. Right? So, that's just the statement. Um the second statement, which is equivalent to the first one, says that F is a maximum flow. So, F being a maximum flow means there's some cut that's saturated. If there's some cut that's saturated for a given flow, you have a max flow. And then, the last one, which is uh important for our Ford-Fulkerson algorithm, is that F admits no augmenting paths. Okay? And so, if I want to show that the Ford-Fulkerson algorithm terminates with a max flow, tell me, based on implications, like um I implies J for numbers I and J, what it is that I need to prove.

We're going to prove a bunch of other things along the way, but crucially, what is the I implies J that I want if I want to claim that the Ford-Fulkerson algorithm terminates with a max flow? Yeah, you over there. Three implies two. That's right. Three implies two. Exactly right. Three implies two. Um so, we need to do three implies two. Now, of course, the theorem says that um one implies two, two implies three, three implies one, et cetera, et cetera. There's a There's a of implications here. Uh what we are going to do is we're going to show that one implies two, two implies three, and three implies one.

Okay, and that pretty much takes care of everything. All right. Um, and it turns out the reason we do this uh, is simply because it makes for the simplest proofs. One implies two, and two implies three are one-liners. And uh, three implies one is a little more interesting and involved. Uh, but uh, it's a little bit easier than directly doing three implies two. Okay? So, that's the way we're going to do this. You can certainly play around and do other things. All right. So, any questions so far? Okay. So, let's go ahead and do this. All right. We should be able to knock these two, one implies two, and two implies three in just about a minute each.

So, I want to show one implies two. And essentially what I want to say here is uh, if I've saturated a uh, a a particular cut capacity, then I have a max flow. And really, I mean this comes from the definitions. Uh, since I'm going to have F less than or equal to CST, and this is simply because of edge capacity constraints. This is just edge capa- capacities for any cut ST. The assumption that F equals C of ST implies F is a maximum flow because F can't be increased. And that's basically it. All right. So, this this is pretty easy. Um, next one is easy as well. Two implies three. If there were an augmenting path, so um, I'm going to do this by contradiction.

If there were an augmenting path, the flow value can be increased because remember the augmenting path corresponds to a path with strictly positive residual capacities. Right? The only reason there's an edge in there is because you have a greater than zero residual capacity. So, that means that the flow value could be increased by some small amount corresponding to CFUV. And each of these quantities that are in here, I'm sorry, corresponding to min CFUV. That's the uh, residual capacity. And but you know that each of these capacities, CFUV, are strictly greater than zero. All right. So, the min clearly is strictly greater than zero.

It might be some tiny quantity, but it's greater than zero, uh, which means that the flow value could be increased, uh, contradicting the maximality of F. All right. So, little proof by contradiction gives you two implies three. All right. So, so far so good. Um, this is primarily based on the definitions of augmenting paths, residual capacities, etc., etc. Now the fun starts. Now we want to show really, I mean this is truly what the max flow min cut is because uh, really didn't have cuts up there. So, what's what's min cut about that, right? So, I had a question at the end of uh, Tuesday's lecture on how come the algorithm didn't use cuts.

And well, the algorithm doesn't use cuts, but showing that the algorithm converges to the max flow uses the notion of cuts. Right? So, what we want to do is do three implies one. And that's going to take care of what we want. And we're going to say, "Well, suppose F admits no augmenting paths." Right? So, what does that mean? Well, that means that you can't reach T from S. Right? If you could reach T from S, there's an augmenting path. So, you can't make that move or make that uh, path. So, let let's go ahead and sort of look at this a little more carefully and figure out what's causing this this uh, lack of connectivity.

Okay? There's a lack of connectivity between S and T. You can't actually get there. And uh, so there's there's like a chasm. There's a gap. And so, what's causing that? And um, what we're going to do is uh, figure out uh, what the cut or the partition is that could be the reason why you have this lack of connectivity. Okay? So, we're going to define cap S, which is exactly going to be our cap S, you know, from our favorite ST uh, cut definition, but bear with me for just a second because we have to I have to tell you what cap S is. Um, there exists a path in GF from S to U. Okay? So, what I'm doing is I'm collecting the reachable vertices from S.

All right. And I know that uh, I'm not going to have T, small t, in this set because F admits no augmenting paths, so I can't possibly reach small t from small s. Right? But I can collect all of the vertices that can be reached from small s in this given G of F and put them all into cap S. Okay? And and then my T definition is simply V minus S. Right? And the key observation which I already have made, but important to emphasize, is that small t belongs to cap T, and obviously small s belongs to cap S. Therefore, ST is a cut. It It satisfies the definition of a cut. Okay? So, we've set ourselves up.

And then we have a a key key observation to make that I'm going to try and extract out of you. Let me move over here. All right. So, what I want to do is I want to draw this out. And I want to look at this as this is cap S. That is cap T. I know that S is over here, small s is over here. Small t is over here. All right. Um, I'm going to pick some vertex V that's over here. Some vertex U that's over here. Okay? I know that there's a path, and I'm writing this as a dotted path because this is a path in G of F. Okay? We're going to actually move between a G of F and G in this proof. So, that's the only hard part of this proof.

The movement between G and G of F. Their edges are different between G and G of F. And but you got to keep got to keep that in your head cuz we're going to make arguments about that. I know that all of the vertices that are on the left-hand side are reachable from S. So, I just picked an arbitrary vertex U. And I know that there's a path in G of F because that's the way I defined it from S to U. Right? I also know that there is no path in G of F from U to V. Okay? Um because if if there was a path, V would have been on this side. Correct? Right? So, there's clearly no path in G of F uh from U to V.

That's why V is over here. But let's say that I'm picking something where there's a there's an edge in G, okay? The original flow network, from U to V. Right? So, the edge that I've drawn here, the dark edge, is an edge between U and V in G. And that edge had a certain capacity. It existed. It The reason it existed is because it had a non-zero capacity. Correct? Because we originally defined our flow network to be something where uh we only put edges in there, in the original flow network, if the capacities were greater than zero. Right? So, that edge out there uh in G had some capacity C U V, which was greater than zero.

Okay? But this edge does not exist in G of F. Correct? So, what can I say? Go ahead. Exactly. In the original graph, uh you you got you have saturated this uh this edge. That was my best throw of the term. I like that. You You guys didn't notice, but maybe it'll be on video. Actually, it won't be on video, unfortunately. But so uh so I got this edge here um in the original graph, and I didn't get this dotted edge here because uh the residual capacity was zero. The original capacity was non-zero, the residual capacity is zero. The only reason that happens is because C F U V is zero. Right? Um since if C F U V greater than zero, then V would belong to S, cap S, not V belonging to cap T, as assumed.

Okay? So, that's essentially what we've determined here. Um so, that means this means that F of U V equals C of U V simply because C F U V equals C U V minus F U V, which is zero. All right? So, that's the statement I can make. Now, I did not have any constraint on U and V. I just said U is belongs to S and V belongs to T. Right? And for each of those things, I know that um I can't have edges in the residual network between U and V, which means that any edge that exists, maybe there's no edge in the original network, but if there was an edge in that original network, it's saturated, according to this argument.

Right? So, every edge from cap S to cap T in the original network is saturated. Okay? And that essentially means that I've gotten to the capacity of my cut. That's essentially what that means. If I've saturated every edge, I've I've reached that capacity. Okay? So, that's it. Um you All you do, once you recognize that you had an arbitrary choice of U and V, you just say summing over all U belonging to S and V belonging to T yields F of S T equals C of S T. All right. I'm on on a roll, not just with Frisbees. I finished the proof with a finger to spare. Um so, F of S T equals C of S T. All right?

So, that's exactly what we want. Um we're saying uh F of S T is of obviously uh cardinality of F, so I've shown this thing over here. All right? So, that's why the Ford-Fulkerson algorithm works. Right? It's because of this analysis that the Ford-Fulkerson algorithm works. So, have we done? What are we missing in algorithm uh design or algorithm analysis? Not you yet. So, sorry? Run time. Good. Run time. Right? I know you have too many Frisbees. You probably do, too. But uh so, we haven't done I we've done correctness. We've done conversions. We haven't done a complexity analysis. Right? And so, there's some bad news here.

Right? And we're reaching a pivotal moment in 6046. Why is this a pivotal moment in 6046? It's on the Frisbee. Exactly. This picture, I mean not exactly that picture. Uh it's not quite that picture, but it's it's it's the same graph. Okay? It's uh it's a pivotal moment because this picture was famous because it was in a textbook. But now it's iconic because it's on a Frisbee. Okay? We we immortalized this picture. Um so, this is an example of uh really a failure of the Ford-Fulkerson algorithm. Okay? So, it's kind of a bad example on this Frisbee, but it's going to lead us to better algorithms.

So, what I have here is uh a weird flow network that has these strange capacities. I mean, it's a fairly straightforward flow network, but uh as of as of the moment, it obviously satisfies uh flow conservation because all of the flows are zero and therefore edge capacities. But we're going to now take a pathological execution of the Ford-Fulkerson algorithm, which by the way did not specify how you were going to select the augmenting path. All right? It just said find an augmenting path. And in passing, I said uh oh, we'll use depth-first search, we'll use breadth-first search, and kind of hand-wave my way through that.

Right? Now, it turns out you can you can't hand-wave when you want to run algorithms, right? Eventually, you have to code them up, and you got to pick something. Right? So, people did. People picked different ways of selecting augmenting paths in the Ford-Fulkerson framework, and they discovered that some of them would work beautifully, and some of them would fail miserably on networks that were as small as this. And they'd just take forever. Okay? And this is before complexity analysis. Kind of maybe before asymptotic complexity really came into vogue. So, they just had empirical analysis to tell them that some techniques for discovering augmenting paths work better than other techniques on an empirical basis, on an empirical basis.

Okay? So, um what could go wrong with Ford-Fulkerson on this example? What selection strategy corresponding to the augmenting path could cause Ford-Fulkerson to have a huge number of iterations? Right? Go ahead. So, each time you pick an augmenting path, you pick one that goes through the center. Exactly. And uh so, let's walk through uh let's walk through a couple here. So, the first one, uh let's just say this was A and B to make it easy. So, what's the first path that we pick? What's the Go go for it. You're not off the hook yet. Yeah. You pick S to A to B to T. Yeah. And then And then when you pick S to A to B to T, I'm not going to draw G of F for this.

Um it's pretty clear that uh G of F is going to have um uh uh You you I'm sorry. You you end up picking S to A to B to T corresponding to the G of F that you've created. Right? So, the GFF might have something like S to uh A there's only going to be an edge this way that's going to have 10 raised to 9, and then this way it's going to have one. And uh that's going to be B, and over here uh to uh to to T it's going to have uh 10 raised to 9. Right? It's also going to have uh 10 raised to 9 this way. And it's going to have 10 raised to 9 this way. Right? And the reason the gentleman was laughing is because um we ended up picking this path.

Okay? S in GFF, this is GFF, just to be clear. You pick S A B T. Okay? And so, what you end up doing is you end up making this one uh making this one. And uh coming over here, making this one. All right? Wow. Okay, you did increase the flow. Very good. Made progress. Right? Um now what happens? Um when you do this um it's suddenly you'll get a different GFF. Okay? And the GFF is going to turn into well, this gets a little more interesting here. This is 10 raised to 9 minus one. This is 10 raised to 9. Uh no, that doesn't change. Um this is still 10 raised to 9. Uh this is uh 10 raised to 9 minus one.

And uh this edge here also changes because um it uh uh it's basically what what ends up happening is you end up going this way with one. Okay? Did I get that right? Yeah. Okay, good. So, now what's the bad path? S B A T. Okay? So, S B A T would now say, "Oh, what I'm going to do is I'm going to go ahead and make this one." What do I do with that? Make it zero. Exactly. Make it zero. And then this one becomes a one. Shall we keep going? No. All right? So, two billion iterations for a graph with four vertices. Now, that's performance for you. Right? So, this particular potentially a depth-first Ford-Fulkerson on this example, depending on the ordering of vertices, it's certainly quite possible uh that um uh you would get uh you would get uh this particular order in the depth-first search on GFF.

Right? Uh the computer is is dumb. It tells does what you tell it to do. It's doing depth-first search. It's producing these paths, and you end up with two billion iterations uh for this. Right? And how many iterations do you really need if you did it right? Two. Right? So, so that's a billion factor slow down. So, this is a pathological example, a simple pathological example to just show you what the problem is. But you can imagine that if you use depth-first search, you might be a factor five slower uh on average than if you use some other technique. And a factor five is nothing to be scoffed at, especially if you're running for minutes.

And you know, back in the day computers were horribly slow. Right? So, um how is this problem fixed? Well, any number of ways. Okay? And but the first real way that took into account asymptotic complexity, did analysis, and did all of that was due to Edmonds-Karp, which is a few years after Ford-Fulkerson. In fact, several years after Ford-Fulkerson. Right? And their contribution was not as much um a new algorithm, though it is called Edmonds-Karp algorithm. It it's really a small change to Ford-Fulkerson. You might want to think about it as the Edmonds-Karp analysis, which was kind of important, and we're not going to do that here.

Uh but you'll see it in section on Friday. Uh but the Edmonds-Karp algorithm {slash} analysis is that um if you use a breadth-first augmenting path, which is obviously just as easy to discover complexity-wise as a depth-first path, then you could get a polynomial bound that did not depend on the capacities for the complexity and therefore iteration count of Ford-Fulkerson. Okay? So, that was their contribution. And so, the breadth-first path is a is a shortest path um in G F from S to T if you count where each edge has weight one. Right? So, in that case, you would get your two iterations. You get the shortest path of weight two.

Right? Whenever I say weight, I mean just counting the number of edges. Um and these algorithms, they actually recognized that breadth-first implementations of Ford-Fulkerson were the ones that ran faster than all of the other ones. Right? And then they said, "Wait, wait, what's going on here? This looks pretty good." And so, they went off and did a fairly sophisticated analysis uh that showed uh that you you you had and as I said, you'll see that uh in section that you only need order VE augmentations in the worst case. So, this is what we know and love with respect to algorithmic complexity.

Right? Order VE augmentations in the worst case, provided you use breadth-first augmentation. Right? So, what is the overall complexity of the algorithm? The Edm- let's call it the Edmonds-Karp algorithm with this breadth-first search. It would be? Order VE squared. Uh you could think about it as let's assume that E is greater than uh V. And so, we'll we'll just say order VE squared time. All right? So, so that was the Edmonds-Karp's contribution. Um there's been an amazing amount of work over the past 30-40 years on improving that bound. Right? Dinic um uh independently arrived at uh uh a similar analysis and bound uh along with Edmonds-Karp.

Uh they were the first to give polynomial bounds on max flow. Uh and uh there was uh an algorithm that uh came out of um MIT uh partly or at least MIT alums where you improve that. And so, until about 2011, and there's a lot of different algorithms depending on whether you're taking into account the value of the capacity, uh and you want to think about this as as uh some max value. And uh if you want to include that in the complexity, then uh things change a bit. If you can limit that, but assuming that those capacities are um essentially um unbounded, then the fastest algorithm in 2011 was King Rao and Tarjan.

Tarjan. And that runs in order VE log of E divided by V log V V. Obviously need something for the log here. Um so, uh so that's that's kind of pretty good here, right? Because this is pretty small. Uh it if you if you really think about it, if E is large for dense graphs, this is going to be a small constant. Okay? So, that's that's pretty good. So, that was the fastest until 2011. Um very recently, Orlin, who's at MIT, um came up with an order VE algorithm. And there are many variants here that use fast matrix multiply. And then just this past uh September, um Alexander Madry joined our department, and uh he has uh a a variant algorithm uh that uh uh it it is better in in some sense, not uh in the the pure sense of uh V and E, but uh there's there's a couple of constraints associated with it that are very uh mild, but it's uh in that sense better than order VE.

And I won't get to that. Uh in the context of um 6046, uh we're obviously going to stick with uh Edmonds-Karp and Ford-Fulkerson in terms of what you're responsible for, but it this has been a rich area of research for uh for decades. Right? Yeah. Um so, can you explain um the vector by E squared Oh, uh simply because uh the uh augmentation uh breadth-first augment- augmentation takes order E. I'm just saying it takes order E time. So, this was the uh order VE augmentations in the worst case. Each augmentation takes uh order E time because breadth-first search takes order E time assuming that E is greater than V, and I just added the E uh squared factor.

Thanks for asking. I'm sure a lot of other people had the same question. Um yeah, so I I just sort of skipped over that a little too quickly. Um that's why we get the order VE squared. Okay? Um and so, that's a significant reduction uh if you assume that uh constant factors don't explode going from um Edmonds-Karp to uh King, Rao, and Tarjan, and uh and and certainly Orlin. Okay? So, so now we got algorithms. We've proven them correct. We've done some analysis. Uh uh tomorrow in section, uh you're going to see uh uh uh the analysis that gives you the order VE, uh which is uh half hour's worth of uh uh pain, should I say?

Uh no. Half hour's worth of excitement. Uh that corresponds to the order VE uh bound that we have. All right? So, it's not that difficult. It's about the level uh of uh this this thing over here. All right? Maybe a little bit more involved. Um so, yeah. Um shouldn't each augmentation take order V? Uh I mean, breadth-first search takes order of V plus E time. Right? On a graph, uh breadth-first search is order V plus E. I and I'm getting lazy here, and I'm paying for it uh by uh putting in the VE squared, but I should really have been, if I wanted to be a stickler, I would have put in V plus E.

Thank you. Right? Um so, uh where was I? Uh so, we got an algorithm now, you know, we got a bunch of algorithms. Uh network flow is this amazing hammer that's been used in a wide variety of things. It's been used for matching, bipartite matching, all sorts of uh things. Uh my favorite example um is uh uh something that uh uh is uh related to sports, I should say, uh which is the baseball elimination. Right? So, uh what is this application about? Uh you see charts that correspond to uh how your team is doing, standings, right? Go go to ESPN and uh click on standings for baseball, for example. I mean, it doesn't Now, you see preseason standings, but let's assume it's uh August or something.

And you you click on you click on standings, and you see a chart uh that corresponds to games played, games won, games lost, games remaining, and so on and so forth. And back in the day, uh when uh they were just uh winners corresponding to uh each division, you had to win your division to make the playoffs. All right? So, you had to you had to be the best. All right? Now, if you ended up being tied, uh you ended up having to play an elimination game. But, uh the whole uh purpose of this analysis is um deciding whether you still have a chance to make the playoffs or not. All right? So, the goal here is we want an algorithm that is going to look at the standings and decide if your team is alive or not.

Okay? Does Is there a chance if God is great, whatever, uh uh everything goes your way, angels in the outfield, right? Uh you're you're going to make the playoffs. Okay? And so, you can be very optimistic. Um and you might think that this is a straightforward I'm going to add up a couple of numbers and figure this out. Right? It turns out it's not quite that simple. Though sports writers would love to think that that it's as simple as adding up a bunch of numbers. And and obviously, there's network flow lurking in here somewhere. Right? Otherwise, I wouldn't be talking about it here. So, um this is not quite historical in terms of the standings.

I tweaked the numbers a little bit in order to make this example a little more interesting. But, roughly speaking, August 30th, 1996, this was the standings corresponding to the American League East. Okay? And now, this is 1996, so the the teams are a little bit different uh from uh what you have. So, New York, unfortunately, was leading the division even back then. Still had Baltimore. Then there was Boston. Okay? And then there was Toronto. And then this is back in 1996, and Detroit was part of the AL East back then. This is before realignment. All right? So, let's just call these one, two, three, four, and five.

All right? Those are the positions. All right? So, Boston was in third place. Okay? And so, I'm going to say these are WI, which are the wins so far, LI, which are the losses, and RI, which are remaining games to play. And um this is usually what you see. I mean, this is the simple version of the standings. And I'm just going to give you uh some of these are most of these, I should say. And I'm not going to write down what Detroit is, simply because I'm going to vary that number. Because it gets interesting as that number varies. And each of these teams had 28 games to play. Okay? So, that's usually what you see when you see a snapshot.

Okay? Um Now, I'm going to also add RIJ, which are the games that these teams play against each other. And the reason is simple. Um there's clearly a correlation between win-loss count specifically corresponding to games that Boston plays with New York. No ties is uh in baseball. So, if Boston wins, New York loses, and vice versa. All right? So, I want those numbers as well. And these are things that um you typically don't see, but they're going to be important because they do determine whether your team is alive or eliminated. All right? So, five. The reason I have dashes here is because a team doesn't play itself in the diagonal.

Yes, that is absolutely the number of games that they're going to play against each other. RIJ. All right? So, I mean, that's a small number. I mean, 5 + 7 12 uh uh + 4 uh what is that? 16? 16 + 3 is 19. Uh there's 28 games left to play. There's obviously games that are being played against other teams outside the division. All right? So, this is just RIJ. Okay? So, so that's the story here. And um oh, I should say that um uh when I when I uh I talk about this, what what uh what what are these corresponding to? Well, this corresponds to NY. Uh this column this corresponds to Baltimore. This corresponds to Boston, same order.

This corresponds to Toronto. This column corresponds to Detroit. Okay? So, otherwise, it's underspecified. Any questions about the table here? If you want to know, the Red Sox did not make the playoffs that year. So, all that most sports writers do, most people do, is they say team I is eliminated if WI + RI is strictly less than WJ for some J. All right? So, you're just going to say, "Okay, you know what? If I won all my games, I'm still not going to make it to this team that's already won 75 games." Right? And so, clearly, I'm done. Uh that that that team has already won more games than I can possibly win.

So, that's an easy one. Right? That's an easy one. And so, this is strictly less because we're just talking about elimination. All right? Total elimination. You know, you get your summer vacation or your fall vacation. So, let's just say that you had Detroit um and we're talking about W5 here, so we're talking about this number here, is 46, L5 is 88. All right? So, they're having a bad season here. Um and you go and you say 46 + 28 = 74 which is less than 75. Therefore, in this scenario, Detroit is eliminated. Right? All makes sense? So, this is sufficient. But, I claim it's not necessary. So, you might actually have false hope if you are a a mere sports writer who only knows to add up these numbers and compare it with others.

But, if you were a 6046 student and you went through these wonderful lectures on network flow, you know much more. Right? And we're not quite there yet in terms of um requiring the power of network flow, but I ask if what if W5 were 47? Right? Can you make an argument which clearly doesn't work here with this naive argument. You have 75 = 75, so you still have hope. But, can you make an argument that if W5 were 47, given the whole table, that's the hint, the whole table, that Detroit was actually eliminated? Right? Where's the Frisbee for Seattle? Right? Over there. Saw you first. In Detroit, the only way Detroit can get more wins than New York is if they win all their games and New York loses all their games.

Yes. And if New York loses all their games, they're going to lose seven games to Boston. And Boston will have 76 Exactly right. So, that's a great argument. Could you stand up? All right. And catch well, too. Um so, that's that's basically the essence of the issue. Uh there's stuff going on which corresponds to teams playing each other that can affect the outcome. Okay? So, let me write out what the gentleman just said. Um still eliminated. Boohoo. Because W5 + R5 = 75 now. 47 + 28 is 75. But either New York or Baltimore. I mean, there's many ways you could uh just you could you could show this.

But, we'll just take uh this is not exactly what the gentleman said, but this is what I had here. So, let me just write that out. Either New York or Baltimore will win 76 games since they play each other five times. Okay? So, okay. All right. So, now I'm going to do some more sophisticated analysis and I got what I wanted. But, let's say that W5 was 48. Right? So, this was 76 and it kind of worked out for both of the examples, the one with Boston and the seven games that I got as an answer and this one that I just wrote down. But what if W5 = 48? Is Detroit eliminated? How many people think Detroit is eliminated?

All right, a bunch of you. Uh you want to explain why? So, um New York, Baltimore, and Boston are guaranteed to get a total of at least 14 more wins. Okay. Which means um their total number of wins that they're allowed to have without any of them getting to 77 is only going to be 13. It'll be like 1 + 5 + 7, so it's too many. But, they're not actually eliminated cuz this is from the wild card era anyway. Uh I didn't like the last part of your answer. Right? Did But, but the other question is did people understand the first part of his answer? Right? That was complicated. I mean, it it was it was the right analysis.

Great Great job. Right? So, we want a systematic way so we can run an algorithm so we can't you know, need to bother with this type of analysis. Right? Um and you're exactly right. Uh this it turns out I I skipped this little detail uh because it was inconvenient. Uh which is that uh in '95 a wild card was introduced. So, uh we could think about this as elimination from being the division winner. Okay? So, that's an aside. Thanks for pointing it out. Um it's important to know sports history. Uh really important. Almost as important as 046. Uh but uh basically it gets more and more complicated uh as you uh get closer and closer to these edge cases.

Okay? And so, you can do an analysis uh and I'll actually describe roughly what uh your analysis was. Uh what's your name? Alexander. Alexander's analysis was. Uh and but I I don't want to do that yet. I'll do that at the end if you have time. I I want to give you a general purpose technique that obviously is going to use max flow to solve this problem. All right? So, we're going to set this up and so, that's uh actually one of the nice things about uh maximum flow, how it can translate, you can sort of create these networks from tables or what have you and add capacities to edges, you know, find max flows, and solve these problems.

Right? So, this is a good example of that. Uh so, let's say let's go ahead and do that. I I am going to draw a flow network based on this table. Okay? It's going to have a source and a sink that are basically these dummy nodes that are essentially going to source well, infinite flow. Uh but, the capacities of the edges are going to come from that table. And the edges themselves are straightforward in the sense that the graph is going to kind of look the same uh based on the number of teams and the particular team that you're analyzing. So, this graph is trying to determine this is a flow network to determine if team five Detroit is eliminated.

Okay? This is just a flow network. Um I'm going to have a a bunch of edges. I'm going to just draw this once and we'll be moving things around on this. Two to three. One to four. Two to four. And lastly three to four. Okay? Uh the reason you don't see five here is because this is uh an analysis for team five. Right? So, the other four teams show up here. They have edges going to T. Um S is over here. And uh it's got a bunch of uh edges going to all of these nodes. What are these pairs? As you can imagine, these pairs correspond to the games that each of these teams that are inside the circle play against each other.

So, three plays four uh a certain number of times. According to that table, there's four times. So, I'm going to put a four in here. Um this is four as well. Four. Five. Seven. Two. Okay? And uh the edges in between here are going to have capacities of infinity. And how are these edges structured? Uh so, so far I've just explained how the left-hand side works. These edges have a capacity of infinity. One two goes to one. One two goes to two. One three goes to one. One three goes to three. And that's pretty much it. So, that's where these edges are. Or that's how these edges are introduced. And all of these edges have a capacity of infinity.

Two to four. Three to four. And that. Right? So far, it's pretty straightforward. Um there's one last thing that we need to do which is add capacities to these edges. Right? And this is actually crucial. Uh it turns out that we have to add capacities such that this max flow is going to represent elimination, right? So, these capacities have to be chosen. And in particular, the equation for this is simply W5 + R5 - W1. Right? And that is in this case, if it's 48, I'm asking the question for 48 for W5 + 28 - 75. Right? So, that's that's one. Okay? And then this thing here would be um W5 I'll just write that out.

W5 + R5 - W2. Hopefully you can read that. And that's a five. And then similarly this is a seven and that's 13. Right? And so you might might ask what what does this represent? Well, it kind of represents what you think it represents if you just look at that equation. It says um I how much can I push through here before I get greater uh than uh than W1. So, what is the capacity? What's the difference here? Um I I I I will still if I have a one here and uh that means that I still I I when I see W5 + R5 um I'm I'm one greater than W1. So, in particular uh if I want to write this out the capacities are the number of games team I can win and not have more wins than team five.

Okay? So, this is really a a a statement about uh team one when I see that over there uh our team two for the other edge. And I'm just trying to figure out how much can I allow uh with respect to this this this other team to determine elimination for the particular team that I'm looking at, team five or not. So, in particular um let's say that uh uh team I uh can wins wins one particular game. So, it goes up to it goes up to 76. And if it goes up to 76 um it uh does not necessarily have more wins than team five because team five can go up to 76 as well. Right? That's pretty much it. And the same thing for team two, team three, and team four.

Okay? Uh so the intuition here is is the following. So, what we're going to do is compute a max flow and look for a certain property on that network. And that's going to tell us if team five is eliminated or not for the particular choice of WI of 48 because that's how I constructed this particular example. So the intuition is assume team five wins all remaining games. That makes perfect sense. Um this is the best case scenario. You're trying to figure out in the best case scenario, are you eliminated or not? Is team five eliminated or not? And what you want to do is divvy up the remaining games.

And that corresponds to sending flow through these edges. So, flow through these edges corresponds to assigning wins to teams one, two, three, and four. Okay? That's the key. Uh divvy up the remaining games so all teams have less than or equal to W5 + R5 wins. So, what does it mean if all teams have less than or equal to W5 + R5 wins? If you can divvy it up such that that's the case, what does that mean for for team five? Team five is still in the game. Team five is not eliminated. Okay? So, if you can do this then team five is not eliminated. Right? Um if you can't, team five is eliminated because some team is going to get uh 77 wins.

All right? And so that analysis that Alexander carried out wasn't a a flow analysis, but somehow that's got to be in here. Right? That type of analysis has got to be in here to show that some team is going to get to 77 wins uh because uh we know uh well, thanks to Alexander uh that Detroit is going to be eliminated here. Okay? Uh but we want to show that in terms of the max flow on on this network. All right? So um there is an associated theorem that I'll write. Oh, good. We got enough time here. We just have to find the max flow for this and that should take just a minute. But I want to set it up so that's pretty much the end.

Finding the max flow what that means. But the theorem is, which is essentially a a more precise restatement of this observation all right? is that team five obviously you can do this for any team is eliminated if and only if the max flow does not saturate all edges leaving the source. I e. in this case the max flow is strictly less than 26. Uh This corresponds to the sum of those things. 5 + 7 + yada yada yada. Right? So, what does it mean to to uh saturate all of the edges? It means that all the games have been played. Right? All all the relevant games here that affect team five have been played.

So, you you want to play all the games because that's the the the the end game if you will. Um but uh basically what the intuition here is that saturation of those edges corresponds to playing all remaining games. And uh the argument is not a proof. Um if you can't play all the remaining games without exceeding the capacity of I to T edges uh team five is eliminated. So, you have to saturate because you have to play all the games. And when you do that saturation obviously your flow network has to uh satisfy its laws corresponding to the capacities that we have in there. And it's quite possible that um this is going to cause a restriction over here that corresponds to requiring that not all the games be played uh in order for Detroit to survive.

Okay? And that's basically the game. Right? So, saturating the network means playing all the games. And uh if you get a max flow uh to be more concrete if you can get a max flow here that's uh uh uh uh less than uh 26 uh then uh you saturated all the edges and uh uh which means that you played all the games and uh you found uh this team uh that beats uh you. The beats uh team five. Okay? So, um what what happens over here? Uh let's take a look at this. And we All we have to do here is to find the max flow. And then we can go back to the statement of the theorem. So I want to find the the min cut corresponding to this, which is going to tell me what the max flow is.

I mean, I could go around Ford-Fulkerson on this and start with zero and augment and so on and so forth. But there's another way which is not necessarily algorithmic, but eyeballs. Use your eyeballs. And uh find me the min cut here which has the minimum capacity. Right? The min cut with minimum capacity is going to tell me what my max flow is. Right? We know that from the max flow min cut theorem. Right? So, uh I want to cut this network into capital capital S and capital T and find uh find the max flow. Okay? So, any ideas? It's a little hard. All right. So, I see some people waving their hands.

All right. Let me Let me just do that since they're running out of time. It's kind of cool. So, we'll use a different color. You're going to go like that. Yeah. And then veer over this way. And then jump up like that. And then come over like that. Okay? And this is S. And on this side is T. Okay? So, I got small S in capital S, small T in cap T, but I got this uh four in cap T. Notice that I got three to four, two to four, one to four in cap T. And I got these other ones in in in uh in in cap S. All right? So, all I've done here, you know, forget baseball elimination, is find uh a min cut. And if you look at uh what the value of this min cut is, uh the value of the min cut is simply uh the capacities of the edges that go from S to T.

Okay? So, it's simply the S to T edges and summing over the capacities. And if you take a look, obviously S to T, you got 4 + 4 + 4. So, you got 4 + 4 + 4 corresponding to this one, this one, and that one. Um do I need to add this edge in here? Over here? That edge has Where does that Where does this edge go? From this this to over there. That goes from T to S. Right? So, that's good because that has a capacity of infinity. That would cause trouble. Um and so, the other edges are um I got one, five, and seven. So, I I need this one, that one, and that one. Okay? So, 4 + 4 + 4 + 1 + 5 + 7 equals 25.

Right? And so, this implies elimination because um what I've done is found a max flow, which is strictly less than 26, which means that I have not saturated all of the edges that come out of S. I have not been able to play all the games. Right? And so, if I played all the games, I'd be exceeding uh some capacity constraint. And if I push more flow in there, I'd be exceeding some capacity constraint on this side. And uh that would imply that uh that the Detroit is eliminated because some team would have a 77 wins. All right? So, hopefully you got the gist of it. Um I'll put this in the notes. Take a long hard look at it.

Uh the particular values aren't important. The framework of translation is important. And uh you can certainly ask questions of your TAs uh on on Friday. And I'll stick around here for questions.