Related Work. Monadic second-order logic (MSO) comes
in two versions: MSO\(_1\)  admits quantification only over sets of nodes
while MSO\(_2\)  can additionally quantify over sets of
edges. Courcelle's theorem states that MSO\(_2\)  model checking is FPL
on graphs of bounded treewidth and
[1]} shows the same for MSO\(_1\)  and
graphs of bounded cliquewidth (when a \(k\) -expression is provided). The
problem studied in the current paper can be translated into MSO\(_1\) ,
but this does not yield the tight complexities presented here. It was
shown in [2]} that MSO\(_2\)  is not FPT for
graph classes that have unbounded treewidth and are closed under
substructures (under certain assumptions), see also
[3]}; results in this style do not
appear to be known for MSO\(_1\)  and cliquewidth.
<FIGURE>