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 from a family of graphs that excludes a topological minor. The algorithm is based on a reduction to a single-exponential number of constraint satisfaction problems over tractable languages and can handle cost minimization. We also present an improved randomized algorithm for the special case where the graph $H$ is an odd cycle.
Categories: cs.CC cs.DM