QBF as an Alternative to Courcelle's Theorem

Michael Lampis, Stefan Mengel, Valia Mitsou

We propose reductions to quantified Boolean formulas (QBF) as a new approach to showing fixed-parameter linear algorithms for problems parameterized by treewidth. We demonstrate th…