Propriedades MSO, gráficos planares e gráficos livres de menor importância

11

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?

Shiva Kintali
fonte

Respostas:

18

Sendo 4 cores? Certamente MSO, e trivial em gráficos planares. É NP-completo para uma camarilha menor proibida o suficiente, por redução para 3 cores planares.

microfone
fonte
1
Mais explicitamente, a 4-colorability é NP-complete na família menor fechada de gráficos do ápice, por redução à 3-colorability planar.
David Eppstein 29/08