Свойства MSO, планарные и неосновные графы

11

Теорема Курселя гласит, что любое свойство графа, определяемое в монадической логике второго порядка, может быть определено за линейное время на графах ограниченной длины дерева . Это одна из самых известных алгоритмических мета-теорем.

Основываясь на теореме Курселя, я высказал следующую гипотезу:

Гипотеза : пусть будет любым определяемым MSO свойством. Если ψ разрешимо за полиномиальное время на плоских графах, то ψ разрешимо за полиномиальное время на всех классах неосновных графов.ψψψ

Я хочу знать, является ли приведенная выше гипотеза явно ложной, т. Е. Есть ли определяемое MSO свойство, которое разрешимо за полиномиальное время на плоских графах, но NP-трудно на некотором классе неосновных графов?

Это мотивация моего предыдущего вопроса : есть ли какие-нибудь проблемы, которые полиномиально разрешимы на графах рода g, но NP-трудны на графах рода> g.

Шива Кинтали
источник

Ответы:

18

Быть 4-красочным? Конечно MSO, и тривиально на планарных графах. Он NP-завершен для достаточно большого запрещенного мелкого клика, путем уменьшения до плоской 3-цветности.

микрофон
источник
1
Более конкретно, 4-окрашиваемость является NP-полной на минор-замкнутом семействе графов вершин путем уменьшения до плоской 3-окрашиваемости.
Дэвид Эппштейн