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.

$\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
    Jan 5 at 20:01
  • $\begingroup$ @nirshahar Are you trolling? That's a lot slower than the algorithm from 2017. $\endgroup$ Jan 5 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
    Jan 5 at 21:55
  • $\begingroup$ @nirshahar Poly-space with the least time. $\endgroup$ Jan 6 at 6:37
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.

$\endgroup$

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.