
We study the notion of quasiperiodicity, in the sense of "coverability", for
biinfinite words. All previous work about quasiperiodicity focused on right
infinite words, but the passage to the biinfinite case could help to prove
stronger results about quasiperiods of Sturmian words. We demonstrate this by
showing that all biinfinite Sturmian words have infinitely many quasiperiods,
which is not quite (but almost) true in the right infinite case, and giving a
characterization of those quasiperiods.
The main difference between right infinite and the biinfinite words is that,
in the latter case, we might have several quasiperiods of the same length. This
is not possible with right infinite words because a quasiperiod has to be a
prefix of the word. We study in depth the relations between quasiperiods of the
same length in a given biinfinite quasiperiodic word. This study gives enough
information to allow to determine the set of quasiperiods of an arbitrary word.

We prove that the strong immersion order is a wellquasiordering on the
class of semicomplete digraphs, thereby strengthening a result of Chudnovsky
and Seymour that this holds for the class of tournaments.

A simple digraph is semicomplete 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 semicomplete 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 semicomplete digraphs. Our techniques can be
also used to analyze the sizes of minimal obstructions for having small
cutwidth under the induced subdigraph relation.

Let integers $r\ge 2$ and $d\ge 3$ be fixed. Let ${\cal G}_d$ be the set of
graphs with no induced path on $d$ vertices. We study the problem of packing
$k$ vertexdisjoint copies of $K_{1,r}$ ($k\ge 2$) into a graph $G$ from
parameterized preprocessing, i.e., kernelization, point of view. We show that
every graph $G\in {\cal G}_d$ can be reduced, in polynomial time, to a graph
$G'\in {\cal G}_d$ with $O(k)$ vertices such that $G$ has at least $k$
vertexdisjoint copies of $K_{1,r}$ if and only if $G'$ has. Such a result is
known for arbitrary graphs $G$ when $r=2$ and we conjecture that it holds for
every $r\ge 2$.