Kernels em complexidade parametrizada

Alguém pode me explicar o que são os kernels (problemáticos) e qual a utilidade deles? Meus slides dizem:

O kernel de um problema parametrizado $L$ é uma transformação $(x,k) \mapsto (x',k')$ de tal modo que:

• $(x,k) \in L \Leftrightarrow (x',k') \in L$
• $|x'| \leq f(k)$ para alguma função $f$
• $k' \leq g(k)$ para alguma função $g$
• transformação deve ser calculada em tempo polinomial.

Minhas perguntas são:

• Como isso está relacionado a um problema que está sendo corrigido nos parâmetros tratáveis?
• O que torna os kernels úteis?
• De onde vem essa definição.

O exemplo nos meus slides é para cobertura de vértice, mas eu realmente não entendo, porque os slides são meio curtos.

Intuitivamente, um algoritmo de kernelização é um algoritmo que, em tempo polinomial, pré-processa uma determinada instância e gera uma instância cujo tamanho é delimitado no parâmetro. O objetivo da kernelização é (pelo menos) duas vezes. Temos garantias de desempenho comprováveis, ou seja, podemos provar limites superiores na instância de saída, que possui aplicativos tanto no design de algoritmos quanto também como uma medida de complexidade.

Mais formalmente, um algoritmo de kernelização (geralmente chamado de kernel), é um algoritmo para um problema que em uma entrada $(G,k)$gera uma instância equivalente $(G',k')$ com $\max\{|G'|,k'\} \leq f(k)$ para alguma função $f$. Além disso, o algoritmo precisa ser executado em tempo polinomial.

O resultado a seguir mostra que o poder dos núcleos é, por assim dizer, equivalente ao poder da rastreabilidade de parâmetros fixos ( PDF )

Teorema (Folclore). Um problema é um parâmetro fixo tratável se e somente se ele admite um kernel e é decidível.

Embora a noção de kernel coincida com a rastreabilidade dos parâmetros fixos, há uma versão mais forte da kernelização em que exigimos a função $f$ acima para ser um polinômio.

Se você quiser ver as definições originais, aconselho que você escolha o livro de Downey e Fellows sobre complexidade parametrizada ou comece na tese de Niedermeier sobre Habilitação mencionada acima. Há também um artigo da Wikipedia sobre Kernelization .