World's most popular travel blog for travel bloggers.

[Solved]: Kernels in parameterized complexity

, , No Comments
Problem Detail: 

Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say:

The kernel of a parameterized problem $L$ is a transformation $(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.

My questions are:

  • How is this connected with a problem being fixed parameter tractable?
  • What makes kernels useful?
  • Where does this definition come from.

The example on my slides is for vertex cover, but I don't really get it, cause the slides are kind of short.

Asked By : Peter W

Answered By : Pål GD

Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter. The goal of kernelization is (at least) two-fold. We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the design of algorithms, and also as a complexity measure.

Kernel diagram

More formally a kernelization algorithm (often referred to as the kernel), is an algorithm for a problem which on an input $(G,k)$ outputs an equivalent instance $(G',k')$ with $\max\{|G'|,k'\} \leq f(k)$ for some function $f$. Furthermore, the algorithm needs to run in polynomial time.

The following result shows that the power of kernels is, so to speak, equivalent to the power of fixed parameter tractability (PDF)

Theorem (Folklore). A problem is fixed parameter tractable if and only if it admits a kernel and is decidable.

Although the notion of kernel coincides with fixed parameter tractability, there is a stronger version of kernelization where we demand the function $f$ above to be a polynomial.

If you want to see the original definitions, I advice you to pick up Downey and Fellows' book on parameterized complexity, or start from Niedermeier's Habilitation thesis mentioned above. There is also a Wikipedia article on Kernelization.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40556

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback