Abstract
Dans ce rapport, nous nous intéressons à l'utilisation de testeurs de propriétés pour la recherche d'homomorphismes de graphes et d'hypergraphes. Après avoir montré quel genre de résultat nous pouvions attendre, nous étudions comment adapter les meilleurs testeurs connus à ce jour pour la résolution du problème k-max-csp, les limites de ces algorithmes utilisés dans le cadre de l'homomorphisme de graphes, et donnons de nouvelles bornes inférieures théoriques concernant ce genre d'algorithmes. En particulier, nous montrons que l'homomorphisme de graphe n'est pas effi cacement testable dans les modèles non-dense, ce que nous prouvons en généralisant le concept de graphe de Behrend.