<p>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).</p>
<p>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 <span class="math-container">$\Sigma^*$</span>), while parameterized reductions deal with parameterized problems (subsets of <span class="math-container">$\Sigma^* \times \mathbb{N}$</span>). Karp reductions (typically) go between <em>different</em> languages, while kernelization algorithms for a single (parameterized) problem. There are more differences, but I guess you get my drift.</p>

CC BY-SA 4.0
2020-11-06T09:57:32.090Z
For the first reason, I noticed that the parameterized problems and classical problems are different. But I did not get that it is a important difference, I think that one can simply generate the notion of Karp reduction for the binary language. And for the second reason, generally, we do not restrict the kernelization for a single problem. (Actually, in the Downey and Fellows's book, the Turing kernelization is defined by using two (parameterized) languages).
Blanco
CC BY-SA 4.0
2020-11-06T09:57:36.530Z
I noticed the differences you mention before I wrote my question, but it seems that these facts are not strong enough for me to believe that they are essentially different.
Blanco
CC BY-SA 4.0
2020-10-18T00:30:21.340Z
2020-10-18T00:30:21.340Z
daniello
<p>The kernel of a parameterized problem <span class="math-container">$L$</span> is a reduction <span class="math-container">$(x,k) \mapsto (x',k')$</span> such that:</p>
<ul>
<li><span class="math-container">$(x,k) \in L \Leftrightarrow  (x',k') \in L$</span></li>
<li><span class="math-container">$|x'| \leq f(k)$</span> for some function <span class="math-container">$f$</span></li>
<li><span class="math-container">$k' \leq g(k)$</span> for some function <span class="math-container">$g$</span></li>
<li>transformation must be computed in polynomial time.</li>
</ul>
<p>Can I say that the reduction is a Karp reduction <span class="math-container">$(x,k) \mapsto (x',k')$</span> such that</p>
<ul>
<li><span class="math-container">$(x,k) \in L \Leftrightarrow  (x',k') \in L$</span></li>
<li><span class="math-container">$|x'| \leq f(k)$</span> for some function <span class="math-container">$f$</span></li>
<li><span class="math-container">$k' \leq g(k)$</span> for some function <span class="math-container">$g$</span></li>
</ul>
<p>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.</p>

<parameterized-complexity><kernelization>
Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?
Blanco
# Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

(Asked by: username_0 on 2020-10-17)

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.

**Tags:** parameterized-complexity, kernelization

---

## 1 answers

### Answer by username_1 on 2020-10-18. Score: 5

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.

> **Comments:**
> **username_0**: For the first reason, I noticed that the parameterized problems and classical problems are different. But I did not get that it is a important difference, I think that one can simply generate the notion of Karp reduction for the binary language. And for the second reason, generally, we do not restrict the kernelization for a single problem. (Actually, in the Downey and Fellows's book, the Turing kernelization is defined by using two (parameterized) languages).  
> **username_0**: I noticed the differences you mention before I wrote my question, but it seems that these facts are not strong enough for me to believe that they are essentially different.  

---

