Hardness of monadic second-order formulae over succinct graphs

Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon +3

Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every cw-nontrivial monadic second-order (MSO) property is either NP-hard or coNP-hard over graph…