1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Why do you think knowing the chromatic number helps? How fast is "brute-force"? $\endgroup$
    – Pål GD
    Jan 6, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 8:35

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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