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.
which raises the question - what is a game? is it the collection of all possible permutations of states allowed by the rules, as in the Pac-Man generalization or this extremely weird corner case SC scenario that requires extended amounts of sub-optimal play? If I -can- construct such a bizarre and entrenched StarCraft position, is it part of "the game", or is it a weird theoretical custom map whose sole purpose is proving starcraft is np-hard to "solve"