It is also possible that on any legally-sized starcraft map the number of nodes in the graph would be so small that the solution would be trivial.

But at the same time it's fascinating that they were able to embed this sub-problem within a starcraft scenario, such that any optimal player would have to solve this NP-hard problem. This sort of argument is a classic in the field, and always fun to read.