Hashing is wasteful, but its redeeming quality is that it takes negligible work to validate, despite taking significant work to find values whose hashes have certain characteristics. Just hash the value produced by the worker node and make sure it conforms to the parameters. Should take microseconds.
With proof of useful work, it's probably significantly harder to find similar problem domains where the validation is fast but the useful work is laborious.
Useful cryptographic problems are usually in the intersection of NP and co-NP.
Current best guess is that NP and co-NP are different.
Thus NP complete problems can't be in co-NP, and thus are probably not cryptographically useful. There's a way to make this argument a bit less vague, but it basically explains why cryptographers have stopped looking at NP complete problems.
There was a cryptosystem based on solving knapsack problems. But they had to patch problems until people stopped paying attention.
You can do it by checking that the solution provided is a valid traversal of the graph, and does not touch two vertices twice. If there are N vertices, you can check in O(N) time.
With proof of useful work, it's probably significantly harder to find similar problem domains where the validation is fast but the useful work is laborious.