I heard brute-force is the only method. Is there any other way? Is there a way to prove that the complexity cannot be exponential?
closed as off-topic by R B, Marzio De Biasi, Mohammad Al-Turkistany, András Salamon, Kaveh Apr 2 '16 at 16:49
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – R B, Marzio De Biasi, Mohammad Al-Turkistany, András Salamon, Kaveh
There are non-obvious improvements over simple brute-force search for $k$-coloring (and for many other NP-hard problems). The obvious approach would take roughly $k^n$ time, but one can do it in time $O(2^n \cdot poly(n))$, and for $k = 3$, one can get $O(1.33^n)$. Algorithms in this area involve simple but interesting applications of dynamic programming and inclusion-exclusion, and for state-of-the-art results can involve intricate case analysis. One good starting point: these lecture notes (with references) by Uri Feige
which also include open problems; e.g., can one get running time $O(2^n \cdot poly(n))$ as above with polynomial space usage?
A broader/deeper introduction to improved exponential-time algorithms for NP problems can be found in the textbook "Exact Exponential Algorithms" by Fomin and Kratsch: