Name
Abstract | ||
|---|---|---|
Kernelization-a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems-plays a central role in parameterized complexity and has triggered an extensive line of research. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Muller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the weaker assumption of P not equal NP. Finally, we study a relaxation of the notion of strict kernels. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-94418-0_17 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Conference | 10936 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Fernau | 1 | 1646 | 162.68 |
| Till Fluschnik | 2 | 26 | 7.14 |
| Danny Hermelin | 3 | 790 | 48.62 |
| Andreas Krebs | 4 | 21 | 8.20 |
| Hendrik Molter | 5 | 57 | 11.14 |
| Rolf Niedermeier | 6 | 3465 | 234.21 |