  We investigate the parameterized complexity of Binary CSP parameterized by
the vertex cover number and the treedepth of the constraint graph, as well as
by a selection of related modulator-based parameters. The main findings are as
follows:
  i) Binary CSP parameterized by the vertex cover number is
$\mathrm{W}[3]$-complete. More generally, for every positive integer $d$,
Binary CSP parameterized by the size of a modulator to a treedepth-d graph is
$\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems
that are complete for odd levels of the W-hierarchy.
  ii) We introduce a new complexity class XSLP, defined so that Binary CSP
parameterized by treedepth is complete for this class. We provide two
equivalent characterizations of XSLP: the first one relates XSLP to a model of
an alternating Turing machine with certain restrictions on conondeterminism and
space complexity, while the second one links XSLP to the problem of
model-checking first-order logic with suitably restricted universal
quantification. Interestingly, the proof of the machine characterization of
XSLP uses the concept of universal trees, which are prominently featured in the
recent work on parity games
  iii) We describe a new complexity hierarchy sandwiched between the
W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a
parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq
\mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that
interpolates between the vertex cover number and the treedepth.
  We expect that many of the studied classes will be useful in the future for
pinpointing the complexity of various structural parameterizations of graph
problems.
