  Vertex deletion problems for graphs are studied intensely in classical and
parameterized complexity theory. They ask whether we can delete at most k
vertices from an input graph such that the resulting graph has a certain
property. Regarding k as the parameter, a dichotomy was recently shown based on
the number of quantifier alternations of first-order formulas that describe the
property. In this paper, we refine this classification by moving from
quantifier alternations to individual quantifier patterns and from a dichotomy
to a trichotomy, resulting in a complete classification of the complexity of
vertex deletion problems based on their quantifier pattern. The more
fine-grained approach uncovers new tractable fragments, which we show to not
only lie in FPT, but even in parameterized constant-depth circuit complexity
classes. On the other hand, we show that vertex deletion becomes intractable
already for just one quantifier per alternation, that is, there is a formula of
the form {\forall}x{\exists}y{\forall}z({\psi}), with {\psi} quantifier-free,
for which the vertex deletion problem is W[1]-hard. The fine-grained analysis
also allows us to uncover differences in the complexity landscape when we
consider different kinds of graphs and more general structures: While basic
graphs (undirected graphs without self-loops), undirected graphs, and directed
graphs each have a different frontier of tractability, the frontier for
arbitrary logical structures coincides with that of directed graphs.
