0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ So I suppose I'm nitpicking and being pedantic, but if you say vertex cover has a kernel of quadratic size or _____ has a kernel of polynomial-size, what is it formally saying? $\endgroup$
    – Hao S
    Sep 13, 2020 at 19:58
  • $\begingroup$ @HaoS If you don't give me a parameter, then formally, you are saying nothing. However, when most people don't give a parameter, they mean parametrized by the so-called "natural" parameter, which is usually the "size" of the answer. So, for vertex cover, the "natural" parameter is the number of vertices in the optimal vertex cover. The concept of a natural parameter is highly informal, I'm afraid. $\endgroup$
    – Discrete lizard
    Sep 13, 2020 at 20:05
  • $\begingroup$ thanks for the clarification $\endgroup$
    – Hao S
    Sep 13, 2020 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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