Lower bounds for kernelization

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

Abstract

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
PublisherSpringer
Pages1-14
Number of pages14
ISBN (Electronic)978-3-319-13524-3
ISBN (Print)978-3-319-13523-6
DOIs
Publication statusPublished - 2014
Event9th International Symposium on Parameterized and Exact Computation (IPEC 2014) - Wroclaw, Poland
Duration: 10 Sep 201412 Sep 2014
Conference number: 9

Publication series

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

Conference

Conference9th International Symposium on Parameterized and Exact Computation (IPEC 2014)
Abbreviated titleIPEC 2014
CountryPoland
CityWroclaw
Period10/09/1412/09/14

Fingerprint

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

Cite this