Karger's Algorithm: Procedure

hello so today we're going to be talking about Carter's algorithm but before we get to that we're going to talk a little bit about kind of what the problem is that Carter's algorithm is trying to solve so there's a general category from called the min cut problem and what that is is trying to divide a connected graph into two disjoint connected graphs which are sub graphs of the original so let's do an example just gonna kind of show what I'm talking about so let's make ourselves a little graph pretend that's anyway so let's let's go like this and let's give our graph some edges so no graph so in the definition above this would be our graph G and what we want to do is we want to break this into some sub graphs two different sub graphs which are some of the nodes but not all of the notes and those sub graphs should be connected to so one example would be lets say removing these three edges if I did that then I have one sub graph here which is connected to itself it's just one node so it's obviously connected everywhere and then another sub graph that's all these nodes and so in the definition above we could call this one as 1 this 1 s 2 but you might be noticing this is using 3 edge cuts that's not as few as possible so the min cut problem is saying which two sub graphs should I cut this into so that I have to cut as few of these edges as possible so let's let's take this cut back and instead you might see that for this graph we can cut this edge and we can cut this edge so we can cut only two edges and that'll let us divide it into these sub graphs which are perfectly valid connected subgraphs we can call these s1 s2 instead and with this cut it only costs two and as it turns out this is the the min cut for this graph so min cut equals q edges so this is the problem that the Carters algorithm is trying to solve there's an older more classical example of how to solve this which is called max-flow min-cut so this is the traditional algorithm that was around before Carver's offer them and it's still used in some places it has a few characteristics so the first is that it's deterministic you are always going to get a min cut when you run the max-flow min-cut algorithm a hundred percent of the time you're going to get but that comes at a cost because it can be pretty slow so the the run time of this max-flow min-cut algorithm can be optimized and this is kind of the best best possible case for this is are the best possible optimization for the worst case of it is the number of vertices times the number of edges squared and as you can imagine that that can kind of get pretty big that's it's not on the order of n cubed exactly because these are different quantities but you can think of it pretty much on the order of of that kind of scale so cargos algorithm is a way to kind of get around those downsides so carvers algorithm is a little bit different so let's just write that Harker's algorithm all right so Carter's algorithm is a randomized algorithm so what that means is you never know for sure whether you're going to get a min cut out of this algorithm you can give it a graph and say give me the min cut and it knows that there's some probability that it'll give you the right answer but it's not a sure thing so generally what these what randomized algorithms will do in general and Carters algorithm is no exception is they'll run a lot of iterations of their probabilistic algorithm see what the answers they get are and then just choose the best one from all of the potential answers so because it's randomized and because we don't have to guarantee that we're going to give the right answer 100% of the time it's a lot faster and it's a lot more efficient than the max-flow min-cut algorithm so if it's if you have a use case where you can afford to have just a small probability of a wrong answer Carter's algorithm is going to give you big improvements so let's see how Carter's algorithm actually works so it curves algorithm it depends on some operation which is called contraction so what contraction is it's between two nodes so all right between to our contraction is the contraction of an edge technically it's not between two nodes it's the contraction of an edge so what it means when you contract an edge is that you pull together the two vertices on either side of the edge so essentially just go through an example of contraction so say I have some graph let's just you four notes so say I have this graph to contract an edge means to bring together the two nodes on either side of it and merge them into one node keeping all the connections is the same so that's a lot of words but let's let's go over any was that one second I want to contract this edge so what I'm gonna do is I'm gonna take this node right here I'm gonna take this node right here and I can combine them into just one vertex so that will look like this so all the other non non contract none of the edges that are involved in the Kanna contraction and none of the vertices that are involved there none of those are gonna move so these two are gonna be the ones that I'm joining so I'm gonna join those two nodes into a single node and I'm gonna keep all the connection is the same so you'll see I have a connection from here to here and I have a connection from here to here now so those correspond let me let me use a different color for this this guy is the exact same as this guy these edges are the exact same all I did was bring it over into this new contracted model and also we still have our old edge there because it wasn't contracted at all so the operation of contraction runs on a given edge and pulls in all of the the edges that used to point to either of the two nodes on the side of the edge that was contracted keep in mind if you had multiple nodes for example I know going from here to here as well then that would also get brought over as another edge between these two nodes so with this contraction operation we tend to get multigraphs so a multi graph is just a name for a graph they can have multiple edges between any two vertices so as you can if we incorporate that here that's what we did and it's important to keep track of these these multiple edges because when we're returning the min cut from cargos algorithm we need to know what the original edges that we were going to cut so even if these get contracted in our modified version we still need to know that hey we're actually going to cut this one and this one in our original graph so that's the operation of contraction so now that we know what that does let's go through Carver's algorithm and this is actually a really it's it's a pretty simple algorithm so here's what we did so for starters we need some graph so a graph has its vertices of P and its edges eat so what we do here is we say we loop over all of our edges and we say well the number of vertices we have is greater than to pick an edge let's call it e in this example pick an edge that's a terribly let me try another one pick an edge E that's beautiful deep from our set of edges which is this back here just all the edges in our graph at random so just pick a random edge from your graph and then after that contractee so that's just the operation that we went through up here to where we smush the edge and any edges with it and bring the two vertices that it connects into one new vertex then that's all we do in here so we keep doing that over and over and over again until we have only two vertices left and when that happens returned the only cut left so when we have two vertices we're only gonna have one cut remaining so you can this kind of make sense if we continued our example up here you can see after this let's say I did another contraction let's say I want to contract this edge this time retract that guy so I'm gonna bring this guy's gonna be the same but my top two nodes join into one so this guy just gets smooshed but this node right here gets kind of redirected and connects to the new merged node so at the end of that operation now I'll have a multi graph which connects two nodes with three edges and then in Carter's algorithm I have two vertices left so I'm just done this is the cut that I'm gonna be returning so you may be noticing though this wasn't actually the optimal cut for this graph this has three edges but I can see just right here if I instead had cut this edge and this edge then I could have had this and this is a sub graph so that's kind of the randomized aspect of cargas algorithm it doesn't work a hundred percent of the time the main benefit is just that it's fast so what you'll see most of the time when you're running this algorithm is you'll do multiple runs of this I'll do maybe one two three four five and each of these will start with the same graph so now you get the picture each of these will start with the same graph and do their own version of randomized contraction so this guy might contract this note for example whereas this one might contract this note and that will give you two different second-level graphs so what happens when you contract this node you get two nodes right there one node right there what happens on this guy you get kind of a similar thing just just in a different order so you can see already these are really different graphs like these the cuts here are not going to end up to be the same so eventually each of these each of these five runs is gonna give you some cut each one is gonna be at a different length so let's say this guy gives you size equals three this has the cut this guy gives you size equals two let's say this guy because your size you goes for I'm not sure that's possible with this graph but let's just say that happen this guy gives you size equals three this guy gives you size equal to so what you do with CarGurus algorithm is you run it a bunch of times just because it's so much faster than the max flow min cut algorithm and you're just picked the best cut so here I could pick this one pick this one either of those is gonna be what Carter's algorithm tells me is my min cut and so that's kind of the beauty of this algorithm is that you can manipulate it by running more time more trials or some things that we'll talk about in future videos but it's just it's just a good way to get a really high confidence but not a hundred percent confidence guess for what the min cut forgiving graph is

Channel: Paul Learns Things

Views: 14,303

Keywords: karger's, algorithms, randomized algorithms, min-cut

Id: KqMGeNZuwfI

Length: 13min 26sec (806 seconds)

Published: Sat Jan 07 2017