I want to tell you about a generalization of a problem that was first popularized by Al Cohen of York, who was an anglo-saxon really smart dude. The problem is: you have a farmer who comes to your river and with him he has a wolf, a bundle of cabbages and a goat; and there's a boat, that's there and it carry-- it can carry him, and one of his charges. Obviously the farmer has to be there because he has to be rowing, and he wants to bring everything to the other shore safely. So that means that he cannot leave the cabbage with the goat, because the goat would be eating the cabbage, and he cannot leave the wolf with the goat because then the wolf would eat the goat. So how can he do it? And so of course we're assuming that the wolf cannot swim which is a question I get all the time, when I'm speaking to kids. So the wolf cannot swim neither can a goat or the cabbage. So the only thing you can do at first is to bring the goat. Okay, so then, okay, the farmer goes back, and he-- takes, let's say, the wolf; but now he cannot leave the wolf with the cat-- with the goat. Otherwise the wolf would eat the goat back. So what if he brown the cabbage instead? Well, same thing if he brings the cabbage now, the goat would eat the cabbage. So the only way it can be done is you have to have this clever moment of saying "Oh, I can bring back the goat". So, okay, he brown the cabbage over and now he brings back the goat, and now takes the wolf, brings it to the other side as well, and now he goes back just to get his goat. So... Then you can generalize, you can say "Well, Let's say that this farmer had more things that he wanted to carry across the river". So let's say that I added a rabbit, so What can I do first? Brady Haran: What does a rabbit day with what? Oh. Brady Haran: Who is in danger from who here? Yeah good question right, so the wolf would eat the rabbit, and... Ah well the rabbit would eat the cabbage. We assume that the rabbit and a goat together are fine. There won't be too much violence there. The boat can hold the farmer and one of these guys. That's it, the farmer still has to be there. We're still assuming also that the revit cannot swim. So what can I bring first? Can I bring the wolf? Well, no obviously the rabbit and the goat would eat the cabbage. Can I bring the rabbit? Well, no again the goat would eat the cabbage, if the wolf doesn't catch the gold first. Okay, can I bring the goat? Well, no, the rabbit will eat the cabbage again, if the wolf doesn't catch the rabbit first. And can I bring the cabbage? No, because the wolf would eat the rabbit and the goat. Brady Haran: Carnage. Carnage, yes. Blood everywhere no matter what we do or shreds of cabbage, one or the other. So the question becomes: Okay, How big of a boat do I need? So if I'm given different things, and I know there's certain conflicts how big does my boat have to be? So here if I have space for my farmer plus two other things, I'll be fine. I could just say fine, I'll bring the wolf and cabbage first I'll leave them on the other side, come back, and get my rabbit and goat and I will be done. Super easy! So the question is how big does it have to be? Well, now we kind of want to start doing math, right? So how do we bring math in there? So we want to think about the conflicts as making a graph. So I have my-- wolf, and I have my goat; and so I cannot leave my wolf with my goat so I'll put an edge, the line, between these two points which are really normally called "vertices". Brady Haran: So edge represents bad news. Yeah conflict, that these two things cannot be left alone unsupervised. The wolf can also not be left with the rabbit. The goat cannot be left with the cabbage and the rabbit cannot be left with the cabbage either. But the wolf can be left with a cabbage so I don't draw an edge there, and I don't draw an edge between my goat and my rabbit because it can be left together. Okay, the point that we see is that let's say that I first took my rabbit, well, there's still some lines remaining, right? I am left with a graph with the wolf, goat and cabbage and there's still some lines that are remaining. And that's tree firing remove any of the corners. So what I want to do is take a set of my things, that will remove all of the lines, and that's actually a really important math concept. It's called a "vertex cover". So, maybe let's write down, what is the vertex cover.
"A vertex cover and a graph G is a set of vertices such that any edge is adjacent to at least one of these services". Okay, so what does that mean? That means that if I want to take a set of points, where every line is touching at least one of these points, my goal is that by taking the vertex cover, I'm removing all the lines so maybe we can just draw a simple example. So, let's say that I have this graph. So, this is a graph so a graph is really just a set of points and set of lines called vertices and edges, and so I might ask myself "What is a vertex cover?" So I could start building one. So I could say "Okay I'll take this vertex within my vertex cover". But that's not enough, right? So these five edges now are covered by this vertex right they're touching... this vertex, but the other ones aren't yet. Now so I could ask "I could add this vertex to my vertex cover, and so I'm getting closer". But I still have this line that is not covered yet. So I could add this one now. And so these three vertices from a vertex cover every single line is adjacent to one of these vertices. Brady Haran: It's almost like how many hands did you need to cover the right number of spots? Yeah exactly, exactly. So here in a vertex cover... What was it? Well, yeah one is not sufficient, right? A single vertex is not a vertex cover. If I cover the rabbit and the goat, then they're covering all of the edges. There's no edges remaining so this forms a vertex cover. So that's why I need to have at least two seats, because the minimum size of a vertex cover in there is 2. So there's no way that I can do it if I don't have at least two extra places besides the place for the-- farmer. So in general I know that my boat has to have at least the minimum size of a vertex cover. Right? Otherwise I won't be able to make my first trip, because there will be some lines remaining in my graph, And lines represent conflict. Brady Haran: I imagine you could do overkill though, there must be as these things get more complicated. There must be-- vertex covers that cover too many vertices. Oh yeah, that's a really good point, right? So in this graph for example-- So if I add this vertex, this is still a vertex cover, right? So, I really want the minimum one. So I want to say that the "number of extra places needed in my boat is at least the size of the minimum vertex cover". So in this graph here that was three. I needed to have at least three-- Brady Haran: Because that final the smallest possible. Yeah, you don't want to overkill as you said. So that's nice, but now you might ask yourself: Will that always be enough? Right? Like-- Sure you can do the first trip across the river, but will you be able to do all of them?
And so now you could check with some examples. So, I mean, we could try with a big example and see if it works out, and then... Try with some other examples. Does that sound good? Okay, so maybe we need another piece of paper. Okay so now we have way more things. And so now we need to think for a second, what is actually going to eat what. And we might disagree on some of these. I am NOT a farm girl So I would go with what I think. The wolf would eat the goose. Potentially, the mouse if it's really hungry. Told eat grass. It... won't eat the cat either, I don't think so. Carrot or cabbage It's not a vegetarian. It's a carnivore so set a goat and the rabbit; and the goose will eat Ahhh... the grass, I see geese eating grass all the time. I don't think it's gonna eat carrot or cabbage because it doesn't really have-- does it have teeth? Does I don't think... I mean certainly if it's not cut up, you know, like it will have trouble it doesn't have hands to-- Brady Haran: Maybe this does not the taste of cabbage. Fine. I think the mouse will eat carrot, and... the cabbage and... the cat will eat the mouse, certainly. The grass will probably be eaten by the goat. I know that you can use them as long Moore's. The rabbit might eat some grass? Cat I think it will just eat the mouse and nothing else will eat it Brady Haran: The rabbits gonna eat the carrot Yes, so the cabbage yeah, that's true. So the rabbit will eat the carrot and the goat will probably eat the carrot too, and the rabbit will also eat the cabbage, and so will the goat, and then the goat and a rabbit are fine. I think that's that looks reasonable to me. Brady Haran: Okay that will be air I guess... Do you agree? Okay, so let's say that I have a river How big it boat we need, and will the minimum vertex cover be enough? The first point I really want to make is that finding the minimum vertex cover is not easy. Right. So, here we only have nine things. right? It's not that much, and to figure out what it is, well since this graph has some meaning, I'm going to use the meaning to help me. So I basically have like my carnivores, my herbivores, and then I have the poor vegetables and herbs. And so these three categories kind of help me determine that oh, maybe the goat rabbit goose and mouse. So my herbivores might form a vertex cover, and I think if I look at it, carefully, like if I were to really look at every single line, so actually yes, the mouse the goose the rabbit and a goat do form a vertex cover It's unclear if that is actually the smallest, I claim it is. It's not an actually such an easy thing to check, so let's just assume that I'm right. So what I'll do is I'll say: Okay for my first trip, I will take my minimum vertex cover. Right? So if I remove my goat, rabbit, boots and mouse; and bring them to the other side. I am left. I removed all of the lines, here, and so, okay, that's fine. So then my farmer will come back. We can only take four things, it will leave a thing behind. Let say it leaves the cat behind And so he brings these guys. But certainly the wolf will attack these guys, and these guys will eat all of the vegetables and grass. So I'll bring them back So it's the same trick as we've seen before. I'll carry my cat over so that it doesn't eat my mouse just itself, right? It's just four places, but you can just bring one thing. That's completely fine. And then I will finally go back, so there's no conflict here. All right this was the original things that I had left at first so no problem there, and then I'll bring my four leftover... herbivores and leave them there. And I'm done! So I succeeded in this case, right? But that's not a proof, right? Maybe... Maybe I wouldn't need more, and certainly We've just seen okay finding your minimum vertex Cover is not necessarily so easy So maybe let's do one other example. So let's say that I had just-- my wolf and-- my-- four herbivores that would get eaten by my wolf. If he has a chance. So my wolf would eat all of these, and none of these would attack each other, right? So I have my river So, I know that I need to have at least... The number of extra places should be at least the size of my minimum vertex cover, which here is easy to calculate. What is it Brady? Do you know? Brady Haran: It's one. It's one... Brady Haran: You should ... the wolf I'm very impressed. Okay, so my wolf is my minimum vertex cover, so I need to bring my well first, right? That's the only thing I can do if I bring anything else. I'll be left with some conflict. So I bring my wolf over. I Come back as I can only take one thing So let's say that I take the mouse. But they all really look the same, like the graph all looks the same for all of them, and these are cold different things, but it could have been called-- you know goat one, goat two, goat three and goat four. Really, so I bring my mouse over So now I have no choice, but to bring the wolf back, right? Otherwise my wolf would eat my mouse So... I bring the wolf back... and then, well, I'm kind of stuck, right? So either I bring one of these guys. But then my wolf would eat the two remaining guys. Or I bring the wolf again, and I keep going like this, and I'm stuck. Okay-- Brady Haran: Minimum vertix cover doesn't work. It doesn't work. It doesn't work. So how much do you need how much bigger does it have to be? And the amazing thing is, you just need one more! at Whatever the graph of conflicts is You will only need at most one more than your minimum vertex cover. And so the way to do it, is very simple You have these conflictual things that, you know, like, like your wolf here. So you just put all these conflictual indivi-- individuals in the boat with you at all times. So you can watch them, and then one by one you carry everything else. So here Okay, my minimum... Brady Haran: So the wolf does every trip? Yeah the wolf is with you the whole time. It does every trip back and forth. So, now let's say that I have the minimum vertex cover plus 1 seat extra, so I have 2 seats plus a farmer's seat. So I'll take my wolf in my mouse first, I'll leave the mouse there, bring back my wolf, take, now my goose with my wall leave my goose. Come back with my wolf. Take my goat in my wolf. But my go there, come back with my wolf, and then carry finally the last 8. And this will work no matter how big your vertex cover is, right? So, no matter how big it is you just keep it with you in your boat, and then one by one you carry everything else. That's pretty amazing, so you know that you need at least a minimum vertex cover, and you need at most the minimum vertex cover plus one to be able to do it. And the amazing thing is that distinguishing between both, knowing one you need one and not the other, is actually really hard. It's NP-hard. So this is a recent result by three Mathematicians: Csobra , Woegunger and Hurkens. And Yes, it's an amazing thing, this small difference of one is hard to determine. Brady Haran: So sometimes minimum vertex cover will do the trick. Yeah, just like in the previous example. Yeah. Sometimes you need to go plus, one and to know which is which, just by looking at the graph. It's hard. So for certain classes of graphs we do know it, but for a general graph, we don't. And it's very hard. Hard problem, actually if you can solve it so you'll not be a millionaire. So you know. Something to try at home. Brady Haran: What's this problem ? So this is the alkene number of the graph? But so it relates because it's NP-hard to determine whether you need a minimum vertex cover our-- the minimum vertex cover plus one, if you were able to come up with a polynomial time algorithm to determine for any graph, what it is. Then you would prove that P is equal to NP. So big problem. This video was brought to you by the Mathematical sciences Research Institute, one of the top places for mathematics in all the world. And whatever you think about the mathematics they do there... they must have the best of you of any maths Institute in the world. San Francisco Bay, Berkeley-- unbelievable. If you'd like to find out more about MSRI, I'll put some links in the description under the video. It's worth a look.
too bad the paper is behind a paywall
How does this problem change if whe also can't bring conflicting thing on the boat with us? Would an upper bound be the maximal vertex cover, that doesn't cover any edge multiple times?