Lower Bounds for Kernelization

Hans Bodlaender

doi:10.1007/978-3-319-13524-3_1

Lower Bounds for Kernelization

Hans Bodlaender

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

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 is not a subset of NP/poly.

Original language	English
Title of host publication	Parameterized and Exact Computation
Subtitle of host publication	9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers
Editors	Marek Cygan, Pinar Heggernes
Publisher	Springer
Pages	1-14
Number of pages	14
ISBN (Electronic)	978-3-319-13524-3
ISBN (Print)	978-3-319-13523-6
DOIs	https://doi.org/10.1007/978-3-319-13524-3_1
Publication status	Published - 2014

Publication series

Name	Lecture Notes in Computer Science

Access to Document

10.1007/978-3-319-13524-3_1

http://dx.doi.org/10.1007/978-3-319-13524-3_1

Cite this

@inbook{8ada466700934769acd365594b94821e,

title = "Lower Bounds for Kernelization",

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 is not a subset of NP/poly.",

author = "Hans Bodlaender",

year = "2014",

doi = "10.1007/978-3-319-13524-3\_1",

language = "English",

isbn = "978-3-319-13523-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--14",

editor = "Marek Cygan and Pinar Heggernes",

booktitle = "Parameterized and Exact Computation",

}

Lower Bounds for Kernelization. / Bodlaender, Hans.
Parameterized and Exact Computation: 9th International Symposium, IPEC 2014, Wroclaw, Poland, September 10-12, 2014. Revised Selected Papers. ed. / Marek Cygan; Pinar Heggernes. Springer, 2014. p. 1-14 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Academic

TY - CHAP

T1 - Lower Bounds for Kernelization

AU - Bodlaender, Hans

PY - 2014

Y1 - 2014

N2 - 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 is not a subset of NP/poly.

AB - 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 is not a subset of NP/poly.

U2 - 10.1007/978-3-319-13524-3_1

DO - 10.1007/978-3-319-13524-3_1

M3 - Chapter

SN - 978-3-319-13523-6

T3 - Lecture Notes in Computer Science

SP - 1

EP - 14

BT - Parameterized and Exact Computation

A2 - Cygan, Marek

A2 - Heggernes, Pinar

PB - Springer

ER -

Lower Bounds for Kernelization

Abstract

Publication series

Access to Document

Fingerprint

Cite this