TY - GEN
T1 - Point-width and Max-CSPs
AU - Carbonnel, Clement
AU - Romero, Miguel
AU - Zivny, Stanislav
N1 - Funding Information:
Stanislav Živný was supported by a Royal Society University Research Fellowship. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 714532). The paper reflects only the authors’ views and not the views of the ERC or the European Commission. The European Union is not liable for any use that may be made of the information contained therein. Work done while Clément Carbonnel was at the University of Oxford.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/6
Y1 - 2019/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85070766318&partnerID=8YFLogxK
U2 - 10.1109/LICS.2019.8785660
DO - 10.1109/LICS.2019.8785660
M3 - Conference contribution
AN - SCOPUS:85070766318
T3 - Proceedings - Symposium on Logic in Computer Science
BT - 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019
Y2 - 24 June 2019 through 27 June 2019
ER -