Revisitando o Teorema de Courcelle

A Complexidade Parametrizada é uma teoria que propõe análise e projeto multivariado de algoritmos. O Teorema de Courcelle é um dos resultados parametrizados mais famosos. Ele estabelece que problemas expressíveis em Lógica Monádica de Segunda Ordem podem ser resolvidos eficientemente em classes de grafos que possuem treewidth limitada. O teorema está definido matematicamente e, apesar de haver parcial algoritmização, não foi encontrada na literatura uma versão totalmente algorítmica e/ou implementação do procedimento. Este trabalho busca fornecer uma descrição algorítmica para o Teorema de Courcelle, permitindo que este seja usado para resolução efetiva de problemas em vez de apenas provar a existência de soluções eficientes.