  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 fine-grained complexity. Our framework is
based on cross-compositions from parameterized complexity. We (conditionally)
exclude running times of the form $O(\ell^{{\gamma}/{(\gamma-1)} - \epsilon} +
n^\gamma)$ for any $1<\gamma<2$ and $\epsilon>0$ for the following problems:
  - Longest Common Subsequence: Given two length-$n$ strings and
$\ell\in\mathbb{N}$, is there a common subsequence of length $\ell$?
  - Discrete Fr\'echet Distance: Given two lists of $n$ points each and $k\in
\mathbb{N}$, is the Fr\'echet distance of the lists at most $k$? Here $\ell$ is
the maximum number of points which one list is ahead of the other list in an
optimum traversal.
  Moreover, we exclude running times $O(\ell^{{2\gamma}/{(\gamma -1)}-\epsilon}
+ n^\gamma)$ for any $1<\gamma<3$ and $\epsilon>0$ for:
  - Negative Triangle: Given an edge-weighted graph with $n$ vertices, is there
a triangle whose sum of edge-weights is negative? Here $\ell$ is the order of a
maximum connected component.
  - Triangle Collection: Given a vertex-colored graph with $n$ vertices, is
there for each triple of colors a triangle whose vertices have these three
colors? Here $\ell$ is the order of a maximum connected component.
  - 2nd Shortest Path: Given an $n$-vertex edge-weighted directed graph, two
vertices $s$ and $t$, and $k \in \mathbb{N}$, has the second longest
$s$-$t$-path length at most $k$? Here $\ell$ is the directed feedback vertex
set.
  Except for 2nd Shortest Path all these running time bounds are tight, that
is, algorithms with running time $O(\ell^{{\gamma}/{(\gamma-1)}} + n^\gamma )$
for any $1 < \gamma < 2$ and $O(\ell^{{2\gamma}/{(\gamma -1)}} + n^\gamma)$ for
any $1 < \gamma < 3$, respectively, are known.
