The concept of similarity between objects plays a key role in many fields, such as image processing, pattern recognition, and machine learning. Since a great variety of objects can be efficiently modelled with graphs, the size of the biggest common subgraph in two given graphs can give valuable information regarding the similarity between the objects that these graphs represent. However, the search for such a subgraph is an outstandingly difficult problem. [Conte, Foggia and Vento, 2007] showed that the best approach choice often depends on the properties of the compared graphs.
Constraint programming has recently been used to solve this problem and yielded promising results ([Ndiaye and Solnon, 2011], [Vismara, 2011]...). It induces a simple representation using a finite set of variables with finite domains, along with a set of constraints. In this context, this thesis objective is to take advantage from the structure of the compared graphs to fasten the resolution process, especially in three ways:
1) The microstructure of a CSP is a graph built to represent the compabilities between possible affectations. An improvement of the method presented in [Ndiaye and Solnon, 2011] will consist in using this microstructure to decompose the variables' domains and define several completely independent subproblems which may be solved seperately. To compute such a decomposition, every maximal clique of the microstructure must be found. However, there may be an exponnential number of such cliques. To limit this number, the microstructure can be triangulated ([Jégou, 1993], [Chmeiss and Jégou, 1997], [Ndiaye, 2005]). We will also consider the possibility of using 2-triangulation, which tends to be much more costly.
2) Techniques of tree-decomposition can improve the resolution process for structured CSPs ([Jégou and Terrioux, 2003]) by identifying subgraphs corresponding to strongly linked variables. In the context of the search for biggest subgraphs, these techniques may be useful to locate similar parts in the compared graphs in order to build solutions more efficiently.
3) In many applications, graphs contain automorphisms corresponding to symmetries that make the search space grow significantly. The third objective is to integrate symmetry-breaking techniques using the work of [Vismara and Coletta, 2012].