Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

Question

The kernel of a parameterized problem $L$ is a reduction $(x,k) \mapsto (x',k')$ such that:

• $(x,k) \in L \Leftrightarrow (x',k') \in L$
• $|x'| \leq f(k)$ for some function $f$
• $k' \leq g(k)$ for some function $g$
• transformation must be computed in polynomial time.

Can I say that the reduction is a Karp reduction $(x,k) \mapsto (x',k')$ such that

• $(x,k) \in L \Leftrightarrow (x',k') \in L$
• $|x'| \leq f(k)$ for some function $f$
• $k' \leq g(k)$ for some function $g$

I am confused because the language is a binary language. Perhaps, this is a naive question, but I am not sure if I can call it Karp reduction. It seems that the Karp reduction is not used in parameterized complexity.

Answer 1

Clearly there are similarities - both kernelization algorithms and Karp reductions need to work in polynomial time and produce an output instances that is equivalent to the input instance (in the sense that both are “yes”-instances or both are “no”-instances).

But they are not the same concept, nor is one a special case of the other. First, they operate on different objects: Karp reductions deal with languages (subsets of $\Sigma^*$), while parameterized reductions deal with parameterized problems (subsets of $\Sigma^* \times \mathbb{N}$). Karp reductions (typically) go between different languages, while kernelization algorithms for a single (parameterized) problem. There are more differences, but I guess you get my drift.