Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem

DOI10.4230/lipics.mfcs.2021.27arXiv2107.02956OpenAlexW3193302153MaRDI QIDQ6168441

Silvia Butti, Victor Dalmau

Publication date: 8 August 2023

Full work available at URL: https://arxiv.org/abs/2107.02956

zbMATH Keywords

graph homomorphismconstraint satisfaction problemSherali-Adams hierarchyWeisfeiler-Leman algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem