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

DOI10.4230/LIPICS.MFCS.2021.27arXiv2107.02956OpenAlexW3193302153MaRDI QIDQ6168441FDOQ6168441

Authors: Silvia Butti, Víctor Dalmau 

Publication date: 8 August 2023

Abstract: Given a pair of graphs $extbfA$ and $extbfB$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $extbfA$ to $extbfB$ 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 $extbfA$ and $extbfB$ 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.

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)

Cited In (1)

• Approximate graph colouring and the hollow shadow

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168441)