Butti, Silvia ;
Dalmau, Víctor
Fractional Homomorphism, WeisfeilerLeman Invariance, and the SheraliAdams Hierarchy for the Constraint Satisfaction Problem
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 NPcomplete, the complexity of the graph isomorphism problem is not fully understood. A wellknown combinatorial heuristic for graph isomorphism is the WeisfeilerLeman 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 highquality relaxations that can still be solved efficiently. We study socalled 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 SheraliAdams 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 WeisfeilerLeman test, equitable partitions, and counting homomorphisms from trees. As a result, we obtain a description of the families of CSPs that are closed under WeisfeilerLeman invariance in terms of their polymorphisms as well as decidability by the first level of the SheraliAdams hierarchy.
BibTeX  Entry
@InProceedings{butti_et_al:LIPIcs.MFCS.2021.27,
author = {Butti, Silvia and Dalmau, V{\'\i}ctor},
title = {{Fractional Homomorphism, WeisfeilerLeman Invariance, and the SheraliAdams Hierarchy for the Constraint Satisfaction Problem}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {27:127:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14467},
URN = {urn:nbn:de:0030drops144679},
doi = {10.4230/LIPIcs.MFCS.2021.27},
annote = {Keywords: WeisfeilerLeman algorithm, SheraliAdams hierarchy, Graph homomorphism, Constraint Satisfaction Problem}
}
18.08.2021
Keywords: 

WeisfeilerLeman algorithm, SheraliAdams hierarchy, Graph homomorphism, Constraint Satisfaction Problem 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 