Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring.
If such an algorithm isn't known, please tell me so.
This question is not a duplicate, contrary to what the title may suggest: Using the chromatic number to compute an optimal coloring
This is not a homework question, I just want to write a program finding optimal colorings.
Probably no theoretical algorithm "faster than brute-force" will be as good as using a SAT solver in practice. If you know the chromatic number already, it suffices to solve a single instance of SAT to find the coloring. Moreover, since you know the instance is always satisfiable, you can also try local search solvers such as Sparrow.
The SAT encoding of k-colorability of straightforward. In my experience the obvious encoding works fine for many instances. Of course, there are multiple ways of encoding the problem some of which can work better for certain instances, but it's hard to know without trying them out. A good symmetry breaking technique which will also speed up things nicely is to find a clique (as large as possible - for sparse graphs there are extremely good practical solvers like pmc), forcing it to have distinct colors, and then feeding that instance to the SAT solver.
I helped implement this very approach to the IGraphM Mathematica library and it works quite nicely.
