Décider de l'homomorphisme du graphe est en général NP-complet.
Y a-t-il des résultats qui étudient ce problème lorsque les graphiques sous-jacents ont une structure algébrique (tels que la décision d'homomorphismes à partir de graphiques de Cayley ou de cosets Cayley vers d'autres graphiques avec une structure définie également)? En plus des résultats de complexité, je m'intéresse également aux techniques algébriques et / ou spectrales utiles.
Si est une classe de graphiques avec une largeur d'arbre bornée, alors le problème d'homomorphisme des graphiques dans est résolu en temps polynomial. Cela peut être généralisé à la propriété plus générale des «graphes dont le noyau a une largeur d'arbre limitée».G
Grohe prouve l'inverse: si les coeurs des graphiques dans ont une largeur d'arbre illimitée, alors le problème d'homomorphisme de n'est pas résolu en temps polynomial (en supposant ). Par conséquent, si vous limitez le graphique de gauche aux graphiques Cayley, etc., ce qui importe est de savoir si les cœurs ont une largeur d'arbre limitée.G F P T ≠ W [ 1 ]
http://dl.acm.org/authorize?951212
Notez que cela ne répond pas complètement à votre question: dans le résultat de Grohe, il est supposé que le graphique de droite est arbitraire. Vous semblez intéressé par les résultats où le graphique de droite est également limité à une classe spécifique de graphiques.
Décider s'il y a un homomorphisme de graphe est plus facile que de compter le nombre d'homomorphismes de graphe (pondérés).
Cas pondéré
Jin-Yi Cai, Xi Chen, Pinyan Lu. Graphique Homomorphismes avec des valeurs complexes: un théorème de dichotomie .
Cas non pondéré
Le cas non pondéré est beaucoup plus simple. Ci-dessous, j'énonce le théorème 1.1 de l'article suivant.
Martin Dyer, Catherine Greehill. La complexité du comptage des homomorphismes des graphes . (Aussi ce lien direct vers un PDF gratuit.)
Théorème 1:
la source