---
title: "Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints"
authors:
  - "Sonja Kraiczy"
  - "Ciaran McCreesh"
doi: "10.24963/ijcai.2021/193"
url: "https://ijcai.org/proceedings/2021/193"
pdf: "https://ijcai.org/proceedings/2021/0193.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "1396-1402"
track: "Main Track"
keywords:
  - "Constraints and SAT: Constraints: Modeling, Solvers, Applications"
  - "Constraints and SAT: Constraint Satisfaction"
---

# 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*, pages 1396-1402. DOI: [10.24963/ijcai.2021/193](https://doi.org/10.24963/ijcai.2021/193)

## Abstract

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.