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
