8
$\begingroup$

I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth.

I am only a beginner in this field.

Any suggestions?

|cite|improve this question
$\endgroup$
4
$\begingroup$

There's a soft introduction in Rolf Niedermeier's book Invitation to Fixed Parameter Algorithms. Daniel Marx also has quite a few slides available on his homepage that contain short examples of modeling a problem in MSOL. One set of relevant slides is here. For more links, see a related question on CSTheory.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

Courcelle's Theorem is one of the things that is better explained (compared with Niedermeier's book) in the book of Flum and Grohe (see the treewidth chapter), since model checking problems etc. are covered in detail there. By the same authors and Frick there is also a generalization of Courcelle's Theorem: Query evaluation via tree-decompositions. You might also look at similar meta theorems for clique-width and shrub-depth.

Also look here for a short overview of some of Courcelle's earlier papers.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.