Теорема Курселя гласит, что любое свойство графа, определяемое в монадической логике второго порядка, может быть определено за линейное время на графах ограниченной длины дерева . Это одна из самых известных алгоритмических мета-теорем.
Основываясь на теореме Курселя, я высказал следующую гипотезу:
Гипотеза : пусть будет любым определяемым MSO свойством. Если ψ разрешимо за полиномиальное время на плоских графах, то ψ разрешимо за полиномиальное время на всех классах неосновных графов.
Я хочу знать, является ли приведенная выше гипотеза явно ложной, т. Е. Есть ли определяемое MSO свойство, которое разрешимо за полиномиальное время на плоских графах, но NP-трудно на некотором классе неосновных графов?
Это мотивация моего предыдущего вопроса : есть ли какие-нибудь проблемы, которые полиномиально разрешимы на графах рода g, но NP-трудны на графах рода> g.
источник