<p>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</p>

<p><a href="http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf">http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf</a></p>

<p>which also include open problems; e.g., can one get running time $O(2^n \cdot poly(n))$ as above with polynomial space usage?</p>

<p>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:</p>

<p><a href="http://www.springer.com/us/book/9783642165320">http://www.springer.com/us/book/9783642165320</a></p>

CC BY-SA 3.0
2016-03-07T22:29:26.640Z
2016-03-07T22:38:26.653Z
2016-03-07T22:38:26.653Z
Andy Drucker
<p>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?</p>

<graph-theory><time-complexity><graph-colouring>
What is the complexity of the fastest method of k-coloring any graph?
user5517534
# What is the complexity of the fastest method of k-coloring any graph?

(Asked by: username_0 on 2016-03-07)

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?

**Tags:** graph-theory, time-complexity, graph-colouring


---

## 1 answers

### Answer by username_1 on 2016-03-07. Score: 10

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

<http://www.wisdom.weizmann.ac.il/~dinuri/courses/11-BoundaryPNP/L01.pdf>

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:

<http://www.springer.com/us/book/9783642165320>


---

