Skip to main content
5 votes

Is the reduction from a parametrized proplem to the problem kernel just a kind of Karp reduction (polynomial-time reduction)?

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 ...
daniello's user avatar
  • 3,266
2 votes

Major open problems on polynomial kernel (non) existence

A more recent open list of problems can be seen in the open problem session videos of the 2019 Workshop on Kernelization (WorKer 2019) (Session 1, Session 2). Several of the problems mentioned already ...
Christian Komusiewicz's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible