Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions

Klaus Heeger, André Nichterlein, Rolf Niedermeier

We provide a general framework to exclude parameterized running times of the form $O({\ell }^{\beta }+n^{\gamma })$ for problems that have polynomial running time lower bounds under hypotheses from…