11
$\begingroup$

Courcelle's theorem states that every graph property definable in monadic second-order logic can be decided in linear time on graphs of bounded treewidth. This is one of the most well-known algorithmic meta-theorems.

Motivated by Courcelle's theorem, I made the following conjecture :

Conjecture : Let $\psi$ be any MSO-definable property. If $\psi$ is solvable in polynomial-time on planar graphs, then $\psi$ is solvable in polynomial-time on all classes of minor-free graphs.

I want to know if the above conjecture is obviously false i.e., is there an MSO-definable property that is polynomial-time solvable on planar graphs but NP-hard on some class of minor-free graphs ?

This is the motivation behind my earlier question : Are there any problems that are polynomially solvable on graphs of genus g but NP-hard on graphs of genus > g.

$\endgroup$
18
$\begingroup$

Being 4-colorable? Certainly MSO, and trivial on planar graphs. It's NP-complete for a large enough forbidden clique minor, by reduction to planar 3-colorability.

$\endgroup$
  • 1
    $\begingroup$ More explicitly, 4-colorability is NP-complete on the minor-closed family of apex graphs, by reduction to planar 3-colorability. $\endgroup$ – David Eppstein Aug 29 '14 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.