Suppose we relax the problem of counting proper colorings by counting weighted colorings as follows: every proper coloring gets weight 1 and every improper coloring gets weight $c^v$ where $c$ is some constant and $v$ is the number of edges with endpoints are colored the same. As $c$ goes to 0, this reduces to counting proper colorings which is hard for many graphs. When c is 1, every colorings gets the same weight and the problem is trivial. When adjacency matrix of the graph multiplied by $-\log(c)/2$ has spectral radius below $1-\epsilon$, this sum can be approximated by belief propagation with convergence guarantee, so it's easy in practice. It's also easy in theory because a particular computation tree exhibits decay of correlations and hence allows a polynomial time algorithm for guaranteed approximation -- Tetali, (2007)My question is -- what other properties of the graph make this problem hard for local algorithms? Hard in a sense that only a small range of $c$'s can be addressed.Edit 09/23: So far I came across two deterministic polynomial approximation algorithms for this class of problem (derivatives of Weitz's STOC2006 paper and of Gamarnik's cavity expansion approach to approximate counting), and both approaches depend on the branching factor of self-avoiding walks on the graph. Spectral radius comes up because it's an upper bound on this branching factor. The question is then  -- is it a good estimate? Could we have a sequence of graphs where branching factor of self-avoiding walks is bounded, while branching factor of regular walks grows without bound?Edit 10/06: This paper by Allan Sly (FOCS 2010) seems relevant...result suggests that branching factor of infinite tree of self-avoiding walks precisely captures the point at which counting becomes hard. Edit 10/31: Alan Sokal conjectures (p.42 of The multivariate Tutte polynomia) that a there's an upper bound on the radius of zero-free region of the chromatic polynomial which is linear in terms of maxmaxflow (maximum s-t flow over all pairs s,t). This seems relevant because long-range correlations appear as the number of proper colorings approaches 0.
When is relaxed counting hard?
graph theory;approximation algorithms;approximation hardness;counting complexity;graph colouring