  A simple digraph is semi-complete if for any two of its vertices $u$ and $v$,
at least one of the arcs $(u,v)$ and $(v,u)$ is present. We study the
complexity of computing two layout parameters of semi-complete digraphs:
cutwidth and optimal linear arrangement (OLA). We prove that: (1) Both
parameters are $\mathsf{NP}$-hard to compute and the known exact and
parameterized algorithms for them have essentially optimal running times,
assuming the Exponential Time Hypothesis; (2) The cutwidth parameter admits a
quadratic Turing kernel, whereas it does not admit any polynomial kernel unless
$\mathsf{NP}\subseteq \mathsf{coNP}/\textrm{poly}$. By contrast, OLA admits a
linear kernel. These results essentially complete the complexity analysis of
computing cutwidth and OLA on semi-complete digraphs. Our techniques can be
also used to analyze the sizes of minimal obstructions for having small
cutwidth under the induced subdigraph relation.
