We give a precise algebraic characterization of the power of Sherali--Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) to optimality. The condition is that of bounded width, which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite programming for robust approximation of CSPs. Our characterization has several algorithmic and complexity consequences. On the algorithmic side, we show that several novel and well-known valued constraint languages are tractable via the third level of the Sherali--Adams relaxation. For the known languages, this is a significantly simpler algorithm than those previously obtained. On the complexity side, we obtain a dichotomy theorem for valued constraint languages that can express an injective unary function. This implies a simple proof of the dichotomy theorem for conservative valued constraint languages established by Kolmogorov and Živný [J. ACM, 60 (2013), 10], and also a ...
It could be that either SA @math and SA @math , or SA @math and SA @math have the same power. The former happens in case of relational width. Dalmau proved that if a crisp language has relational width @math then it has relational width @math @cite_52 . Together with Theorem and the analogue of Proposition for relational width established in @cite_55 , this gives a trichotomy for relational width.
@cite_55 @cite_52
2150339067 2123895606
This paper starts with the project of finding a large subclass of NP which exhibits a dichotomy. The approach is to find this subclass via syntactic prescriptions. While the paper does not achieve this goal, it does isolate a class (of problems specified by) "monotone monadic SNP without inequality" which may exhibit this dichotomy. We justify the placing of all these restrictions by showing, essentially using Ladner's theorem, that classes obtained by using only two of the above three restrictions do not show this dichotomy. We then explore the structure of this class. We show that all problems in this class reduce to the seemingly simpler class CSP. We divide CSP into subclasses and try to unify the collection of all known polytime algorithms for CSP problems and extract properties that make CSP problems NP-hard. This is where the second part of the title, "a study through Datalog and group theory," comes in. We present conjectures about this class which would end in showing the dichotomy. In this note, we show that every constraint satisfaction problem that has relational width 2 has also relational width 1. This is achieved by means of an obstruction-like characterization of relational width which we believe to be of independent interest.