A problem described can be related to Knapsack or The Travalling Salesman Problem--correctly described as NP-hard or NP-complete--but it can still be solved in real time using Perl when the CS majors give up. I've done this many times.
The thing about NP complete problems is that they don't scale. It could be you can still find solutions for, for example, 20 nodes, while for just a few more nodes, solving the same problem takes many times longer, so long that it's no longer practically usable. Your particular problem may take a few minutes to solve, while the slighhtly more complex problem takes hours, or days.