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

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.

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.