Suppose we want to find $$\sum_x \prod_{ij \in E} f(x_i,x_j)$$ or $$\max_x \prod_{ij \in E} f(x_i,x_j)$$

Where max or sum is taken over all labelings of $V$, product is taken over all edges $E$ for a graph $G=\{V,E\}$ and $f$ is an arbitrary function. This quantity is easy to find for bounded tree width graphs and in general NP-hard for planar graphs. Number of proper colorings, maximum independent set and number of Eulerian subgraphs are special instances of the problem above. I'm interested in polynomial time approximation schemes for problems of this kind, especially for planar graphs. What graph decompositions would be useful?

Edit 11/1: As an example, I'm wondering about decompositions that might be analogous to cluster expansions of statistical physics (ie, Mayer expansion). When $f$ represents weak interactions, such expansions converge, which means that you could achieve given accuracy with $k$ terms of the expansion regardless of the size of the graph. Wouldn't this imply existence of PTAS for the quantity?

Update 02/11/2011

High temperature expansions rewrite partition function $Z$ as a sum of terms where higher order terms depend on higher order interactions. When "correlations decay", high order terms decay fast enough so that almost all of $Z$'s mass is contained in finite number of low-order terms.

For instance for Ising model consider the following expression of its partition function

$$Z=\sum_\mathbf{x\in \mathcal{X}} \exp J \sum_{ij \in E} x_i x_j = c \sum_{A\in C} (\tanh J)^{|A|} $$

Here $c$ a simple constant, $C$ is a set of Eulerian subgraphs of our graph, $|A|$ is number of edges in subgraph $A$.

We have rewritten partition function as a sum over subgraphs where each term in the sum is exponentially penalized by size of the subgraph. Now group terms with same exponent together and approximate $Z$ by taking first $k$ terms. When number of Eulerian subgraphs of size $p$ doesn't grow too fast, the error of our approximation decays exponentially with $k$.

Approximate counting is hard in general, but easy for "correlation decay" instances. For instance, in the case of Ising model, there's correlation decay when $f(k)$ grows slower than $(\tanh J)^k$ where $f(k)$ is the number of Eulerian subgraphs of size $k$. I believe in such case, truncating high temperature expansion gives a PTAS for $Z$

Another example is counting weighted independent sets -- it's tractable for any graph if the weight is low enough because you can make the problem exhibit correlation decay. The quantity is then approximated by counting independent sets in bounded size regions. I believe Dror Weitz' STOC'06 result implies that unweighted independent set counting is possible for any graph with maximum degree 4.

I've found two families of "local" decompositions -- Bethe cluster graphs and Kikuchi region graphs. Bethe decomposition essentially tells you to multiply counts in regions, and divide by counts in region overlaps. Kikuchi region graph method improves on this by taking into account that region overlaps can themselves overlap, using "inclusion-exclusion" type of correction.

Alternative approach is to decompose the problem into global tractable parts, like in, "Variational Inference over Combinatorial Spaces". However, local decompositions allow you to control approximation quality by selecting region size


1 Answer 1


What I want to say is too long for (but really should be) a comment.

If I am reading the question correctly, you want a FPRAS (fully polynomial randomised approximation scheme) for either of the above quantities, each of which includes various #P-complete problems as special cases. In particular, you want a general FPRAS in the case of planar graphs, by the use of cluster expansion.

I doubt that this is possible due to the fact that NP-completeness of the existence problem (e.g. proper colouring) implies that the corresponding counting problem (e.g. number of proper colourings) is complete in #P with respect to AP-reducibility (approximation-preserving). See Dyer, Goldberg, Greenhill and Jerrum, Algorithmica (2004) 38: 471-500.

But perhaps I've misread the question.

(Actually, would you be able to explain to the uninitiated the meaning of high-temperature expansions?)

  • $\begingroup$ I've put reply into my question $\endgroup$ Feb 12, 2011 at 4:05
  • $\begingroup$ @Yaroslav: Thank you for the extensive clarification! BTW, by "region" do you mean "vertex subset"? (This is what I see when I look at Heske, JAIR 26 (2006), 153-190.) So in fact it seems that you seek specific FPRASs (that is, with particular choices of f) for specific classes (like degree at most 4) of planar graphs using what you refer to as "graph decomposition" (which is a very overloaded term, to be fair). Is that correct? $\endgroup$
    – RJK
    Feb 12, 2011 at 10:49
  • $\begingroup$ Yes, regions are vertex subsets, and I'm interested in PTAS for for "tractable" classes of graphs. BTW, here's a worked out example of a cluster decomposition to count independent sets which I think can be turned into PTAS for instances with correlation decay -- yaroslavvb.blogspot.com/2011/02/… $\endgroup$ Feb 15, 2011 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.