1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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. :-) $\endgroup$ – David Richerby Dec 17 '14 at 0:52
  • $\begingroup$ 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 $\endgroup$ – badroit Dec 17 '14 at 14:04
2
$\begingroup$

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 $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$.

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.

$\endgroup$
  • $\begingroup$ Okay, so what I understand then is that the run-time of the/an algorithm depends on that parameter. This could be put in contrast with other parameters that when bounded, do not affect the complexity. $\endgroup$ – badroit Dec 17 '14 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.