The significance of bounded parameters in complexity A lot of complexity results are given with respect to bounded cases where results are more favourable. 

For example, the graph isomorphism problem — which is GI-complete in general — is known to be tractable in cases where degree is bounded.

But every time I see such a result, I have a nagging voice in my head telling me that for any input graph the degree must be bounded. I find it hard to intuitively resolve the resulting cognitive dissonance.

I understand that bounding a parameter allows for considering it as a constant rather than a variable in the complexity analysis. But that seems almost like a semantic game since you can still define the bound to be arbitrarily large so long as it's fixed.

Perhaps the message to be gleaned from these bounded results is that if you assume the parameter in question to generally be small, the worst case is more favourable. But this seems rather vague to me since one can define "small" arbitrarily.

The nagging voice tells me I'm still missing something ... that something hasn't clicked.



To distil a question out of this: when one sees such a bounded-parameter result, what should one intuitively conclude about the problem in practice with respect to that parameter? 

What is the importance of such a result?
When you see that a parameter is bounded, you shouldn't think of the value of the parameter of a single graph, but of a class of all graphs that satisfy the bound on the parameter.

So, to say that graph isomorphism is in polynomial time for bounded degree graphs really means that, for every $d$, there is a polynomial time algorithm&nbsp;$A_d$ that decides graph isomorphism on the class of all graphs of degree at most&nbsp;$d$.  However, the running time of&nbsp;$A_d$ depends on&nbsp;$d$.

And, yes, the take-home is generally that there are decent algorithms as long as the parameter is small. What counts as decent will depend on your circumstances: what sorts of inputs you need to deal with and how much computing time you have available.