Abstract
Solving the algebraic dichotomy conjecture for constraint satisfaction problems over structures firstorder definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of localconsistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP(πΈ) for firstorder 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).
BibTeX  Entry
@InProceedings{wrona:LIPIcs:2020:11900,
author = {MichaΕ Wrona},
title = {{Relational Width of FirstOrder Expansions of Homogeneous Graphs with Bounded Strict Width}},
booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
pages = {39:139:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771405},
ISSN = {18688969},
year = {2020},
volume = {154},
editor = {Christophe Paul and Markus Bl{\"a}ser},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11900},
URN = {urn:nbn:de:0030drops119000},
doi = {10.4230/LIPIcs.STACS.2020.39},
annote = {Keywords: Constraint Satisfaction, Homogeneous Graphs, Bounded Width, Strict Width, Relational Width, Computational Complexity}
}
Keywords: 

Constraint Satisfaction, Homogeneous Graphs, Bounded Width, Strict Width, Relational Width, Computational Complexity 
Collection: 

37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 
Issue Date: 

2020 
Date of publication: 

04.03.2020 