This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
This problem is to create an algorithm on a graph. You might use some ideas from the randomized MST algorithm, but it won't be exactly like that.
Here's the scenario: You have taken a bunch of prisoners and have 2 prison cells to put them in. Some of the prisoners really don't get along with each other, so you'd like as many of them to be in different cells as possible. And you also want to make this decision as quickly as possible because you need to lock them up soon.
Specifically, you have \(n\) prisoners, as well as a list of \(m\) pairs of prisoners that don't get along with each other and should be separated. This is a graph: each prisoner is a node in the graph, and there is an edge between two prisoners if they don't get along. We want to partition the \(n\) nodes of this graph into two groups so that as many edges as possible go between the two groups, and as few edges as possible go within a single group.
Here's a deterministic algorithm to solve this problem: Start out with all the prisoners in the same cell. Then go through the list of prisoners and, for each one, put them in whichever cell has fewer of that prisoner's enemies in it. Then go through the list again and do the same thing, each time moving a prisoner into the other cell if and only if they have fewer enemies in that cell. The algorithm stops when you can't make any more moves.
It can be shown that the algorithm above runs in time \(O(m(n+m))\). This is because, at each iteration, we have to look at all of the enemies of all of the prisoner, which costs \(O(n+m)\), and there are at most \(O(m)\) iterations.
After running the algorithm above, the number of enemy relationships that exist within one cell or another is at most \(\frac{m}{2}\). This is because, for each prisoner, at least half of that prisoner's enemies are in the other cell. Since this is true for every prisoner, the number of edges (enemy relationships) that go between the cells must be at least \(\frac{m}{2}\).
Phew! That's a pretty neat algorithm, but it's also pretty slow and a little complicated to analyze. Come up with a way simpler randomized algorithm that has the same performance in expectation: the number of edges that go between the two cells should be at least \(\frac{m}{2}\), on average. Your randomized algorithm should be faster than \(O(m^2)\) time.