This is going to be a long question. But, I promise, I'll try my best to make this as lucid a read as possible. Also, the first half doesn't even have much maths in it to be honest.
We were analysing a riddle in our Graph Theory class. Chances are high that you've seen this riddle before, but things will soon go deeper.
Puzzle 1: Consider you have a boat with one more seat (apart from you), and you have a goat, a wolf, and a cabbage with you. You are on one side of a river and you want to cross it with the three accessories with you. The only problem is, the wolf will eat the goat, and the goat will eat the cabbage if you are not with them. The question is, how will you take all of the on the other side.
Solution: The solution is quite simple. One can see it here or just use trial and error to find it. A more general way is to use Djikstra's algorithm, but (as you will soon see) I'm not concerned with the shortest path.
Adding a variation: Now, let everything be as above, only that now you have an extra donkey with you who is at the same level in the chain as the goat. In other words, the donkey will eat the cabbage and will be eaten by the wolf. Now, what's the required algorithm?
Solution: (I'll pause so that you can close your eyes if you want to think of it) Well, it's almost obvious that it's no longer possible. You'll run into trouble only in the first iteration.
Modification: You need two extra seats (instead of one) on your boat for a solution to exist.
Question: Looking at the main puzzle and the variation, the question arises- what determines the least number of seats we need in a random general case?
Guess: Now is when Graph Theory kicks in. Consider a graph $G$ whose vertices denote the objects we are carrying with us. Two vertices $v_1$ and $v_2$ are connected if and only if they have a conflict, i.e., either $v_1$ eats $v_2$ or $v_2$ eats $v_1$. So, for the first puzzle, the graph looks like
while for the second one, the graph looks like
So, a reasonable guess is to pick in the first turn, the least number of vertices from this graph such that the remaining vertices do not have any edge between them. In the language of Graph Theory, we basically want to pick the minimum vertex cover in the first step and hence leave the maximal independent set behind. These two will be denoted by $\beta(G)$ and $\alpha (G)$ respectevily.
(Almost) General Puzzle: Now that we have made a guess, let us try using a random graph and see if it works. Here's one such graph
Some nonsensical connections have been made sure, but we're doing maths, not biology.
In this case, it's easy to see that
$$\beta(G)=\{\mathtt{Goat},\mathtt{Rabbit},\mathtt{Goose},\mathtt{Mouse}\}$$
which means required number of seats on boat (apart from you) is
$$|\beta(G)|=4$$
So, the algorithm we need to follow is-
- Take $\beta(G)$ to the other side.
- Return alone.
- Take $\{\mathtt{Carrot},\mathtt{Cabbage},\mathtt{Grass},\mathtt{Wolf}\}$ to the other side.
- Return with $\beta(G)$.
- Keep $\beta(G)$ on the initial side and take $\{\mathtt{Cat}\}$ to the other side.
- Return alone.
- Take $\beta(G)$ to the other side.
Slight Modification: As you may have noticed, there's something more in the last case that helped us. This extra advantage is that our $\beta (G)$ was also independent. That's why, we could perform step 2. Now, let $\beta (G)$ is not independent. What can we do in this case?
Answer: (I'll pause so that you can close your eyes if you want to think of it) Let $I=\alpha(\beta(G))$ be the largest independent set inside $\beta(G)$. Assume $|I|<|\beta(G)|$ or else it's the same case as above. In step 2, instead of returning alone, we will return with $\beta(G)\backslash I$ and keep $I$ on the other side. In general, we will keep $\beta(G)\backslash I$ with us on the boat throughout.
So, it does seem that our guess was correct. But is it?
Counterexample: Consider the following graph
If our guess was right, only one more seat should have been enough since $\beta(G)=\{\mathtt{Wolf}\}$. But, it's easy to see that it's not- you run into trouble in step 5. So, we need $\left(|\beta (G)|+1\right)$ seats to have a solution (like last time, the wolf stays on the boat).
Now, we return back to
Question: Is there any other case where even $\left(|\beta (G)|+1\right)$ seats are not enough to guarantee a solution? If yes, generate such a solution. If no, find the most general cases where we need $\left(|\beta (G)|+1\right)$ seats, and those where only $|\beta(G)|$ seats are enough.
My conjectured solution: I can't construct a proof, but I would guess that $\left(|\beta (G)|+1\right)$ seats are enough irrespective of the case. Also, if we let $n=|\beta (G)|$ if $\beta (G)$ is independent, and $n=|\beta(G)|-|\alpha(\beta(G))|$ otherwise, then we need $\left(|\beta (G)|+1\right)$ seats if and only if $|\alpha(G)|>2n$. Otherwise, only $|\beta(G)|$ seats will be enough.
Even if my solution is correct, please provide a proof of that.
Edit: I'm a little new to Graph Theory, and I messed up the $\alpha (G)$ and $\beta (G)$ notations. They are usually used to denote the cardinalities of the minimal vertex cover or the maximal independent set. But, I used them in this question to denote the graph induced by them. As Misha Lavrov pointed out, there can be more than one minimal vertex cover, and so it's not okay to use the $\alpha$ or $\beta$ notations in that manner. But, I guess, the abuse of notations never really created any problems in this question since the main solution was written using $|\alpha (G)|$ and $|\beta (G)|$; and in the rest of the question, it was quite clear which set was being referred to as there was no other set to confuse it with.
Best Answer
If we have $\beta(G)+1$ seats available (apart from the one you sit in), then the following algorithm always works: first, load a vertex cover of order $\beta(G)$ onto the boat, and keep them on the boat for the rest of the solution. This leaves one free seat, which we can use to transport all the remaining animals, one at a time.
Since the remaining animals form an independent set, nothing can go wrong. When they've all crossed the river, the animals you've been keeping on the boat get off, too - and you're done.
The following algorithm often works with just $\beta(G)$ seats available. Let $C$ be a minimum vertex cover of $G$, and let $D$ be a minimum vertex cover of $G[C]$. Then:
This lets us take up to $2\beta(G)-|D|$ animals outside $C$ across, a slight refinement of your solution when $C$ is not independent.
Note that there could be several minimum vertex covers, and in that case, we should pick one to minimize $|D|$. For example, suppose we're transporting a tiger, a wolf, a cabbage, and a goat; the tiger would eat the wolf but is friends with the goat. Then $\{\text{tiger}, \text{goat}\}$ and $\{\text{wolf}, \text{goat}\}$ are both minimum vertex covers, but the first one has $|D|=0$ while the second has $|D|=1$. (Though in this case, both vertex covers would work, because there aren't enough other animals to care.)
However, there are also cases where we're fine with $\beta(G)$ seats even when there are many more vertices than this. For example, suppose that we have $n$ free seats in the boat, and:
This is far worse than our bounds above, but we can still do it. First, bring all $n$ goats across. Then, for $i=1,\dots,n$, bring the $i^{\text{th}}$ goat back and bring all $n$ cabbages from the $i^{\text{th}}$ goat's planet across. When we've done that, all cabbages are across, so finish by bringing all $n$ goats across again.