1
$\begingroup$

The fastest algorithm I could find that finds the chromatic number of an undirected simple graph exactly in only polynomial-space is "Faster Graph Coloring in Polynomial Space" by Gaspers and Lee (DOI: 10.1007/978-3-319-62389-4_31). It's running time is $O(2.2356^n)$.

However that's from 2016/2017, so I'm wondering whether there are any new relevant developments.

The mentioned algorithm is based on a procedure for counting the number of independent sets of a graph, meaning that new developments in that area are possibly relevant, too.

Improve this question
$\endgroup$
4
  • $\begingroup$ for a polynomial space (as in the title of the question), just enumerate all different coloring options until you find a correct one. $\endgroup$
    – nir shahar
    Commented Jan 5, 2022 at 20:01
  • $\begingroup$ @nirshahar Are you trolling? That's a lot slower than the algorithm from 2017. $\endgroup$
    – user2373145
    Commented Jan 5, 2022 at 20:03
  • $\begingroup$ Sorry, I might have misunderstood your question. Do you ask for an algorithm with the least space used? Or poly-space with the least time? $\endgroup$
    – nir shahar
    Commented Jan 5, 2022 at 21:55
  • $\begingroup$ @nirshahar Poly-space with the least time. $\endgroup$
    – user2373145
    Commented Jan 6, 2022 at 6:37

1 Answer 1

Reset to default
1
$\begingroup$

The way to tell whether there are any new developments is to look up that paper on Google Scholar, find all newer papers that cite it, and check each to see whether it reports a better result. Anyone who has an improvement will surely cite that paper.

Improve this answer
$\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.