Ford-Fulkerson: Min Cut

[00:00:00]
>> Let's try a different path because obviously I chose one path that totally worked out. But what happens if we do a different path? What happens if things don't work out as nicely as we just had them work out here? Let me just erase all these little things.

[00:00:14]
Cuz there's another path through this graph that kinda screws things up. So 0, 0, 0, 0, 0, 0, 0, 0. Lets' start at the bottom and I'm gonna choose five, five, five, eight. So I'm gonna go down, down, through the middle to eight. So that means we will be able to have a maximum flow of five cuz that is our smallest pipe.

[00:00:42]
But I want you to make an observation. What is the problem with this flow?
>> Cuts off the bottom, yeah.
>> Cuts off the bottom node, exactly. So a part of the Ford-Fulkerson algorithm is they call this the augmenting path, the path that changes the flow. And so what it allows for is after you make a flow to a node, you actually create a back link.

[00:01:08]
This back link has a negative five flow. This back link has a negative five flow. This back link has a negative five flow and this back link has a negative five flow. The rest all have zeros, negative zeros, if you're IEEE floating point standard. We're not floating point standards here, okay?

[00:01:30]
So now, if I wish to try to do something, I can't go along this bottom route anymore. I can no longer take advantage of this. But if I choose to go seven, ten, negative five, ten I'm able to put five units of flow this direction back through cuz we have a negative five flow.

[00:01:51]
So I can bring this one back down to zero as much as possible. If you think about this will make more sense, we'll just see. So if I put five units of flow this direction, it will turn this into a zero and turn this back into a zero.

[00:02:05]
And now, I'm able to put five units of flow through here at the very end. If you've noticed, we've re effectively created the exact same problem that we had before. Now we've chosen and now we've kind of healed or augmented our path to be back to what it was.

[00:02:22]
So now, you can see I just went reverse through, cleared everything out, and now I can do this path or I can do this path and create again the maximum amount of flow that we need. So, I can just go like this. We can do two or three along this line, right?

[00:02:37]
So I can just go 3, 3, 8. And now, again, our maximum flow is 13. And so, the goal here is just to find a path, and you may have to use negative weights. The negative weights will be going back through and reversing a flow which allows you to effectively open up this path down at the bottom.

[00:02:59]
So if you goof something up, the negative flow will help you. All right, awesome. Everyone feeling good? Yeah, because we just put five flow units through this way. I can do that, I can just do that, okay? All right, so what do I mean by car problem British people?

[00:03:19]
It's very funny. I listened to this person a long time ago and he did this explanation of how do you find the minimum cut? And he's just like when he was talking, he was talking about a car driving through the maze this way. And when driving through the maze he called this the passenger side and this the driver side.

[00:03:37]
So I knew right away, something's off here, okay? That's not how things work. And so, if you have a flow that hits the passenger side of your very not American car, you add that to your minimum cut. If it hits this side, you don't add it to your minimum cut.

[00:03:55]
And this does make sense cuz look at this, how much flow is going through this? None, we don't even use this link. This is an unused link, so when we make a minimum cut, it does not count towards our total. And so, if you imagine we drive our car, our car gets hit on the passenger side, our car gets hit on the driver's side, our car gets hit on the passenger side.

[00:04:16]
So we will do 5 plus 0 plus 8 or 13, the minimum cut across this graph to separate out the sync. Wait, the sync from the source, there you go. Kinda fun little way to remember it, that's how I always remembered it. I don't know why I just think this is a great way to remember it.

[00:04:35]
So in my head, I'm always like car, British people. And then I just drive my car through there and it just works. And you can kinda think of this, if this was like, if you had a hose completely on and water was flowing through here, what would end up happening is all of your water would go here and none of it would go here.

[00:04:49]
So if you cut it, nothing would come out, theoretically, nothing would come out. Would that actually happen in a practical world? Probably not because things aren't as clean in the real world as they are in the fake world, so you'd probably get stuff. But in the theoretical world, no flow would happen here because the sync's taking all the flow that it can through this bottom part.

[00:05:08]
All right, there you go, that is maximum flow, minimum cut.
>> Would this work when scaling up to multiple sources and syncs?
>> I'm sure there is a multiple source, multiple sync problem. I haven't looked at it so I don't know that one. Anytime you get into multiple like Dijkstra's multi stuff you get into NP hard super difficult problems that aren't very easy to solve at all.

[00:05:35]
Every graph problem is just teetering on the edge of becoming a really hard problem. And so the moment you add one more condition, it just blows up. I don't know that one, I'm sure there is some algorithm that has explored this. I've just never tried it, so I do not know.

[00:05:49]
All right, so there is one more thing to say about this. What is the runtime of this algorithm? Kinda crazy, right? Anyone wanna make a guess? No one can Google though, no Googlies, okay?
>> I can guess linear?
>> Linear, no. Yes, but no, V squared? Wrong, you're dead.

[00:06:13]
All right, so I'm gonna make a graph that hopefully it makes sense. Okay, you can just see it right away. So we have a source, we have a sync, and in between, we have these two nodes. And then this one across here. This has a maximum flow of 1, this has a maximum flow of 100, 100, 100, 100.

[00:06:38]
So that means, remember, we're doing a depth for search, do you have any guarantee on order? You don't know the graph ahead of time. So you could imagine you go and you choose a flow of 1. When that flow of 1 happens, you get one out of 100, you get 0 out of 1, you get a back link of -1, then you get 1 out of 100.

[00:07:05]
The next time you search, you do this, you backflow the other direction, you backflow the other direction, you back flow. You just keep on going back and forth and you're doing one flow at a time. Eventually, you would eventually at the very end hit a maximum flow of 200, but it would take you 200 times through the graph and you could potentially touch every single edge.

[00:07:26]
So the runtime is the maximum flow times the number of edges. It is the strangest of them all, okay? The strange runtime, people don't often see this one. If you could whip out a maximum flow runtime in the interview, I think the person would just, so what is happening here?

[00:07:42]
It's just like using square root of n. If you can hit them with the square root of n runtime, blows their mind. But that is the worst possible case of the maximum flow algorithm. So there you go, it's maxflow times edge.