2026-08-14T17:24:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11900 2024-03-06T10:48:58Z ddc:004 open_access

Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width Wrona, Michał Constraint Satisfaction Homogeneous Graphs Bounded Width Strict Width Relational Width Computational Complexity 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(?) for first-order expansions ? of countably infinite homogeneous graphs ℋ := (A; E), which happen all to be finitely bounded. We study our problem for structures ? that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of CSP(?) 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 ? under consideration have relational width exactly (2, ?_ℋ) where ?_ℋ is the maximal size of a forbidden subgraph of ℋ, but not smaller than 3. It beats the upper bound: (2 m, 3 m) where m = max(arity(?)+1, ?, 3) and arity(?) is the largest arity of a relation in ?, which follows from a sufficient condition implying bounded relational width given in [Manuel Bodirsky and Antoine Mottet, 2018]. Since ?_ℋ may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures ?, whose relational width, if finite, is always at most (2,3). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michał Wrona 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.39 urn:nbn:de:0030-drops-119000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.39 eng https://creativecommons.org/licenses/by/3.0/legalcode