MSO-Eigenschaften, planare Diagramme und kleinere freie Diagramme

11

Der Satz von Courcelle besagt, dass jede in der monadischen Logik zweiter Ordnung definierbare Grapheneigenschaft in linearer Zeit auf Graphen mit begrenzter Baumbreite entschieden werden kann . Dies ist einer der bekanntesten algorithmischen Metasätze.

Motiviert durch Courcelles Theorem machte ich folgende Vermutung:

Vermutung : Sei eine beliebige MSO-definierbare Eigenschaft. Wenn ψ in planaren Graphen in Polynomzeit lösbar ist , ist ψ in allen Klassen von mollfreien Graphen in Polynomzeit lösbar.ψψψ

Ich möchte wissen, ob die obige Vermutung offensichtlich falsch ist, dh gibt es eine MSO-definierbare Eigenschaft, die in planaren Graphen polynomial lösbar ist, in einigen Klassen von mollfreien Graphen jedoch NP-hart?

Dies ist die Motivation für meine frühere Frage : Gibt es Probleme, die in Graphen der Gattung g polynomiell lösbar sind, in Graphen der Gattung> g jedoch NP-hart.

Shiva Kintali
quelle

Antworten:

18

4-färbbar sein? Sicherlich MSO und trivial in planaren Graphen. Es ist NP-vollständig für eine ausreichend große verbotene Clique Minor, indem es auf planare 3-Färbbarkeit reduziert wird.

mic
quelle
1
Genauer gesagt ist die 4-Färbbarkeit in der geringfügig geschlossenen Familie der Apex-Graphen NP-vollständig, indem sie auf die planare 3-Färbbarkeit reduziert wird.
David Eppstein