First Order Logic on Pathwidth Revisited Again

Michael Lampis

Courcelle's celebrated theorem states that all MSO-expressible properties can be decided in linear time on graphs of bounded treewidth. Unfortunately, the hidden constant implied b…