Point-Width and Max-CSPs

Clément Carbonnel, Miguel Romero, Stanislav Åivný

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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. We introduce the framework of point decompositions for hypergraphs and use it to derive a new sufficient condition for the tractability of (structurally restricted) Max-CSPs, which generalises both bounded MIM-width and β-acyclicity. On the way, we give a new characterisation of bounded MIM-width and discuss other hypergraph properties which are relevant to the complexity of Max-CSPs, such as β-hypertreewidth.

Original languageEnglish
Article number3409447
JournalACM Transactions on Algorithms
Issue number4
StatePublished - Sep 2020
Externally publishedYes


  • constraint satisfaction
  • hypergraphs
  • hypertree width
  • maximum constraint satisfaction
  • β-acyclicity


Dive into the research topics of 'Point-Width and Max-CSPs'. Together they form a unique fingerprint.

Cite this