Graph Colouring

Well, once again it is time for yet another issue of “Intractable Problems”. In this issue I would like to examine just how difficult it is to colour something. Now, I know that many of us did finger-painting as children, and we probably coloured our hands, feet, faces, and other areas of ourselves which, I suspect, even our mothers blush to talk about. So, what can be so difficult about colouring?

Well, random colouring such as children might do is not too difficult. But, if we are asked to colour something in a particular way, then this can be a very difficult problem to solve.

Consider, for example, a graph. A graph is a set of points with lines between the points. We are asked to colour the graph such that every line has a different colour at each end. The problem is that my crayon box has only a few colours. The question is: Can I colour the graph?


The graph shown here requires at least four colours to colour it. It can’t be coloured if crayon number 4, my yellow crayon, is broken. If you don’t believe me, then try and colour this graph using only three colours.

It is computationally intractable to determine if a graph can be coloured with fewer colours than the number of points in the graph.[1] This means that if the graph is sufficiently large, then there is a computational barrier that stops us from finding a valid colouring of the graph. The computational difficulty grows exponentially with graph size. This type of problem is similar to our trying to count the correct number of grains of sand on the beach. An impossibility, in anyone’s lifetime!

We can use computational intractability to our advantage, especially if we want to build secure systems. The idea is that we all generate our own three-colourable graph of sufficient size. This is easy to do and it does not take very much time. We then use this graph as our identification. To access something, we show our graph and prove our ownership of it by demonstrating, to whatever level is necessary to prove beyond any reasonable doubt, that we know how to properly colour it.

It doesn’t matter if someone else gets our graph because no one else can figure out how to three-colour it. It can’t be done in their lifetime, not even with the fastest conceivable computers to help them. They will always fail any non-trivial colouring test. This is similar to a public key cryptography system. In this system the user identifier, or graph, can be public. The colouring key must be kept secret and, unlike an ordinary password, does not need not be known by the system being accessed.

So, for those of you who, like me, get quite annoyed with computer systems that force us to change our passwords all the time, simply because these systems are susceptible to a security breach, have faith. There are other ways to protect our identity.  All we need do is convince those who build and run systems to do things for us, instead of the machine. Our task will be to memorize the proper colouring of a sufficiently large graph which, of course, is a completely different problem!

Next issue, I will continue to examine problems with computers. How many of you have difficulty getting what you want from the computer?





Footnotes

1. Karp, R. M. “Reducibility among combinatorial problems” in R. E. Miller and J. W. Thatcher, Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103.