Even though I didn't really understood the math, two important points stick out from their description:
- a) Complexity is still n^O(log(n)). This is better than O(e^n) but still worse than O(n^c) for any fixed c.
- b) It is a heuristic and I couldn't find in their paper a statement how well this heuristics work, i.e. in how many cases it will find its (optimal/only) result and in how many not or only in a much more time.
As far as I understood they empirically showed their approach to work on one example. A study showing the general feasibility of the heuristics would be more convincing (yeah, that's the engineer speaking not the mathematician).
It should also be noted that the authors themselves write in their conclusion:
"Compared to existing approaches, and in particular to the line of recent works [15,10], the practical relevance of our algorithm is not clear, and will be explored by further work."
So, before running to conclusions maybe we should wait for the "further work".