Promise constraint satisfaction and width

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Atserias, Albert
• dc.contributor.author Dalmau, Víctor
• dc.date.accessioned 2023-02-23T07:10:49Z
• dc.date.available 2023-02-23T07:10:49Z
• dc.date.issued 2022
• dc.description Comunicació presentada a 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), celebrat del 9 al 12 de gener de 2022 de manera virtual.
• dc.description.abstract We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is that the template of every PCSP that is solvable in bounded width satisfies a certain structural condition implying that its algebraic closure-properties include weak near unanimity polymorphisms of all large arities. While this parallels the standard (non-promise) CSP theory, the method of proof is quite different and applies even to the regime of sublinear width. We also show that, in contrast with the CSP world, the presence of weak near unanimity polymorphisms of all large arities does not guarantee solvability in bounded width. The separating example is even solvable in the second level of the Sherali-Adams (SA) hierarchy of linear programming relaxations. This shows that, unlike for CSPs, linear programming can be stronger than bounded width. A direct application of these methods also show that the problem of q-coloring p-colorable graphs is not solvable in bounded or even sublinear width, for any two constants p and q such that 3 ≤ p ≤ q. Turning to algorithms, we note that Wigderson's algorithm for O( √ n)-coloring 3-colorable graphs with n vertices is implementable in width 4. Indeed, by generalizing the method we see that, for any ∊ > 0 smaller than 1/2, the optimal width for solving the problem of O(n∊)-coloring 3-colorable graphs with n vertices lies between n1–3∊ and n1–2∊. The upper bound gives a simple exp(Θ(n1–2∊ log(n)))-time algorithm that, asymptotically, beats the straightforward exp(Θ(n1–∊)) bound that follows from partitioning the graph into O(n∊) many independent parts each of size O(n1–∊).
• dc.description.sponsorship Albert Atserias: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS) and the Severo Ochoa and María de Maeztu Program for Centers and Units of Excellence in R&D (CEX2020-001084-M). Víctor Dalmau: Partially funded by the MICIN through grant PID2019-109137GB-C22 (PROOFS).
• dc.format.mimetype application/pdf
• dc.identifier.citation Atserias A, Dalmau V. Promise constraint satisfaction and width. In: Naor JS, Buchbinder N, editors. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA); 2022 Jan 9-12; Alexandria, United States. New York: Society for Industrial and Applied Mathematics; 2022. p. 1129-53. DOI: 10.1137/1.9781611977073.48
• dc.identifier.doi http://dx.doi.org/10.1137/1.9781611977073.48
• dc.identifier.uri http://hdl.handle.net/10230/55882
• dc.language.iso eng
• dc.publisher SIAM (Society for Industrial and Applied Mathematics)
• dc.relation.ispartof Naor JS, Buchbinder N, editors. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA); 2022 Jan 9-12; Alexandria, United States. New York: Society for Industrial and Applied Mathematics; 2022. p. 1129-53.
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-109137GB-C22
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/CEX2020-001084-M
• dc.rights © 2022 by SIAM. Unauthorized reproduction of this article is prohibited. First Published in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in 2022, published by the Society for Industrial and Applied Mathematics (SIAM).
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.subject.other Algorismes
• dc.subject.other Matemàtica
• dc.title Promise constraint satisfaction and width
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/publishedVersion