[bitL]

It's like you have some problems in graph theory that are NP-Complete/Hard, so in theory you are out of luck. But if you restrict yourself to a certain type of graphs, or you change your problem from e.g. computing a chromatic number on a certain type of graphs to instead decide if for a given K such K-coloring exists, suddenly there is a polynomial algorithm. And practically-wise, you might be fine with just K={2,3,4,5} and couldn't care less about other values of K for your practical case; so while in general you can't solve it, in practice you have a fast algorithm you run 4x in a row and are done.