Lower bounds for kernelization

H.L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

1 Citation (Scopus)


Kernelization is the process of transforming the input of a combinatorial decision problem to an equivalent instance, with a guarantee on the size of the resulting instances as a function of a parameter. Recent techniques from the field of fixed parameter complexity and tractability allow to give lower bounds for such kernels. In particular, it is discussed how one can show for parameterized problems that these do not have polynomial kernels, under the assumption that coNP⊆ NP/poly.

Original languageEnglish
Title of host publicationParameterized and Exact Computation
Subtitle of host publication9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers
EditorsM. Cygan , P. Heggemes
Place of PublicationDordrecht
Number of pages14
ISBN (Electronic)978-3-319-13524-3
ISBN (Print)978-3-319-13523-6
Publication statusPublished - 2014
Event9th International Symposium on Parameterized and Exact Computation, IPEC 2014 - Wroclaw, Poland
Duration: 10 Sept 201412 Sept 2014
Conference number: 9

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference9th International Symposium on Parameterized and Exact Computation, IPEC 2014
Abbreviated titleIPEC 2014


Dive into the research topics of 'Lower bounds for kernelization'. Together they form a unique fingerprint.

Cite this