<p>After asking around some more, it seems that the answers to 1) and 2) are both YES. Optimizing the cardinality of a set is possible in LinEMSOL (as mentioned by Martin Lackner); as I have been told, the existence of the cardinality predicates is no problem since they can be efficiently handled by finite-state tree automatons, which should follow (more explicitly than in the originally referenced paper) from <a href="http://dx.doi.org/10.1016/j.dam.2009.10.018" rel="noreferrer">On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width</a>.</p>

CC BY-SA 2.5
2011-02-08T13:20:39.957Z
2011-02-08T13:20:39.957Z
Bart Jansen
<p><a href="http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf" rel="nofollow">http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf</a> (which is the paper you mentioned but a better readable version) defines LinEMSOL (Definition 10).
LinEMSOL allows for MSO1 optimization problems and Theorem 4 states that such problems are fixed-parameter tractable with regard to clique-width. So the answer to your second bullet/question should be yes.</p>

<p>Concerning the first bullet: In "Vertex-minors, monadic second-order logic, and a conjecture by Seese" by Bruno Courcelle and Sang-il Oum the authors write that "It can be proved that no MS formula φ(X) can express, in every structure, that a set X has even cardinality [10]" where [10]="Courcelle, The monadic second-order logic of graphs"</p>

<p>Hope that helps</p>

CC BY-SA 2.5
2011-02-08T09:33:41.980Z
Thanks for the insight, but the fact that no MS formula (in general) can express whether a set has even cardinality is not really relevant here, since the question is about the Counting MSOL language which has special predicates added that explicitly allow testing the cardinality of a set modulo some fixed number; hence in the Counting MSOL language it is possible to express the even-ness of a set, and the question was whether we can efficiently find the smallest/biggest set satisfying a sentence in Counting MSOL parameterized by cliquewidth. Thanks anyway!
Bart Jansen
CC BY-SA 2.5
2011-02-08T12:46:10.783Z
You are of course right. I just wanted to make the point that the paper you mentioned does not cover CMSOL. (I do not know of a result that does that.)
Martin Lackner
CC BY-SA 2.5
2011-02-06T12:03:32.553Z
2011-02-06T12:03:32.553Z
Martin Lackner
<p>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$.</p>

<p><a href="http://portal.acm.org/citation.cfm?id=81255">Courcelle's famous theorem</a> 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 <a href="http://portal.acm.org/citation.cfm?id=243727">Bodlaender's algorithm</a>), 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)$.</p>

<p>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 <strong>not edge sets</strong> 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 </p>

<blockquote>
  <p><a href="http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf">Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width</a> by Courcelle, Makowsky and Rotics, Theory of Computing Systems, 2000.</p>
</blockquote>

<p>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.</p>

<ul>
<li>Does MSOL1 allow the $\textrm{Card}_{n,p}(S)$ predicate for testing the size of a set modulo some number?</li>
<li>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?</li>
</ul>

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

CC BY-SA 2.5
2011-01-24T14:48:06.743Z
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?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-24T16:52:34.217Z
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$).
Bart Jansen
CC BY-SA 2.5
2011-01-24T19:42:45.473Z
Bruno Courcelle's draft book volumes might be useful: see http://www.labri.fr/perso/courcell/ActSci.html under "Graph structure and monadic second-order logic, a language theoretic approach".
András Salamon
CC BY-SA 2.5
2011-01-25T13:48:52.103Z
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.
Bart Jansen
<ds.algorithms><reference-request><graph-algorithms><descriptive-complexity><cliquewidth>
MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates
Bart Jansen
# MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

(Asked by: username_0 on 2011-01-24)

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](http://portal.acm.org/citation.cfm?id=81255) 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](http://portal.acm.org/citation.cfm?id=243727)), 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](http://perso.ens-lyon.fr/eric.thierry/Graphes2007/cmr00.pdf) 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!

**Tags:** ds.algorithms, reference-request, graph-algorithms, descriptive-complexity, cliquewidth

> **Comments:**
> **username_1**: 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?  
> **username_0**: 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$).  
> **username_2**: Bruno Courcelle's draft book volumes might be useful: see http://www.labri.fr/perso/courcell/ActSci.html under "Graph structure and monadic second-order logic, a language theoretic approach".  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_0 on 2011-02-08. Score: 5 | Accepted answer

After asking around some more, it seems that the answers to 1) and 2) are both YES. Optimizing the cardinality of a set is possible in LinEMSOL (as mentioned by username_3); as I have been told, the existence of the cardinality predicates is no problem since they can be efficiently handled by finite-state tree automatons, which should follow (more explicitly than in the originally referenced paper) from [On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width](http://dx.doi.org/10.1016/j.dam.2009.10.018).


---

### Answer by username_3 on 2011-02-06. Score: 4

<http://www.labri.fr/perso/courcell/Textes1/BC-Makowsky-Rotics(2000).pdf> (which is the paper you mentioned but a better readable version) defines LinEMSOL (Definition 10).
LinEMSOL allows for MSO1 optimization problems and Theorem 4 states that such problems are fixed-parameter tractable with regard to clique-width. So the answer to your second bullet/question should be yes.

Concerning the first bullet: In "Vertex-minors, monadic second-order logic, and a conjecture by Seese" by Bruno Courcelle and Sang-il Oum the authors write that "It can be proved that no MS formula φ(X) can express, in every structure, that a set X has even cardinality [10]" where [10]="Courcelle, The monadic second-order logic of graphs"

Hope that helps

> **Comments:**
> **username_0**: Thanks for the insight, but the fact that no MS formula (in general) can express whether a set has even cardinality is not really relevant here, since the question is about the Counting MSOL language which has special predicates added that explicitly allow testing the cardinality of a set modulo some fixed number; hence in the Counting MSOL language it is possible to express the even-ness of a set, and the question was whether we can efficiently find the smallest/biggest set satisfying a sentence in Counting MSOL parameterized by cliquewidth. Thanks anyway!  
> **username_3**: You are of course right. I just wanted to make the point that the paper you mentioned does not cover CMSOL. (I do not know of a result that does that.)  

---

