<p>This is hard for planar graphs, at least for six colours or more. See
<a href="http://arxiv.org/abs/0907.1724">"Inapproximability of the Tutte polynomial of a planar graph"</a> by Goldberg and Jerrum</p>

CC BY-SA 2.5
2010-10-10T19:12:59.853Z
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
CC BY-SA 2.5
2010-10-10T23:52:05.707Z
OK. I seem to have stolen the bounty you offered, so I will reoffer 50 points on this question.
Colin McQuillan
CC BY-SA 2.5
2010-10-11T02:12:20.453Z
nice gesture, Colin !
Suresh Venkat
CC BY-SA 2.5
2010-10-11T11:18:11.983Z
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 http://meta.stackexchange.com/questions/1413/why-an-answer-cant-be-accepted-after-an-unresolved-bounty for discussion of the most recent change in the system.
András Salamon
CC BY-SA 2.5
2010-10-10T15:06:49.343Z
2010-10-10T15:06:49.343Z
Colin McQuillan
<p>Some more comments:</p>

<p>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 <a href="http://yaroslavvb.com/research/qr/cavity-method/cavityReport.html" rel="noreferrer">example</a> of this reduction for a simple graph.</p>

<p>It follows from Alan Sly's recent <a href="http://arxiv.org/abs/1005.5584" rel="noreferrer">paper</a> 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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. </p>

<p>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.</p>

CC BY-SA 2.5
2010-10-10T20:23:09.930Z
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
CC BY-SA 2.5
2010-10-10T19:48:17.703Z
2010-10-10T19:48:17.703Z
Yaroslav Bulatov
<p>Some comments: not an answer.</p>

<p>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$.)</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-10T13:57:26.673Z
2010-10-10T13:57:26.673Z
András Salamon
<p>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 -- <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.7388">Tetali, (2007)</a></p>

<p>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.</p>

<p><b>Edit 09/23</b>: 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?</p>

<p><b>Edit 10/06</b>: This <a href="http://arxiv.org/abs/1005.5584">paper</a> 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. </p>

<p><b>Edit 10/31</b>: Alan Sokal conjectures (<a href="http://arxiv.org/abs/math/0503607">p.42 of "The multivariate Tutte polynomia"</a>) 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.</p>

CC BY-SA 2.5
2010-09-22T22:49:31.963Z
Great question.
András Salamon
CC BY-SA 2.5
2010-10-04T12:51:10.800Z
Could you make your question a bit more precise? 1) What local algorithms do you have in mind. 2) In the concrete question in the edit, what is the "branching factor of self-avoiding/regular walks" referring to. If it is just the degree of the tree of self-avoiding/regular walks where you create a new vertex whenever you repeat in the regular walks case, then the degree of these trees is bounded by the maximum degree in both cases, or both unbounded. I guess I don't really understand your question.
slimton
CC BY-SA 2.5
2010-10-04T16:33:01.763Z
1) I have an intuitive sense of "local" as something that excludes holographic algorithms, but I'm not 100% sure how to define it, so one could just drop it to answer "what makes this problem hard?" 2) maximum degree of graphs in a sequence doesn't have to be bounded
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-10T14:28:02.910Z
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
CC BY-SA 2.5
2010-10-10T14:50:02.783Z
Also, this is the antiferromagnetic q-state Potts model, correct?
Colin McQuillan
CC BY-SA 2.5
2010-10-10T15:03:43.240Z
Yes, I think it's equivalent to Potts
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-13T15:22:56.560Z
BTW, interesting paper, thanks. It seems that their rank-1 condition is far from capturing precisely what makes the exact problem hard. For instance, any partition function is easy to compute for bounded tree-width graphs
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-02T02:37:39.523Z
@Yaroslav Bulatov: I replaced the two least popular tags with two more popular top-level tags (since the site does not allow more than 5 tags), hoping that it would attract more interest and answers.
Kaveh
CC BY-SA 2.5
2010-11-02T08:44:15.243Z
@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
CC BY-SA 2.5
2010-11-02T10:17:48.770Z
@RJK: for now I rolled back as you said, but I think it is better to have at least one top level tag (AFAIK, this is required on MO). Tags are not for *describing* questions, that's what the title should do, tags are for *organizing* questions. I think we should start a meta discussion on this.
Kaveh
CC BY-SA 2.5
2010-11-02T10:30:43.250Z
@RJK: It seems that it is already decided that there should be at least one arXive tag. See [this](http://meta.cstheory.stackexchange.com/questions/253/retag-etiquette) meta discussion and Ryan's comment. So am rolling back to the other version.
Kaveh
CC BY-SA 2.5
2010-11-02T10:58:54.890Z
@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
CC BY-SA 2.5
2010-11-02T11:34:24.867Z
@RJK: the OP can of course change the top level tag to those he prefers, these were just those that I thought would apply. I think the idea for tagging is similar to the idea on arXive or subject classification on other sites (e.g. MSC), any submission to arXive needs at least one top level tag and I think it is very efficient in organizing submissions, but of course you can disagree. There are 4 other tags that can be used others tags including your favorite ones.
Kaveh
CC BY-SA 2.5
2010-11-02T14:25:55.583Z
@Kaveh: I should have added, or perhaps you could infer, that graph-colouring and counting-complexity are two of my favourite tags. This question happens to be extremely close to my current research, but now it is no longer highlighted when I visit TCS.SX due to your retag.  I think that probably many other people on this site "filter out the noise" in this way, because they are simply not interested in every possible question in complexity-theory or algorithms.
RJK
CC BY-SA 2.5
2010-11-02T21:29:07.753Z
This is a somewhat specialized question, and my impression is that most people in theoretical computer science have no background needed to answer it (or would even be interested in the answer), so I'd rather keep the more specialized tags, changed it to back to "counting complexity" and "colouring graphs"
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-03T17:13:14.713Z
I agree with RJK and Yaroslav. the complexity-theory tag is almost useless at this point because it's being used indiscriminately. the ds.algorithms tag might be more appropriate, but it really isn't. the best tags for this question are the current ones.
Suresh Venkat
CC BY-SA 2.5
2010-11-03T19:01:56.707Z
@Suresh: the reason is that lots of current questions do fall under cc.complexity-theory as defined in the tag wiki and on arXive, replace the tag with a better top level one if you know one. I thought that there is a consensus on the policy to have at least one top level arXive tag.
Kaveh
CC BY-SA 2.5
2010-11-03T22:21:45.350Z
true true. But this question is an example of where the arxiv characterization really fails IMO
Suresh Venkat
<graph-theory><approximation-algorithms><approximation-hardness><counting-complexity><graph-colouring>
When is relaxed counting hard?
Yaroslav Bulatov
# When is relaxed counting hard?

(Asked by: username_0 on 2010-09-22)

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)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.127.7388)

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](http://arxiv.org/abs/1005.5584) 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"](http://arxiv.org/abs/math/0503607)) 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.

**Tags:** graph-theory, approximation-algorithms, approximation-hardness, counting-complexity, graph-colouring
> **Comments:**
> **username_1**: Great question.  
> **username_2**: Could you make your question a bit more precise? 1) What local algorithms do you have in mind. 2) In the concrete question in the edit, what is the "branching factor of self-avoiding/regular walks" referring to. If it is just the degree of the tree of self-avoiding/regular walks where you create a new vertex whenever you repeat in the regular walks case, then the degree of these trees is bounded by the maximum degree in both cases, or both unbounded. I guess I don't really understand your question.  
> **username_0**: 1) I have an intuitive sense of "local" as something that excludes holographic algorithms, but I'm not 100% sure how to define it, so one could just drop it to answer "what makes this problem hard?" 2) maximum degree of graphs in a sequence doesn't have to be bounded  
> **username_3**: 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.  
> **username_3**: Also, this is the antiferromagnetic q-state Potts model, correct?  
> **username_0**: Yes, I think it's equivalent to Potts  
> **username_0**: BTW, interesting paper, thanks. It seems that their rank-1 condition is far from capturing precisely what makes the exact problem hard. For instance, any partition function is easy to compute for bounded tree-width graphs  
> **username_4**: @Yaroslav Bulatov: I replaced the two least popular tags with two more popular top-level tags (since the site does not allow more than 5 tags), hoping that it would attract more interest and answers.  
> **username_5**: @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.  
> **username_4**: @RJK: for now I rolled back as you said, but I think it is better to have at least one top level tag (AFAIK, this is required on MO). Tags are not for *describing* questions, that's what the title should do, tags are for *organizing* questions. I think we should start a meta discussion on this.  
> **username_4**: @RJK: It seems that it is already decided that there should be at least one arXive tag. See [this](http://meta.cstheory.stackexchange.com/questions/253/retag-etiquette) meta discussion and Ryan's comment. So am rolling back to the other version.  
> **username_5**: @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.  
> **username_4**: @RJK: the OP can of course change the top level tag to those he prefers, these were just those that I thought would apply. I think the idea for tagging is similar to the idea on arXive or subject classification on other sites (e.g. MSC), any submission to arXive needs at least one top level tag and I think it is very efficient in organizing submissions, but of course you can disagree. There are 4 other tags that can be used others tags including your favorite ones.  
> **username_5**: @Kaveh: I should have added, or perhaps you could infer, that graph-colouring and counting-complexity are two of my favourite tags. This question happens to be extremely close to my current research, but now it is no longer highlighted when I visit TCS.SX due to your retag.  I think that probably many other people on this site "filter out the noise" in this way, because they are simply not interested in every possible question in complexity-theory or algorithms.  
> **username_0**: This is a somewhat specialized question, and my impression is that most people in theoretical computer science have no background needed to answer it (or would even be interested in the answer), so I'd rather keep the more specialized tags, changed it to back to "counting complexity" and "colouring graphs"  
> **username_6**: I agree with RJK and Yaroslav. the complexity-theory tag is almost useless at this point because it's being used indiscriminately. the ds.algorithms tag might be more appropriate, but it really isn't. the best tags for this question are the current ones.  
> **username_4**: @Suresh: the reason is that lots of current questions do fall under cc.complexity-theory as defined in the tag wiki and on arXive, replace the tag with a better top level one if you know one. I thought that there is a consensus on the policy to have at least one top level arXive tag.  
> **username_6**: true true. But this question is an example of where the arxiv characterization really fails IMO  

---

## 3 answers

### Answer by username_3 on 2010-10-10. Score: 11

This is hard for planar graphs, at least for six colours or more. See
["Inapproximability of the Tutte polynomial of a planar graph"](http://arxiv.org/abs/0907.1724) by Goldberg and Jerrum

> **Comments:**
> **username_0**: 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  
> **username_3**: OK. I seem to have stolen the bounty you offered, so I will reoffer 50 points on this question.  
> **username_6**: nice gesture, Colin !  
> **username_1**: 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 http://meta.stackexchange.com/questions/1413/why-an-answer-cant-be-accepted-after-an-unresolved-bounty for discussion of the most recent change in the system.  

---

### Answer by username_0 on 2010-10-10. Score: 5

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](http://yaroslavvb.com/research/qr/cavity-method/cavityReport.html) of this reduction for a simple graph.

It follows from Alan Sly's recent [paper](http://arxiv.org/abs/1005.5584) 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.

> **Comments:**
> **username_6**: this is a nice summary, and thanks for the pointer to Allan Sly's paper: now I'm inspired to attend the talk !  

---

### Answer by username_1 on 2010-10-10. Score: 4

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.


---

