  We present a new local approximation algorithm for computing Maximum a
Posteriori (MAP) and log-partition function for arbitrary exponential family
distribution represented by a finite-valued pair-wise Markov random field
(MRF), say $G$. Our algorithm is based on decomposition of $G$ into {\em
appropriately} chosen small components; then computing estimates locally in
each of these components and then producing a {\em good} global solution. We
show that if the underlying graph $G$ either excludes some finite-sized graph
as its minor (e.g. Planar graph) or has low doubling dimension (e.g. any graph
with {\em geometry}), then our algorithm will produce solution for both
questions within {\em arbitrary accuracy}. We present a message-passing
implementation of our algorithm for MAP computation using self-avoiding walk of
graph. In order to evaluate the computational cost of this implementation, we
derive novel tight bounds on the size of self-avoiding walk tree for arbitrary
graph.
  As a consequence of our algorithmic result, we show that the normalized
log-partition function (also known as free-energy) for a class of {\em regular}
MRFs will converge to a limit, that is computable to an arbitrary accuracy.
