Prisoners and their enemies
Moderators: jestingrabbit, Moderators General, Prelates
Prisoners and their enemies
Each prisoner in a prison has up to three enemies. If two enemies face each other, nothing serious will happen, because the odds of winning in a fight would be even, but if a prisoner faces two or three of his enemies, they'll team up, beat him, and quite possibly kill him.
The guards know about this and they also know the enemies of each prisoner. To avoid fights and riots they want to divide the prisoners in the prison's two blocks in such a way that no prisoner has more than one enemy in his block.
Is this always possible?
PS "Enmity" is always mutual  each prisoner is an enemy to his enemies
The guards know about this and they also know the enemies of each prisoner. To avoid fights and riots they want to divide the prisoners in the prison's two blocks in such a way that no prisoner has more than one enemy in his block.
Is this always possible?
PS "Enmity" is always mutual  each prisoner is an enemy to his enemies
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: Prisoners and their enemies
ahammel wrote:Spoiler:
Spoiler:
Xenomortis wrote:O(n^{2}) takes on new meaning when trying to find pairs of socks in the morning.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prisoners and their enemies
wraith wrote:Each prisoner in a prison has up to three enemies. If two enemies face each other, nothing serious will happen, because the odds of winning in a fight would be even, but if a prisoner faces two or three of his enemies, they'll team up, beat him, and quite possibly kill him.
The guards know about this and they also know the enemies of each prisoner. To avoid fights and riots they want to divide the prisoners in the prison's two blocks in such a way that no prisoner has more than one enemy in his block.
Is this always possible?
PS "Enmity" is always mutual  each prisoner is an enemy to his enemies
Put another way, in a undirected graph where no vertex has a degree greater than 3, is the graph "almost" bipartite.
Spoiler:
Suspect that the answer is "yes you can" but no proof just yet.
eta
Spoiler:
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prisoners and their enemies
What do you mean by this?
jestingrabbit wrote:Spoiler:
Spoiler:
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prisoners and their enemies
Yeah, there are a lot of configurations with each vertex having maximum order. I thought that the tetrahedron was a good example to mention/ruleout.
I'm thinking about ruling out some other sub configurations. For instance, a solution for the second graph in the diagram can be extended to the first in an obvious way.
A more complicated reduction also works for graphs that have a loop of size 3.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prisoners and their enemies
The Petersen graph is not a counterexample, so the result is very likely true. (Curiously, the block assignment for the Petersen graph does not have equal numbers in each block.) However, in general you can't just pick any pair of enemy prisoners, throw them into the same block, and expand from there: there's a counterexample of size six to that idea.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Prisoners and their enemies
Any maximal cut solves the problem...
Zµ«VjÕ«ZµjÖZµ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«VµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZµkVZÕ«ZµjÖZµ«VjÕ«ZµjÖZÕ«VµjÕZ
Re: Prisoners and their enemies
notzeb wrote:Any maximal cut solves the problem...
Here is a max cut on a Petersen graph. Notice the prisoner with two enemies in his block.
 Attachments

 maxcuptpetersen.png (11.37 KiB) Viewed 7010 times
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: Prisoners and their enemies
Actually, never mind. This wasn't a maximum cut.
It really seems that a maximum cut does solve it, but I'm still not sure that ANY maximum cut does.
It really seems that a maximum cut does solve it, but I'm still not sure that ANY maximum cut does.
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: Prisoners and their enemies
Actually I agree with it completely now. Any maximum cut solves it.
Funny. I hadn't thought of that
My solution doesn't use graphs at all.
Funny. I hadn't thought of that
My solution doesn't use graphs at all.
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: Prisoners and their enemies
wraith wrote:Actually, never mind. This wasn't a maximum cut.
It really seems that a maximum cut does solve it, but I'm still not sure that ANY maximum cut does.
Take a maximum cut, and assume for sake of contradiction that it fails the condition given in the problem. Then, there exists some vertex such that at most one of its incident edges crosses the cut. Flip which side of the partition it's on, and now at least two of its incident edges cross the cut, without changing the crossing status of any other edge. So our cut wasn't actually a maximum cut, contradiction.
I'm not terribly versed in graph theory, so things like "maximum cuts" don't spring to my mind immediately, but in retrospect it's an obvious solution. We want to partition the vertices, and we want a lot of edges to cross the partition, so an obvious first guess is the partition that makes the most edges cross.
With a little more work, this also turns into a proof that every such graph is fourcolorable, and a similar argument yields that a graph with max degree at most 5 is sixcolorable, and a graph with max degree at most 7 is eightcolorable (and similarly for several other numbers as well). Is the statement "a graph with max degree at most n is (n+1)colorable" true in general, and is an argument similar to this a proof for it?
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
 Lopsidation
 Posts: 183
 Joined: Tue Oct 27, 2009 11:29 pm UTC
Re: Prisoners and their enemies
Yes, that is true, Cauchy.
Spoiler:
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prisoners and their enemies
wraith wrote:Actually I agree with it completely now. Any maximum cut solves it.
Funny. I hadn't thought of that
My solution doesn't use graphs at all.
What does your solution look like?
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prisoners and their enemies
Lopsidation wrote:Yes, that is true, Cauchy.Spoiler:
Wow, I am *really* rusty, because that's incredibly straightforward.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Re: Prisoners and their enemies
jestingrabbit wrote:wraith wrote:Actually I agree with it completely now. Any maximum cut solves it.
Funny. I hadn't thought of that
My solution doesn't use graphs at all.
What does your solution look like?
Spoiler:
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prisoners and their enemies
Your method has the benefit of being complete after #prisoners time (I think), whereas finding a max cut is probably not doable in poly time (it is doable iff P=NP).
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prisoners and their enemies
jestingrabbit wrote:Your method has the benefit of being complete after #prisoners time (I think), whereas finding a max cut is probably not doable in poly time (it is doable iff P=NP).
Well, for max enmity (every prisoner has three enemies), my method produces a max cut, since only a max cut is a solution in this case (it's not necessarily so if some prisoners have less than three enemies, though).
Is this suddenly a polynomial algorithm for finding max cuts for graphs, where all vertices have a degree of 3?
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Re: Prisoners and their enemies
This is not the case. If the enmity graph is a cube, there are two cuts (up to isomorphism) that satisfy the condition, but only one max cut.
Re: Prisoners and their enemies
The algorithm doesn't necessarily produce a maximum cut. Instead, it produces a sort of maximal cut, maximal in the sense that it cuts more edges than the cuts produced by flipping any one vertex to the other side. It's a local max, but not necessarily a global max.
(∫p^{2})(∫q^{2}) ≥ (∫pq)^{2}
Thanks, skeptical scientist, for knowing symbols and giving them to me.
Thanks, skeptical scientist, for knowing symbols and giving them to me.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Prisoners and their enemies
That said, there might be a polynomial time algorithm for graphs where every vertex has degree less than 3 that finds the max cut, but this isn't it.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Prisoners and their enemies
Cauchy wrote:The algorithm doesn't necessarily produce a maximum cut. Instead, it produces a sort of maximal cut, maximal in the sense that it cuts more edges than the cuts produced by flipping any one vertex to the other side. It's a local max, but not necessarily a global max.
Indeed. My mistake
It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames
Who is online
Users browsing this forum: Google Feedfetcher and 15 guests