O teorema de Courcelle afirma que toda propriedade de gráfico definível na lógica monádica de segunda ordem pode ser decidida em tempo linear em gráficos de largura de árvore limitada . Este é um dos meta-teoremas algorítmicos mais conhecidos.
Motivado pelo teorema de Courcelle, fiz a seguinte conjectura:
Conjectura : Seja qualquer propriedade definível pelo MSO. Se é solucionável em tempo polinomial em gráficos planares, então é solucionável em tempo polinomial em todas as classes de gráficos livres menores.
Eu quero saber se a conjectura acima é obviamente falsa, ou seja, existe uma propriedade definível pelo MSO que pode ser resolvida em tempo polinomial em gráficos planares, mas NP-hard em alguma classe de gráficos menores-livres?
Esta é a motivação por trás da minha pergunta anterior : existem problemas que são polinomialmente solucionáveis em gráficos do gênero g, mas rígidos em NP em gráficos do gênero g?
fonte