Preservation and decomposition theorems for bounded degree structures

ABSTRACT. We provide elementary algorithms for two preservation theorems for first-order sentences with modulo m counting quantifiers (FO+MOD_m) on the class C_d of all finite structures of degree at most d: For each FO+MOD_m-sentence that is preserved under homomorphisms (extensions) on C_d, a C_d-equivalent existential-positive (existential) FO-sentence can be constructed in 4-fold (6-fold) exponential time. For FO-sentences, the algorithm has 3-fold (5-fold) exponential time complexity. This is complemented by lower bounds showing that for FO-sentences a 3-fold exponential blow-up of the computed existential-positive (existential) sentence is unavoidable.

Furthermore, we show that for an input FO-formula, a C_d-equivalent Feferman-Vaught decomposition can be computed in 3-fold exponential time. We also provide a matching lower bound.