Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem

Mostra el registre complet Registre parcial de l'ítem

• dc.contributor.author Butti, Silvia
• dc.contributor.author Dalmau, Víctor
• dc.date.accessioned 2023-01-20T07:51:14Z
• dc.date.available 2023-01-20T07:51:14Z
• dc.date.issued 2021
• dc.description Comunicació presentada a: MFCS 2021 celebrat del 23 a 27 d'agost de 2021 a Tallinn, Estònia.
• dc.description.abstract Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, the complexity of the graph isomorphism problem is not fully understood. A well-known combinatorial heuristic for graph isomorphism is the Weisfeiler-Leman test together with its higher order variants. On the other hand, both problems can be reformulated as integer programs and various LP methods can be applied to obtain high-quality relaxations that can still be solved efficiently. We study so-called fractional relaxations of these programs in the more general context where 𝐀 and 𝐁 are not graphs but arbitrary relational structures. We give a combinatorial characterization of the Sherali-Adams hierarchy applied to the homomorphism problem in terms of fractional isomorphism. Collaterally, we also extend a number of known results from graph theory to give a characterization of the notion of fractional isomorphism for relational structures in terms of the Weisfeiler-Leman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under Weisfeiler-Leman invariance in terms of their polymorphisms as well as decidability by the first level of the Sherali-Adams hierarchy.
• dc.description.sponsorship Silvia Butti: The project that gave rise to these results received the support of a fellowship from “la Caixa” Foundation (ID 100010434). The fellowship code is LCF/BQ/DI18/11660056. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 713673. Víctor Dalmau: Víctor Dalmau was supported by MICCIN grant PID2019-109137GB-C22.
• dc.format.mimetype application/pdf
• dc.identifier.citation Butti S, Dalmau V. Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem. In: Bonchi F, Puglisi SJ, editors. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021); 2021 Aug 23-27; Tallinn, Estonia. Germany: Dagstuhl Publishing; 2021;(27):19 p. DOI: 10.4230/LIPIcs.MFCS.2021.27
• dc.identifier.doi http://dx.doi.org/10.4230/LIPIcs.MFCS.2021.27
• dc.identifier.issn 1868-8969
• dc.identifier.uri http://hdl.handle.net/10230/55351
• dc.language.iso eng
• dc.publisher Dagstuhl Publishing
• dc.relation.ispartof Bonchi F, Puglisi SJ, editors. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021); 2021 Aug 23-27; Tallinn, Estonia. Germany: Dagstuhl Publishing; 2021;(27):19 p.
• dc.relation.projectID info:eu-repo/grantAgreement/EC/H2020/713673
• dc.relation.projectID info:eu-repo/grantAgreement/ES/2PE/PID2019-109137GB-C22
• dc.relation.uri https://arxiv.org/abs/2107.02956
• dc.rights © Silvia Butti and Víctor Dalmau; licensed under Creative Commons License CC-BY 4.0
• dc.rights.accessRights info:eu-repo/semantics/openAccess
• dc.rights.uri https://creativecommons.org/licenses/by/4.0/
• dc.subject.keyword Weisfeiler-Leman algorithm
• dc.subject.keyword Sherali-Adams hierarchy
• dc.subject.keyword Graph homomorphism
• dc.subject.keyword Constraint Satisfaction Problem
• dc.title Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem
• dc.type info:eu-repo/semantics/conferenceObject
• dc.type.version info:eu-repo/semantics/publishedVersion