When is relaxed counting hard?

Question

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.

Answer 1

This is hard for planar graphs, at least for six colours or more. See "Inapproximability of the Tutte polynomial of a planar graph" by Goldberg and Jerrum

Answer 2

Some more comments:

A local algorithm for counting will compute the count from a set of per-node statistics where each statistic is a function of some graph neighborhood of the node. For colorings, those statistics are related to the "marginal probability of encountering color c". Here's an example of this reduction for a simple graph.

It follows from Alan Sly's recent paper that counting independent sets using a local algorithm is as hard as counting independent sets using any algorithm. My suspicion that this is true for general counting on graphs.

For local algorithms, hardness depends on how correlation between nodes behaves with respect to distance between nodes. For large enough distances, this correlation essentially has only two behaviors -- either correlation decays exponentially in graph distance, or it doesn't decay at all.

If there's exponential decay, local statistics depend on a neighbourhood whose size is polynomial in size of the graph, so the problem of counting is easy.

In statistical physics models it was noted (ie, de Gennes, Emery) that there's a connection between self-avoiding walks, correlation decay, and phase transitions. The point at which generating function for self-avoiding walks on a lattice becomes infinite corresponds to the temperature at which long-range correlations appear in the model.

You can see from Weitz' self-avoiding walk tree construction why self-avoiding walks come up in correlation decay -- marginal can be represented exactly as a root of a tree of self-avoiding walks, so if the branching factor of this tree is small enough, leaves of the tree become irrelevant eventually.

If "local hardness" implies hardness, then it's sufficient to quantify properties that determine the growth rate of self-avoiding walks. Exact growth rate can be extracted from the generating function for self-avoiding walks, but it is is intractable to compute. Spectral radius is easy to compute, and gives a lower bound.

Answer 3

Some comments: not an answer.

If $c$ is small enough with respect to the number of vertices in the graph, then the improper colourings will add up to less than 1. Hence there is a trivial reduction from the weight-0 case to this case: simply choose $c$ to be small enough. This means that the problem is #P-hard for any collection of instances with $c \in [0,\epsilon)$, for any $\epsilon > 0$. (Here I allow $c$ to be different in different instances, so the classes are unions of classes with fixed $c$.)

Now suppose that $c$ is truly fixed, as in your problem setup. Then for large enough graphs it is always possible to exceed a weighted sum of 1 for improper colourings, so this direct reduction does not work.

You are asking for structural properties of the class of graphs which would allow the problem to remain hard. As far as I can tell, it will be hard nearly always. But this is very sketchy and needs more work.