Diminishable parameterized problems and strict polynomial kernelization

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

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

Publication date: 8 September 2020

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-180220

zbMATH Keywords

NP-hard problemsparameterized complexityexponential time hypothesispolynomial-time data reductionkernelization lower bounds

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

This page was built for publication: Diminishable parameterized problems and strict polynomial kernelization