Bounded width problems and algebras (Q997127)

Many natural decision problems like SAT or graph \(k\)-colourability can be expressed in terms of a decision problem of the following type CSP\((A)\): Let \(A\) be a finite relational structure of finite type and let \(I\) be a given structure of the same type. Does there exist a homomorphism from \(I\) to \(A\)? To each relational structure \(A\) naturally an algebra \({\mathbf A}\) is associated whose structure determines the complexity of the associated decision problem. In the paper the authors investigate finite algebras arising from CSPs of bounded width, i.e. for which local consistency algorithms effectively decide the problem. They are able to prove that bounded width of a CSP implies that the variety generated by the associated algebra omits Hobby-McKenzie types 1 and 2. From this they can conclude the existence of CSPs that do not have bounded width. The paper concludes by giving several applications of this result by showing that various graph homomorphism problems do not have bounded width, i.e. that the corresponding graph-decision problems cannot be solved using local consistency algorithms.