Skip to main content

Questions tagged [kernelization]

Questions related to the existence of kernels for parameterized problems.

Filter by
Sorted by
Tagged with
1 vote
0 answers
45 views

Find the SVM kernel in detecting if a substring in a given string

Consider the task of learning to find a sequence of characters ("signature") in a file that indicates whether it contains a virus or not and let $\mathcal{X}$ be the set of all finite ...
8 votes
0 answers
113 views

Is it possible that feedback vertex set problem has an $O(k^2/\log k)$ kernel?

(This question also suits for other similar natural $\mathrm{NP}$-hard problems) I know that there is a $4k^2$ vertex kernel (and $8k^2$ edge kernel) by Thomasse [Thomasse09] for Feedback Vertex Set (...
2 votes
1 answer
83 views

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 ...
7 votes
0 answers
240 views

Can we achieve a better kernel for the Vertex Cover problem on planar graphs?

We have known how to get a $2k$ kernel for the Vertex Cover problem for thirty years, and it is not expected to be improved assuming UGC. My question is, can we do better for planar graphs? It is easy ...
12 votes
2 answers
384 views

Major open problems on polynomial kernel (non) existence

We are not able to settle the (non-)existence of a polynomial kernel for a parameterized combinatorial NP-complete problem (we also tried to apply some recent lower bound techniques to prove the non-...