Map Colouring

Apr 2019

Map colouring is an interesting puzzle where you are looking to assign different colours to different feautures on a map. It was first mentioned in 1852 as a mathamatics problem to determine the minimum number of colors when trying to colour a map of England. It was postulated that 4 colors were the minimum number of colours to fill a map so that no regions sharing a common border had the same colour.

Since then computers have got much quicker and there are many different proof methods for the Four color theorem and was the first major theorem to be proved using a computer in 1976.

When converting the map to a graph, with the features represents as nodes and the borders as connections this becomes a more difficult problem and more useful part of graph theory. It could be used in scheduling problems, register allocation problems and problems such as pattern matching and solving Sudoku puzzles.

Solving

For the second segment of the discrete optimization course you need to colour a map where each neighbouring country is a different colour. The challenge is to find the smallest number of colours to fill in the map. Like the other problems in this course, this is an NP problem.

Name Nodes Colours Number of States Time to Solve*
Small Example 20 3 3,486,784,401 or 10^9 2 seconds
Counties of England 83 4 10^50 10^36 years
Countries of the World 195 4 10^117 10^103 years

*Assuming 2GHz computer, very optimistically checking 1 combination a cycle

Brute force

I would start by trying every single combination and returning the best solution. Computers are great with numbers and I want to be lazy. But looking at the table above there is no way to complete this in a reasonable time.

We need another way

Pick most connected

Instead of trying every combination, lets order the way we select the nodes we colour. Starting from the node which has the most connections, choosing its colour and moving to the next, adding a new colour if neighbouring nodes used all the previous colors. This will run until all the colours are chosen

This is so much faster! It is a greedy algorithm so it doesn’t give us an optimal result, but the speed is important here. When you add a new node, it adds only a small amount of time and is close to linear.

Saturation

This method is very similar to the “most connected” but in this case the next node to select will update each time. When a node is colored the connected nodes are updated with a new saturation number. This saturation number tells how many different colors a node neighbours with. The other name for this algorithm is DSATUR and is a well known algorithm for completing this problem

Continuing

So far it has been interesting on how large NP problems can get and we have to try different algorithms. A good enough solution is much easier to get than a perfect solution. I will continue to write more about this as I go through the class and it looks like there is some possibility of using local search.

Thank you for reading