  It is known that first-order logic with some counting extensions can be
efficiently evaluated on graph classes with bounded expansion, where depth-$r$
minors have constant density. More precisely, the formulas are $\exists x_1 ...
x_k \#y \varphi(x_1,...,x_k, y)>N$, where $\varphi$ is an FO-formula. If
$\varphi$ is quantifier-free, we can extend this result to nowhere dense graph
classes with an almost linear FPT run time. Lifting this result further to
slightly more general graph classes, namely almost nowhere dense classes, where
the size of depth-$r$ clique minors is subpolynomial, is impossible unless
FPT=W[1]. On the other hand, in almost nowhere dense classes we can approximate
such counting formulas with a small additive error. Note those counting
formulas are contained in FOC({<}) but not FOC1(P). In particular, it follows
that partial covering problems, such as partial dominating set, have fixed
parameter algorithms on nowhere dense graph classes with almost linear running
time.
