Most problems in this space have reasonable-time approximations that get you close to the right answer for far less computational complexity. Even without ever having looked at Steiner trees before, I guess that there were reasonable approximations, and confirmed that was true without looking too hard. Letting Patterson know about the problem mapping ("your problem is an instance of <X>") is typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments.
(many people say the protein folding problem is NP-complete, but the community generally believes you can predict the folding pathways of all proteins without explicitly running such calculations).