Approximation Algorithms For Counting Problems

The classification of counting problems in terms of their computational complexity is a central topic in theoretical computer science.Despite the success in the exact counting setting,the study of the approximability is still in its infancy.Complete understanding of the approx-imability of counting problems only exists for some restricted models.In this thesis,we study the approximate counting algorithms in the framework of Holant problems,a concise yet expressive framework which includes a number of well-studied count-ing frameworks like counting homomorphism,counting CSP as special cases.This is the first systematic study of Holant problem in the approximate counting setting.Specifically,we de-velop techniques to design approximation algorithms for Holant problem.The techniques we use fall into two categories.Markov chain Monte Carlo.A classic technique to design approximate counting and sam-pling algorithms is the Markov chain Monte Carlo(MCMC)method.The key to the use of this method is analyzing the mixing time of a specific Markov chain.We give a new characteri-zation of the rapidly mixing Markov chains for Holant problems.The characterization can be used to explain nearly all previously successful application of the technique in the framework.Furthermore,it gives new approximate counting problems for natural combinatorial problems including counting b-matching and counting b-edge covers.Correlation Decay.A more modern technique we use is the method of correlation decay.This method has been successfully applied to produce optimal deterministic approximate count-ing algorithms for anti-ferromagnetic two-state spin system,in which MCMC method fails to apply.We first apply this method for Holant problems and obtain a number of new approximate counting algorithms.We first study the problem of counting weighted edges covers.This is a well-studied com-binatorial problem that can be described as a Holant problem with very simple constraint func-tions.Previous MCMC based randomized approximate algorithms only exist for graphs of max-imum degree three without edge weight.We successfully apply correlation decay technique to design deterministic approximate algorithms for all graphs with arbitrary edge weight.We then consider Hardcore models in hypergraphs.This is a model that has been well-studied in statistical physics,it also generalizes the problem of counting independent sets and it is equivalent to counting weighted solutions of monotone CNF.The approximability of the partition function of the model for ordinary graphs has been recently established.We extend the result to hypergraphs and show that the ordinary graphs are in fact the worst case in terms of approximability.A class of Holant problem that plays a central role in the exact counting setting is the unweighted Fibonacci gates,as it can be viewed as a computational primitive for many other Holant problems.We study the approximability of the weighted version,as it becomes#P-hard to exactly compute with edge weight present.We develop approximation algorithms with dif-ferent range of parameters.Like the case in the exact counting,these approximation algorithms can be transformed to algorithms for other problems via Holographic reduction.An impor-tant example is the problem of computing the partition function of ferromagnetic two-state spin system.Our result is the first deterministic approximation algorithm for this problem.We also study counting problems on special graphs.Tree-like Graphs.We consider graphs of low treewidth,which is a family of graphs close to trees.This notion plays an important role in the development of the graph minor theory.We identify a family of Holant problems which can be efficiently solved on this family of graphs.Our algorithm generalizes many known exact counting algorithms that involve treewidth as a parameter.Planar Graphs.We develop deterministic approximate counting algorithms on planar graphs.We make use of the locally tree-like structure of planar graphs and the correlation de-cay property.These two ingredients are respectively based on the algorithm for tree-like graph we developed before and a recursive coupling technique proposed recently.Our main result can be summarized as a sufficient condition under which Holant problems admit deterministic approximation algorithms on planar graphs.Random Graphs.Another special graph family we study is the Erdos-Renyi random graph g(n,p).This is a class of graphs with small average degree and large maximum degree.We con-sider the problem of counting proper q-colorings on g(n,d/n),we design an efficient sampler(which is equivalent to an approximate counting algorithm)for the problem provided q>3d+4,improving the current best bound q>5.5d.In fact,our algorithm works for more general mod-els and a broader family of sparse graphs.