Bodlaender's Theorem states that for every k there is a linear-time algorithm that decides whether an input graph has tree width~k and, if so, computes a width-k tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic second-order formula \phi and for
every k there is ... more >>>