Point-width and Max-CSPs - Carbonnel, C; Romero, M; Živný, S (Association for Computing Machinery, 2020)
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs, β-acyclicity and bounded (incidence) MIM-width, are incomparable and lead to very different algorithms.