# When is relaxed counting hard?

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.

• Great question. – András Salamon Sep 22 '10 at 22:49
• This will be familiar to anyone working in this area, but perhaps you could mention that the exact problem for $k\geq3$ colours and $c\neq 1$ is known to be #P-hard by Theorem 1 of "The complexity of partition functions" by A. Bulatov & Grohe, because the $k\times k$ matrix with $c$ on the diagonal and $1$ elsewhere has rank at least 2. – Colin McQuillan Oct 10 '10 at 14:28
• Also, this is the antiferromagnetic q-state Potts model, correct? – Colin McQuillan Oct 10 '10 at 14:50
• @Kaveh: Could you roll that back? Those two tags, although least popular, described this question best. Retagging every question to include only the most popular tags seems disingenuous to me. – RJK Nov 2 '10 at 8:44
• @Kaveh: Why don't you ask the OP which arXiv tag(s) he wants and which non-arXiv tag(s) he wishes to remove, as opposed to making a unilateral choice according to popularity? I don't at all agree with the contention that giving more general tags organises the site better. My favourite tags do not include any top-level ones. – RJK Nov 2 '10 at 10:58

## 3 Answers

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

• Note that this is asking about relaxed version of counting. For any graph there's a range of c's for which relaxed counting is easy. The question is how to quantify this range – Yaroslav Bulatov Oct 10 '10 at 19:12
• OK. I seem to have stolen the bounty you offered, so I will reoffer 50 points on this question. – Colin McQuillan Oct 10 '10 at 23:52
• nice gesture, Colin ! – Suresh Venkat Oct 11 '10 at 2:12
• There were no other answers and the 50 points would have been lost otherwise! The system enforces an arbitrary 7-day limit for bounties. See meta.stackexchange.com/questions/1413/… for discussion of the most recent change in the system. – András Salamon Oct 11 '10 at 11:18

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.

• this is a nice summary, and thanks for the pointer to Allan Sly's paper: now I'm inspired to attend the talk ! – Suresh Venkat Oct 10 '10 at 20:23

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.