Diminishable parameterized problems and strict polynomial kernelization

DOI10.3233/COM-180220zbMath1485.68117MaRDI QIDQ5118456

Rolf Niedermeier, Henning Fernau, Danny Hermelin, Andreas Krebs, Hendrik Molter, Till Fluschnik

Publication date: 8 September 2020

Published in: Computability (Search for Journal in Brave)

zbMATH Keywords

NP-hard problems; parameterized complexity; exponential time hypothesis; polynomial-time data reduction; kernelization lower bounds

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q27: Parameterized complexity, tractability and kernelization