  We consider a refinement of the partition function of graph homomorphisms and
present a quasi-polynomial algorithm to compute it in a certain domain. As a
corollary, we obtain quasi-polynomial algorithms for computing partition
functions for independent sets, perfect matchings, Hamiltonian cycles and dense
subgraphs in graphs as well as for graph colorings. This allows us to tell
apart in quasi-polynomial time graphs that are sufficiently far from having a
structure of a given type (i.e., independent set of a given size, Hamiltonian
cycle, etc.) from graphs that have sufficiently many structures of that type,
even when the probability to hit such a structure at random is exponentially
small.
