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.

  • $\begingroup$ Why do you think knowing the chromatic number helps? How fast is "brute-force"? $\endgroup$
    – Pål GD
    Jan 6 at 20:01
  • $\begingroup$ @PålGD Regarding your first question, I don't know (except in the brute force case). I arrived at this question because after looking up a few fast exponential algorithms for "coloring" I realized that they all actually compute the chromatic number, and it's not obvious to me whether it's possible to reconstruct the optimal coloring from their data structures after the chromatic number is found. $\endgroup$ Jan 6 at 20:46
  • $\begingroup$ @PålGD Regarding the second question, I think there are two possible brute-force approaches, I think that one is O(n!*n) (greedy coloring on all possible node orderings), the other one is O(k^n). Here n is the number of nodes and k is the number of colors. $\endgroup$ Jan 6 at 20:48
  • $\begingroup$ There is actually a $2.461^n$ algorithm to compute the chromatic number of a graph using polynomial space. $\endgroup$
    – Pål GD
    Jan 6 at 21:15
  • 1
    $\begingroup$ No, you have an oracle that runs in $2.461^n$ time and polynomial space. Can you use that to get the colouring in the same time? Check again the answer by Y Filmus. $\endgroup$
    – Pål GD
    Jan 7 at 8:35

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.