# 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?

• "the graph isomorphism problem — which is GI-complete in general" Given that GI is, by definition, the class of problems that are reducible to the graph isomorphism problem, that's not saying a whole lot. :-) – David Richerby Dec 17 '14 at 0:52
• Heh, well I guess the point was that in the general case it's not known to be tractable, but yes I know what you mean. :P – badroit Dec 17 '14 at 14:04

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 $A_d$ that decides graph isomorphism on the class of all graphs of degree at most $d$. However, the running time of $A_d$ depends on $d$.