Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints

Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints

Sonja Kraiczy, Ciaran McCreesh

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 1396-1402. https://doi.org/10.24963/ijcai.2021/193

Graph homomorphism problems involve finding adjacency-preserving mappings between two given graphs. Although theoretically hard, these problems can often be solved in practice using constraint programming algorithms. We show how techniques from the state-of-the-art in subgraph isomorphism solving can be applied to broader graph homomorphism problems, and introduce a new form of filtering based upon clique-finding. We demonstrate empirically that this filtering is effective for the locally injective graph homomorphism and subgraph isomorphism problems, and gives the first practical constraint programming approach to finding general graph homomorphisms.
Keywords:
Constraints and SAT: Constraint Satisfaction
Constraints and SAT: Constraints: Modeling, Solvers, Applications