\nIn terms of computational complexity – the measure that we computer scientists use to describe how hard it is to compute a solution to a problem – it’s actually NP-hard. What that means that there is no known algorithm for optimal graph coloring which isn’t exponential; and that further, if there *were* a non-exponential algorithm for it, there would be a non-exponential solution for *all* NP-complete problems, but a non-exponential solution to another NP-complete problem wouldn’t necessarily produce a non-exponential time solution for graph coloring! (See [here][np] for some explanation of what this P and NP stuff is all about.)
\n[np]: http:\/\/scienceblogs.com\/goodmath\/2007\/01\/basic_complexity_classes_p_and_1.php
\nIn fact, the *only* general solution to finding an optimal graph coloring is exhaustive search: start with one node, give it a color, assign non-conflicting colors to its neighbors, and so on. Try it with two colors, if you get no result, then try with three, and so on. There are a lot of fancy algorithms that try to improve on that – both by reducing the search space, and by using heuristics. With a combination of those two
\ntechniques, we can get colorings to be quite efficient in the average case – but if always want the optimal coloring of *any* graph, then there’s no way (or at least, no way that anyone knows about) to always get the optimal result quickly.
\nFor an idea of what I mean by heuristics, here’s one very simple algorithm:
\nGiven G=(V,E):
\nCompute Degree(v) for all v in V.
\nSet uncolored = V sorted in decreasing order of Degree(v).
\nset currentColor = 0.
\nwhile there are uncolored nodes:
\nset A=first element of uncolored
\nremove A from uncolored
\nset Color(A) = currentColor
\nset coloredWithCurrent = {A}
\nfor each v in uncolored:
\nif v is not adjacent to anything in coloredWithCurrent:
\nset Color(v)=currentColor.
\nadd v to currentColor.
\nremove v from uncolored.
\nend if
\nend for
\ncurrentColor = currentColor + 1.
\nend while
\nThis is, implicitly, trying out every possible combination of colors: you can read
\n“for each v∈uncolored:” as “try assigning the current color to v, and see if it gives
\nan invalid coloring”. But by stopping the instant it tries to assign an invalid coloring,
\nit can prune that coloring out without completing it. That’s one of its tricks for
\nbeing fast on average: quickly eliminating invalid colorings.
\nThe other trick in this algorithm is a heuristic: *on average*, searching for colorings
\nstarting with the highest degree uncolored nodes will find an optimal result faster than
\nassigning colorings to nodes in random order. In the average case, this will perform
\nwell – and run in less that exponential time. But there are definitely graphs where this
\nheuristic fails, and this algorithm will be a disaster.
\nThe fortunate thing is that many of the most common applications of graph coloring
\nare running on relatively small graphs, and often, the coloring doesn’t really need to be optimal – just *close*.
\nFor example, one of the uses of graph coloring that I’m particularly familiar with is in
\ncompilers. In a compiler, one of the tricks to make code run faster is to store values in
\nCPU registers that are part of the CPU itself, rather than in memory which is out on the motherboard. Things stored in registers can be manipulated dramatically faster than things in memory: for example, on the Core Due processor in my MacBook, it takes 10 clock cycles to retrieve a single value from memory into the processor cache; it takes 2 cycles to get memory from the cache into the CPU. Values in a register can be accessed with *no* wait. So naturally, it makes a big difference in the performance of a program which values wind up in registers, and which don’t.
\n
![\"register.jpg\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_167.jpg?resize=226%2C309\")
\nGreg Chaitin (the same Chaitin of information theory), along with several other people at IBM research, [figured out that deciding how to allocate registers to variables in a program was really a graph coloring problem.][chaitin] If you lay out the program on a page, and draw a line from the *first* time a variable is given a value until the *last* time that variable is
\nused, that line is called the *lifetime* of the variable. Now, do that for all of the variables. And then build a graph: every variable in the graph is a vertex, and there’s an edge between two variables if and only if their lifetimes overlap. (The diagram to the right illustrates this: the vertical bars are the lifetimes of the different variables; beneath is the graph inferred from overlapping lifetimes.) Then, you color the graph – with each color corresponding to a register. If you can color the entire graph with no more colors than there are registers, then you can just keep everything in registers. Otherwise, you need to figure out what variables to cut from the graph in order to produce a colorable graph; each time you cut a variable from the graph, you’re saying that it’s going to stay in memory, rather than in a register.
\nRegister allocation is typically done over relatively small regions of code – subroutines, rather than entire programs. Within a subroutine, you rarely see code with more than a couple of dozen variables that you’d like to store in registers – which means that you’re rarely going to try to do coloring of a graph with more that a couple of dozen nodes – and even then, if you use a *nearly* optimal coloring rather than a truly optimal one, you’ll be making the program a bit slower, but not causing it to generate incorrect results.
\n[chaitin]: http:\/\/en.wikipedia.org\/wiki\/Register_allocation<\/p>\n","protected":false},"excerpt":{"rendered":"