  Courcelle's theorem and its adaptations to cliquewidth have shaped the field
of exact parameterized algorithms and are widely considered the archetype of
algorithmic meta-theorems. In the past decade, there has been growing interest
in developing parameterized approximation algorithms for problems which are not
captured by Courcelle's theorem and, in particular, are considered not
fixed-parameter tractable under the associated widths.
  We develop a generalization of Courcelle's theorem that yields efficient
approximation schemes for any problem that can be captured by an expanded logic
we call Blocked CMSO, capable of making logical statements about the sizes of
set variables via so-called weight comparisons. The logic controls weight
comparisons via the quantifier-alternation depth of the involved variables,
allowing full comparisons for zero-alternation variables and limited
comparisons for one-alternation variables. We show that the developed framework
threads the very needle of tractability: on one hand it can describe a broad
range of approximable problems, while on the other hand we show that the
restrictions of our logic cannot be relaxed under well-established complexity
assumptions.
  The running time of our approximation scheme is polynomial in
$1/\varepsilon$, allowing us to fully interpolate between faster approximate
algorithms and slower exact algorithms. This provides a unified framework to
explain the tractability landscape of graph problems parameterized by treewidth
and cliquewidth, as well as classical non-graph problems such as Subset Sum and
Knapsack.

Computational Complexity;Discrete Mathematics;Data Structures and Algorithms;Logic in Computer Science