Graph coloring is deceptively simple. The idea of coloring a graph is very straightforward, and it seems as if it should be relatively straightforward to find a coloring. It turns out to not be – in fact, it’s extremely difficult. A simple algorithm for graph coloring is easy to describe, but potentially extremely expensive to run.
In 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.)
[np]: http://scienceblogs.com/goodmath/2007/01/basic_complexity_classes_p_and_1.php
In 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
techniques, 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.
For an idea of what I mean by heuristics, here’s one very simple algorithm:
Given G=(V,E):
Compute Degree(v) for all v in V.
Set uncolored = V sorted in decreasing order of Degree(v).
set currentColor = 0.
while there are uncolored nodes:
set A=first element of uncolored
remove A from uncolored
set Color(A) = currentColor
set coloredWithCurrent = {A}
for each v in uncolored:
if v is not adjacent to anything in coloredWithCurrent:
set Color(v)=currentColor.
add v to currentColor.
remove v from uncolored.
end if
end for
currentColor = currentColor + 1.
end while
This is, implicitly, trying out every possible combination of colors: you can read
“for each v∈uncolored:” as “try assigning the current color to v, and see if it gives
an invalid coloring”. But by stopping the instant it tries to assign an invalid coloring,
it can prune that coloring out without completing it. That’s one of its tricks for
being fast on average: quickly eliminating invalid colorings.
The other trick in this algorithm is a heuristic: *on average*, searching for colorings
starting with the highest degree uncolored nodes will find an optimal result faster than
assigning colorings to nodes in random order. In the average case, this will perform
well – and run in less that exponential time. But there are definitely graphs where this
heuristic fails, and this algorithm will be a disaster.
The fortunate thing is that many of the most common applications of graph coloring
are running on relatively small graphs, and often, the coloring doesn’t really need to be optimal – just *close*.
For example, one of the uses of graph coloring that I’m particularly familiar with is in
compilers. In a compiler, one of the tricks to make code run faster is to store values in
CPU 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.
Greg 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
used, 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.
Register 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.
[chaitin]: http://en.wikipedia.org/wiki/Register_allocation
One comment on that last point.
Ideally, you’d like to store all variables in registers except those which are too big or for which you need to take the address of where it is (registers, obviously, don’t have an address). And even for those variables for which that’s not true, you’d often like to hold temporary copies of data in registers for some part of the subroutine. This last point does increase the amount of data that you’d like to hold in registers. Any variables that you’d like to store in registers but can’t need to be spilled, either to temporary storage on the machine stack, or back to where they came from if they’re a temporary copy.
However, the most common general-purpose CPUs out there are based on the IA32 ISA (e.g. the Pentium) which, to a first approximation, has almost no free registers. It has few to begin with, and the few it has often have special-purpose jobs to do as well as being general storage locations. On such a CPU, “spilling” is actually a more important problem to solve than allocation.
So one piece of modern thinking for the IA32 is actually to decide what should be in registers at what locations first, in such a way that the register graph is always k-colourable at each instruction. Then, register allocation is almost trivial, though you may need to shuffle storage locations occasionally.
(It helps that the IA32 ISA has an extremely cheap register-to-register exchange operation, which is implemented internally as a register renaming. It means that the “shuffle” is cheap.)
The spilling problem, by the way, is quite elegantly expressed as an integer linear programming problem. It’s a big one, though, and ILP is also NP-hard.
Graph colouring is also used in spilling algorithms to work out where to spill to. When not all variables fit in registers, it pays to fit as many of the spilled variables as you can in the same cache line.
If you have a given coloring of a graph, say with 2 colors, it would be easy enough to transform that to a 3 color graph, by splitting one of the 2 colors into two new colors. But is there anything similar in reverse? I mean to say, given a specific coloring of a graph, does that in any way facilitate generating a new coloring with fewer colors?
> 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.
These days it’s actually about 3 from L1 cache, 10 to from L2 cache, and 100-1000+ from memory. So it’s very important to have a good register allocator.
…which is why it’s too bad gcc’s is absolutely terrible. For some reason all of the projects to replace it fail.
For a deeper (nonelementary!) abstract look at graph colorings over at the n-Category cafe:
http://golem.ph.utexas.edu/category/2007/06/colorings_of_graphs.html
The link you gave for P and NP has you saying that graph coloring is NP-complete, which I think is true.
NP-complete is a subset of NP-hard, so it’s still true that it would be NP-hard. The definition of NP-hard is, I think, also correct, but the way you’ve stuck them together comes out wrong.
It’s a question of what exactly you define the graph-coloring problem to be. The problem “What is a coloring of this graph using at most n colors?” is NP-complete. The problem “What’s an optimal coloring of this graph?” is certainly NP-hard, but appears to dip a little into co-NP.
Mark, will you be discussing coloring of *planar* graphs in a separate post, or should we comment on it here?
@Antendren
Ah, that makes sense. (After some Googling. I’m not as up on this stuff as I should be.)
I’m not sure I completely get how you’d show that optimal coloring is co-NP. From the description of co-NP, I’d guess that you’d show it takes polynomial time to confirm that a graph is colored with fewer than a given number of colors (so the given number isn’t the minimum).
Is that right?
Well, I’m not actually claiming that it’s co-NP. There’s an entire hierarchy of levels beyond NP and co-NP that will all collapse to P if P=NP.
To answer “Is n the fewest number of colors needed?” I need to answer two questions: “Can it be colored in n colors?” and “Can it be colored in n-1 colors?”. I’m looking for a “yes” to the first and a “no” to the second. Both of these questions are in NP, but since I’m looking for a negative answer to the second, that means I’m actually working in co-NP there.
So it uses a bit of both, and consequently is in neither. That’s what I meant by dipping into co-NP.
I have developed a exact conceptual algorithm of linear complexity for graph coloring. If there one who seriosly interestd in this, I can share my work with him.
=Sirzat KAHRAMANLI/TURKEY
I think you forgot to add v to coloredWithCurrent in the innermost if
I am a college student(11th standard) from india.My professor told that there is no algorithm for graph coloring so I worked on that for fun and last night i found one process for graph coloring .surprisingly that process is similar to the process mentioned above (Its true).I am really excited to see this here.