La notion de similarité entre des objets est un point important dans de nombreux domaines tels que l'analyse d'images, la recherche de motifs, ou encore l'apprentissage automatique. Or, de nombreux objets peuvent être efficacement modélisés sous forme de graphes. La taille du plus grand sous-graphe commun se trouvant dans deux graphes donnés peut alors donner une indication précieuse pour estimer la similarité entre les objets qu'ils représentent. [Conte, Foggia and Vento, 2007] montre qu'en général le meilleur choix d'approche dépend des propriétés des graphes que l'on compare.

La programmation par contraintes a été récemment utilisée pour résoudre ce problème avec des résultats prometteurs ([Ndiaye and Solnon, 2011], [Vismara, 2011]...). Elle permet une modélisation simple à travers un ensemble fini de variables qui prennent leurs valeurs dans des domaines de taille finie en essayant de respecter un ensemble de contraintes. Dans ce contexte, l'objectif de la thèse est d'exploiter la structure des graphes pour accelérer la résolution, en particulier via trois pistes :
1) La microstructure d'un CSP est un graphe représentant les compatibilités entre les affectations possibles. Une amélioration de la méthode de résolution de [Ndiaye and Solnon, 2011] va consister à utiliser cette microstructure pour décomposer les domaines des variables et définir plusieurs sous-problèmes totalement indépendants qui pourront être résolus séparément. Le calcul de cette décomposition repose sur la recherche de l'ensemble des cliques maximales de la micro-structure. Or leur nombre peut être exponentiel. Pour limiter ce nombre, on peut trianguler la micro-structure ([Jégou, 1993], [Chmeiss and Jégou, 1997], [Ndiaye, 2005]) avant d'en extraire les cliques maximales. L'éventualité de la 2-triangulation, plus coûteuse, devra également être considérée.
2) Les techniques de décomposition arborescente peuvent accélérer la résolution de problèmes de satisfaction de contraintes structurés ([Jégou and Terrioux, 2003]) en identifiant des sous-ensembles de variables fortement liées. Dans le contexte de la recherche de plus grands sous-graphes communs, elles peuvent permettre d'identifier des parties similaires entre les deux graphes afin d'accélérer la construction des solutions.
3) Dans beaucoup d'applications, les graphes contiennent des automorphismes correspondant à des symétries qui augmentent considérablement la taille de l'espace de recherche à explorer. Un troisième objectif de la thèse est d'intégrer des techniques permettant de casser ces symétries et donc d'accélérer la recherche de solutions. Nous nous appuierons pour cela sur les travaux de [Vismara and Coletta, 2012].