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

Kraiczy, Sonja; McCreesh, Ciaran

doi:10.24963/ijcai.2021/193

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

Sonja Kraiczy, Ciaran McCreesh

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1396-1402.

https://doi.org/10.24963/ijcai.2021/193

Keywords

Constraints and SAT: Constraints: Modeling, Solvers, Applications
Constraints and SAT: Constraint Satisfaction

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.

Sonja Kraiczy, and Ciaran McCreesh. 2021. Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1396–1402. https://doi.org/10.24963/ijcai.2021/193

@inproceedings{ijcai2021p193,
  title     = {Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints},
  author    = {Kraiczy, Sonja and McCreesh, Ciaran},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {1396--1402},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/193},
  url       = {https://doi.org/10.24963/ijcai.2021/193},
}

TY  - CPAPER
TI  - Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints
AU  - Kraiczy, Sonja
AU  - McCreesh, Ciaran
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 1396
EP  - 1402
DO  - 10.24963/ijcai.2021/193
UR  - https://doi.org/10.24963/ijcai.2021/193
ER  -