simont | Four-colouring (somewhat belated)

Occasionally something diary-worthy happens to me which never quite gets written down in here, because it happened so gradually that there was no point at which I could look back and decide it was obviously over and hence able to be written about coherently. Earlier this week, a conversation at post-pizza reminded me of just such an incident from the year before last, so I'll write it up now on the basis that it's better late than never.

In mid-2005 my puzzle collection acquired a game called Map, in which you are given a map with a partially specified four-colouring, and your task is to reconstruct the full four-colouring (of which there is one unique one which satisfies the provided clues). In order to automatically generate such puzzles, my plan was to create a map, four-colour it, and then gradually un-colour regions in order to create a puzzle of the desired difficulty. Step two of that, of course, needs an algorithm which four-colours a map.

The simplest algorithm that does the job is a recursive one. Given a map, pick an uncoloured region, iterate through all the colours for that region which don't already conflict with something else, and for each possibility recurse into the remaining regions, stopping as soon as an answer appears. You can speed this up hugely by choosing, at every stage of the recursion, the currently most constrained region to iterate over next; this prunes the search tree early and often, and although the worst-case performance is still exponential in theory, this technique turns out to be able to handle puzzle-grade maps without becoming unreasonably slow.

But I've never been a fan of algorithms which have a hideous worst case but are OK in practice. So during my initial research for this puzzle, I googled around to see if I could find a four-colouring algorithm with a more sensible time complexity, and was pleasantly surprised to turn up one that claimed to run in O(N^2) time.

The algorithm was a by-product of a proof of the four-colour theorem. Apparently the original 1977 proof had included an O(N^4) algorithm, but more recently a bunch of four mathematicians re-proved the theorem using fewer special cases and more verifiable computation, and as a side effect managed to improve the associated algorithm to be quadratic rather than quartic. Unfortunately, this meant the algorithm was also described in terms of high-powered graph theory some way beyond my fluency, so the paper didn't really give me enough details to implement it.

So I mailed one of the authors of the paper and asked if he could clarify some details for me. He replied, in what felt like a rather patronising tone, that he didn't think his algorithm would be much use to me because it was hard to implement.

Well, I'm not scared by that. I'm pretty good at implementing strange algorithms, even algorithms which I've been warned not to try because they're too hard. For example, when I was doing my DipCS, the Algorithms lecturer warned an entire roomful of Cambridge students that they should on no account attempt to implement a B-tree library, because they would be picking bugs out of it until Judgment Day and it would never become stable enough to be useful; since then I've ignored that advice two and a half times with no obvious ill effects, and one of the resulting B-tree libraries has been extensively used in PuTTY for many years now and has contributed virtually nothing to the rate of bug reports. It was indeed fiddly and did take some very careful and thorough testing, but I did it. So while his warning was probably not an unreasonable thing to say to a completely random person who'd just emailed him announcing an intent to implement his algorithm, I decided that if anyone could have a decent go at the job regardless then I could.

So I persisted, and we discussed the details of the algorithm, and gradually – so gradually that I never got round to writing this post about it – it became clear to me that despite my self-confidence he had in fact been right.

A basic sketch of the proof of the four-colour theorem goes like this:

Here is a ginormous appendix listing about six hundred small fragments of graphs.
Given any planar graph (which has had some simple preprocessing done on it), you can guaranteeably find one of those fragments somewhere in it. Proof by exhaustive computer search.
Given a graph which contains one of those fragments, you can reduce it to a slightly smaller graph, in such a way that if you are then presented with a four-colouring of the reduced graph you can transform it back into a four-colouring of the original graph. Details of exactly how to do this for each of the 600 fragments are given in the ginormous appendix.
All sufficiently small planar graphs can be four-coloured, simply by virtue of having at most four vertices.
Hence, essentially by an induction-like argument, any planar graph can be four-coloured.

The four-colouring algorithm precisely follows the structure of the proof: given a (preprocessed) graph, we search for one of the 600 fragments in it, which we turn out to be able to do in linear time by applying cleverness. We then construct our reduced graph (still in linear time), recurse to four-colour that, and (in linear time) transform the four-colouring of the reduced graph into one for the original graph. Since each recursive step takes O(N) time internally, and each recursive step removes at least one vertex from the graph so that there can be at most N recursive steps in total, this leads to a quadratic-time algorithm, as promised.

Unfortunately, this also leads to some rather undesirable properties of the algorithm:

It has quadratic space cost as well as quadratic time. Each recursive step has to construct a slightly reduced version of its input graph, and as best I could tell it pretty much has to construct it in entirely separate memory rather than subtly modifying the original graph data structures. Quadratic space cost is really hideous; I can't think of any algorithm in common use which has it.
Its linear-time recursive step has an extremely large time constant. It has to search the graph for one of 600-odd small graph fragments, which is going to take 600 times however long it takes to find one fragment. And before that it has to compute a quantity called ‘charge’ for each vertex of the graph, which is done by another nasty graph-pattern-matching step, and which is vital to knowing whether you've found your fragment or not. Meanwhile, even finding one fragment is painfully slow: you have to essentially iterate over all edges of your input graph and ask ‘Suppose this edge of G corresponded to a given edge of my fragment F; can I then match up the rest of the edges and vertices of F without finding a mismatch?’.
Perhaps worst of all, it isn't sensibly testable. The set of 600 fragments has been proved to be sufficient to guarantee that one can be found in any graph, but hasn't been proved to be necessary. The guy I corresponded with, in fact, was of the opinion that it might easily be that only 20-50 of them were actually required; he just hadn't managed to prove it. So you end up with 600 special cases in the algorithm code, but you can't construct a set of test inputs which between them exercise more than a small fraction of those special cases. This is a recipe for unreliability.

Once that lot became clear, I abandoned the idea of implementing the algorithm. I still think my original self-confidence was reasonably justified, in that I could make pretty much as credible an attempt at the job as anyone. It's just that given the first two points above, I think no sensible programmer would want to use such an algorithm in production code even if a working implementation was handed to them on a plate; and given that point three then stands in the way of producing that working implementation in the first place, it's just not a feasible project at all.

So the current version of Map still uses the simple early-pruning recursive algorithm; and the story stands as a cautionary tale with the moral that even if you have my antipathy to cowboy algorithms like Quicksort and hash tables, just occasionally the worst-case asymptotic time complexity of an algorithm can still be a vanishingly small concern compared to other considerations.

Flat | Top-Level Comments Only

Said ginormous appendix is still small compared to the appendix of the original proof!

OTOH my memory of other attempts to prove the theorem suggest to me that as long as your graph doesn't have any vertices which have 5 edges meeting at it then a good algorithm might exist. This stems from the fact it is far easier to prove the 4 colour theorem for all maps without pentagonal countries :).

There exists somewhere in my house a passable (if overly verbose) pop-sci book about the theorem which neatly sets out a) how you can reduce the problem to {2,3,4,5}-agonal countries and b) how {2,3,4}-agonal countries aren't too much of a problem. I believe it is called 'Four colours suffice' or something similar.

Untestable though the algorithm might be, the validity of its result in any given case is trivial to check. This means an option would be to use the O(N²) algorithm and if it broke fall back to the O(e^N) one, giving the option to e-mail the author.

…except that I just bet the constants in the O(N²) are so huge you need to be colouring a much larger map than the ones in your puzzle before they're amortised.

For the avoidance of doubt, when you say that each step has to construct a reduced version of its input graph, I assume the previous version must be retained in its entirety?

I assume the previous version must be retained in its entirety?

As I said in the post, "as best I could tell". I didn't see any way to avoid having to do so, although it's possible that a way might have existed and I failed to spot it.

Ah. Possible misunderstanding.

I noted your saying that a graph couldn't be reduced in situ; I was just wanting confirmation that you can't delete graph_n once you've made graph_n+1, i.e. that you have to retain the entire sequence of graphs in order to reconstruct the colouring once all the reductions have been done.

Incidentally, if — as I suspect — the algorithm works by creating a reducing sequence of graphs then reconstructing a colouring back up the sequence towards the original, you can probably transform the algorithm from O(N²) time O(N²) space into one that's O(N³) time and O(N) space, simply by making sure the reduction sequence is deterministic then replaying it at each step in the reconstruction instead of using retained copies of the graphs.

Well, I think you were right to try, in that you learnt a lot about it. And you probably *could* have gone on to do it, if it had been a reasonable thing to do.

Do you think there could be any short cut solution? Something that in practice works more like the recursive algorithm, but that you can put some really large theoretical limit on by proving it the bad cases are ruled out by the proof??

Or you could implement this algorithm, but for graphs with N smaller than [BIGNUM] reduce to the recursive algorithm, instead. That's linear, and leaving out the quadratic algorithm is a bug that will never show up :)

Or you could release it untested, and check the answer, and if it fails automatically email a submission of the core dump to a maths journal of your choice ;)

Could you solve the creation issue by building graphs in steps which do not violate the property?

Possibly, although I was vaguely worried that doing so might introduce some sort of non-generality in the resulting graphs which might detract from the fun of the puzzle in some obscure way.

I think you're right, it probably would. I don't think I'd have the brain to work it out, but some people certainly would.

Another thing along the same lines would be to try to find a way of dividing a one-region one-coloured graph recursively with recolouring until you were bored. That would be a general approach (as an arbitrary graph could be assembled into such a hierarchy) if you could find out a recolour step, but trying to develop your own analytic algorithm for four-colouring is not something to do in your spare time, ;).

Fwiw, I implemented a four-colouring algorithm for work a couple of years ago and used the obvious recursive approach, but N was small.

recently a bunch of four mathematicians re-proved the theorem

That you need four mathematicians for an efficient proof of the four-colour theorem sounds like a corollary of Conway's Law...

Either that or you need Fred Brooks to explain why eight mathematicians couldn't have proven it in half the time.

Four-colouring (somewhat belated)

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject