Collapsing the Bounded Width Hierarchy for Infinite-Domain Constraint Satisfaction Problems: When Symmetries Are Enough

Journal
SIAM journal on computing  
Volume
53
Issue
6
Citation
SIAM Journal on Computing 53 (6): 1709-1745 (2024)
Publisher DOI
10.1137/22m1538934
Scopus ID
2-s2.0-85214290902
Publisher
Society for Industrial & Applied Mathematics (SIAM)
We prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n>3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain constraint satisfaction problems (CSPs) studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of Monotone Monadic SNP (MMSNP) sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al. In particular, the bounded width hierarchy collapses in those cases as well. Our results extend the scope of theorems of Barto and Kozik characterizing bounded width for finite structures and show the applicability of infinite-domain CSPs to other fields.
DDC Class
004: Computer Sciences