Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width

Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures first-order definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of local-consistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP(A) for first-order expansions A of countably infinite homogeneous graphs H := (A; E), which happen all to be finitely bounded. We study our problem for structures A that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of CSP(A) not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking. Our main result is that the structures A under consideration have relational width exactly (2, L-H) where L-H is the maximal size of a forbidden subgraph of 74, but not smaller than 3. It beats the upper bound: (2m, 3m) where m = max(arity(A) + 1, L, 3) and arity(A) is the largest arity of a relation in A, which follows from a sufficient condition implying bounded relational width given in [10]. Since L-H may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures A, whose relational width, if finite, is always at most (2, 3).