Faster algorithms for graph homomorphism via tractable constraint satisfaction

Clément Carbonnel

We show that the existence of a homomorphism from an $n$-vertex graph $G$ to an $h$-vertex graph $H$ can be decided in time $2^{O(n)}{h}^{O(1)}$ and polynomial space if $H$ comes fro…