# MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

CMSOL is Counting Monadic Second Order Logic, i.e. a logic of graphs where the domain is the set of vertices and edges, there are predicates for vertex-vertex adjacency and edge-vertex incidence, there is quantification over edges, vertices, edge sets and vertex sets, and there is a predicate $\textrm{Card}_{n,p}(S)$ which expresses whether the size of $S$ is $n$ modulo $p$.

Courcelle's famous theorem states that if $\Pi$ is a property of graphs expressible in CMSOL, then for every graph $G$ of treewidth at most $k$ it can be decided in linear time whether $\Pi$ holds, provided that a tree decomposition of $G$ is given in the input. Later versions of the theorem dropped the requirement that a tree decomposition is given in the input (because one can be computed with Bodlaender's algorithm), and also allowed optimization instead of merely decision; i.e. given a MSOL formula $\phi(S)$ we can also compute the largest or smallest set $S$ which satisfies $\phi(S)$.

My question concerns the adaptation of Courcelle's theorem to graphs of bounded cliquewidth. There is a similar theorem saying that if you have a MSOL1 which allows quantification over vertices, edges, vertex sets but not edge sets then given a graph $G$ of cliquewidth $k$ (with given clique-expression), for every fixed $k$ it can be decided in linear time whether graph $G$ satisfies some MSOL1 formula $\phi$; all references I have seen point to

Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width by Courcelle, Makowsky and Rotics, Theory of Computing Systems, 2000.

I have tried to read the paper, but it is not self-contained with respect to the exact definition of MSOL1 and it is frankly hard to read. I have two questions with respect to what exactly is possible to optimize in FPT, parameterized by the cliquewidth of the graph, if a clique expression is given in the input.

• Does MSOL1 allow the $\textrm{Card}_{n,p}(S)$ predicate for testing the size of a set modulo some number?
• Is it possible to find a minimum / maximum size set $S$ which satisfies a MSOL1 formula $\phi(S)$ in FPT parameterized by cliquewidth, when the expression is given?

For both these questions I would also like to know what the correct references are to cite when claiming these results. Thanks in advance!

• I tried to modify some of your article, sorry about that. Because I'm pretty interested in your question, but still after the modification I'm not sure if I understand you ideas correctly. So, do you mean that you need the exact definition of MSOL1, and the existance of predicate and an FPT of an optimization problem? Jan 24 '11 at 14:48
• Ideally what I would like to hear is that for each fixed $MSOL_1$ formula $\phi(S)$, where $S$ is a vertex set variable and the formula $\phi$ involves Card$_{n,p}(S)$ predicates, there is an algorithm which given a graph G and a clique-expression of width k, computes a minimum-size set $S$ which satisfies $\phi(S)$ in $f(k) |V(G)|^{O(1)}$ for some arbitrary function $f$ (or outputs that no set $S$ satisfies $\phi$). Jan 24 '11 at 16:52
• Bruno Courcelle's draft book volumes might be useful: see labri.fr/perso/courcell/ActSci.html under "Graph structure and monadic second-order logic, a language theoretic approach". Jan 24 '11 at 19:42
• Thanks; this at least settles part 1) of the problem, since his Theorem 6.4 in the first part of the book says: For all finite sets K and L of vertex and edge labels, the model-checking problem of a Counting MSOL1 formula is fixed-parameter cubic with respect to the parameter cliquewidth(G) + size of the formula. Jan 25 '11 at 13:48