Thank you for letting me know about the Cuckoo Cycle algorithm. I remember hearing it once, but never did a deeper digging on how it works. Will definitely now.

After some research I have concluded that the original TSP does not fit as PoW since verifying the solutions requires NP time.

However, in a modified version of TSP where we try to find a route < GIVEN_LENGTH the solution verification can be done in P time.