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 ...
Tran Khanh's user avatar
8 votes
0 answers
111 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 (...
Blanco's user avatar
  • 421
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 ...
Blanco's user avatar
  • 421
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-...
Marzio De Biasi's user avatar
7 votes
0 answers
239 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 ...
Yixin Cao's user avatar
  • 2,559