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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
