What does a kernel of size n,n^2 ,... mean?

Question

So according to Wikipedia,

In the Notation of [Flum and Grohe (2006)], a ''parameterized problem'' consists of a decision problem $L\subseteq\Sigma^*$ and a function $\kappa:\Sigma^*\to N$, the parameterization. The ''parameter'' of an instance $x$ is the number $\kappa(x)$. A '''kernelization''' for a parameterized problem $L$ is an algorithm that takes an instance $x$ with parameter $k$ and maps it in polynomial time to an instance $y$ such that

• $x$ is in $L$ if and only if $y$ is in $L$ and
• the size of $y$ is bounded by a computable function $f$ in $k$. Note that in this notation, the bound on the size of $y$ implies that the parameter of $y$ is also bounded by a function in $k$.

The function $f$ is often referred to as the size of the kernel. If $f=k^{O(1)}$, it is said that $L$ admits a polynomial kernel. Similarly, for $f={O(k)}$, the problem admits linear kernel. '''

Stupid question, but since the parameter can be anything can't you just define the parameter to be really large and then you always have linear kernel?

Answer 1

The point of investigating a parametrized problem is that we hope or assume that the parameter will be fairly small or even bounded by a known small constant in some particular case you encounter in practice. In that case, algorithms with FPT could be called efficient.

So yes, you can definitely pick an arbitrary parameter that will be very large in practice, but then a linear kernel will probably not be useful, because you are measuring the wrong parameter.

As a side remark, this is not something specific to parametrized complexity. In any type of complexity, you must be careful that the thing your are investigating the complexity of is actually meaningful.