NP-hard refers to solving the problem in the general case - for a given specific instance it may be possible to find an optimal solution more easily by exploiti

NP-hard refers to solving the problem in the general case - for a given specific instance it may be possible to find an optimal solution more easily by exploiting specific features of the graph (for instance, a series of nodes arranged in a ring would have a trivial optimal solution).