Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences?
Jakub Gajarský · 2016
Abstract. Fix an integer h ≥ 1. In the universe of coloured trees of height at most h, we prove that for any MSO formula with r variables there exists a set of kernels, each of size bounded by an elementary func-tion of r and the number of colours. This yields two noteworthy conse-quences. Consider any graph class G having a simple MSO interpretation in the universe of coloured trees of height h (equivalently, G is a class of shrub-depth h). First, G admits an MSO model checking algorithm whose runtime has an elementary dependence on the formula size. Sec-ond, on G the expressive powers of FO and MSO coincide (which extends a 2012 result of Elberfeld, Grohe, and Tantau [9]).