Tractable hypergraph properties for constraint satisfaction and conjunctive queries
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances (i.e., where each constraint involves only two variables), the situation is well understood: the complexity …