18
$\begingroup$

Courcelle's theorem states that "Every graph property which is expressible in monadic second order logic is decidable in linear time for bounded tree-width graphs". Later it was extended to bounded clique-width graphs [CMR99].

The theorem also holds with linear time replaced by logarithmic space [EJT10] for bounded tree-width graphs. My question is: Does this theorem still hold for bounded clique-width graphs if we replace linear time with logarithmic space? Let me know of the recent progress in this direction.

$\endgroup$
  • 8
    $\begingroup$ You should be careful with what you mean by "monadic second order logic". MSO${}_1$ (vertex set) properties can be extended to bounded clique-width, but MSO${}_2$ (edge set) properties only work with bounded treewidth. $\endgroup$ – David Eppstein May 6 '15 at 20:38
  • 5
    $\begingroup$ I will assume that you are talking about $MSO_1$. I am not aware of any work, however as far as I know about the proof in Tantau et al.'s paper Section 4 can be probably translated to any graph grammar based on disjoint union, fusion and quantifier-free operations (which will include clique-width). Now, the problem will be how to construct a rank-decomposition (or clique-width expression) in logspace. $\endgroup$ – M. kanté May 7 '15 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.