@article{165dfd3192f444e397ebe7ab3a04df7b,
title = "Point-Width and Max-CSPs",
abstract = "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.",
keywords = "constraint satisfaction, hypergraphs, hypertree width, maximum constraint satisfaction, β-acyclicity",
author = "Cl{\'e}ment Carbonnel and Miguel Romero and Stanislav {\AA}ivn{\'y}",
note = "Funding Information: An extended abstract of this work appeared in Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS{\textquoteright}19) [9]. The work was done while C. Carbonnel and M. Romero were at the University of Oxford. S. {\v Z}ivn{\'y} was supported by a Royal Society University Research Fellowship. This project received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement no. 714532). The article reflects only the authors{\textquoteright} 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. Authors{\textquoteright} addresses: C. Carbonnel, CNRS, University of Montpellier, LIRMM UMR 5506, CC477, 161 rue Ada 34095 Montpel-lier Cedex 5, France; email: clement.carbonnel@lirmm.fr; M. Romero, Facultad de Ingenier{\'i}a y Ciencias, Universidad Adolfo Ib{\'a}{\~n}ez, Diagonal Las Torres 2640, Pe{\~n}alol{\'e}n, Santiago, Chile; email: miguel.romero.o@uai.cl; S. {\v Z}ivn{\'y}, Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK; email: standa.zivny@cs.ox.ac.uk. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Association for Computing Machinery. 1549-6325/2020/09-ART54 $15.00 https://doi.org/10.1145/3409447 Funding Information: This project received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714532). Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2020",
month = sep,
doi = "10.1145/3409447",
language = "English",
volume = "16",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "4",
}