No, I don't believe so. It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal o

No, I don't believe so. It clarifies specifically what problem it is optimal for "We prove that our working-set property is sufficient to guarantee universal optimality, specifically, for the problem of ordering vertices by their distance from the source vertex", but A* only explores a subset of vertices based on the heuristic, so it can be more efficient.