A constraint programming approach to subgraph isomorphism

by Zampelli, Stéphane

This thesis proposes an expressive yet efficient declarative framework for graph matching in constraint programming (CP), and focuses on efficient algorithms to solve the subgraph isomorphism problem. The framework is based on graph and map variables, and specific graph morphism constraints. This allows to model and solve various graph matching problems, avoiding the tedious development of dedicated and specific algorithms. A specialized filtering algorithm is proposed for the subgraph isomorphism problem, which uses the semantic of the problem as well as the global structure of the two input graphs. It is shown that it is the state-of-the-art filtering algorithm, compared to dedicated algorithms and other CP approaches. Various search techniques from CP are also extended to the subgraph isomorphism problem. An automatic detection and exploitation of symmetries for the subgraph isomorphism problem is proposed, together with a decomposition approach of the search. The significance of this thesis lies in the fact that, even though the framework is expressive, CP can be considered as the state-of-the-art for subgraph isomorphism, outperforming the dedicated known algorithms on current benchmarks.