Subgraph isomorphism problem

Question

Subgraph isomorphism problem is an NP-hard problem. However, if the subgraph size is constant (assume $k$), then it can be polynomial time solvable. The most easiest way is that: Randomly obtain $k$ vertices in the graph (with size $n$), then it can be solvable in $\operatorname{O}(n^k k^2)=\operatorname{O}(n^k)$. But in my concept of constant, it can be any value, for example: $10,100,1\,000,10\,000,\dotsc,10\,000\,000\,000\,000,\dotsc$ Then I wonder why it is still not polynomial time solvable? It seems that all instances can be solved in polynomial time. Is there something wrong?

Answer 1

For each size subgraph $k$ there is a polynomial $p_k$ such that a brute-force search takes at most time $p_k(n)$, where $n$ is the size of a description of the problem instance.

But there is not a single polynomial that works for all sizes of subgraph.

It seems that all instances can be solved in polynomial time.

It makes no sense to say that a particular instance can or cannot be solved in polynomial time. Whether problem can be solved in polynomial time is a collective property of all its instances taken together. One can view it as a measure of how different the difficulties of the various instances can be.

If you view a single problem instance (and a single algorithm) in isolation, the algorithm takes some amount of time to run on the input. This amount of time is what it is -- by itself it is just a constant; you can't meaningfully say it is a polynomial number, or an exponential number -- it's just some number.

But that doesn't mean that we cay that an entire collection of instances (that is, in the usual terminology, a "problem") can be solved in constant time.