2
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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