Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints
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.
Cite
Text
Kraiczy and McCreesh. "Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints." International Joint Conference on Artificial Intelligence, 2021. doi:10.24963/IJCAI.2021/193Markdown
[Kraiczy and McCreesh. "Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints." International Joint Conference on Artificial Intelligence, 2021.](https://mlanthology.org/ijcai/2021/kraiczy2021ijcai-solving/) doi:10.24963/IJCAI.2021/193BibTeX
@inproceedings{kraiczy2021ijcai-solving,
title = {{Solving Graph Homomorphism and Subgraph Isomorphism Problems Faster Through Clique Neighbourhood Constraints}},
author = {Kraiczy, Sonja and McCreesh, Ciaran},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2021},
pages = {1396-1402},
doi = {10.24963/IJCAI.2021/193},
url = {https://mlanthology.org/ijcai/2021/kraiczy2021ijcai-solving/}
}