Lower Bounds on the Complexity of MSO_1 Model-Checking

Robert Ganian, Petr Hlineny, Alexander Langer, Jan ObdrÂÃ¡Lek & Peter Rossmanith
One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not...