Universal Structures and the logic of Forbidden Patterns
arXiv:0904.2521 · doi:10.2168/LMCS-5(2:13)2009
Abstract
Forbidden Patterns Problems (FPPs) are a proper generalisation of Constraint Satisfaction Problems (CSPs). However, we show that when the input is connected and belongs to a class which has low tree-depth decomposition (e.g. structure of bounded degree, proper minor closed class and more generally class of bounded expansion) any FPP becomes a CSP. This result can also be rephrased in terms of expressiveness of the logic MMSNP, introduced by Feder and Vardi in relation with CSPs. Our proof generalises that of a recent paper by Nesetril and Ossona de Mendez. Note that our result holds in the general setting of problems over arbitrary relational structures (not just for graphs).
25 pages, 3 figures, extended version of conference papers at CSR'06 and CSL'06