The problem with Karger's algorithm isn't that it's randomized, but that even the expected runtime is orders of magnitude worse than this new deterministic algorithm.

For that reason I wouldn't call it amazing though it is an interesting algorithm.