Mark Huber Publications

Exact Sampling and Approximate Counting Techniques
M. Huber, Proc. 30th ACM Symposium on Theory of Computing (1998), pp. 31–40

Abstract: We present two algorithms for uniformly sampling from the proper colorings of a graph using k colors. We use exact snmpling from the stationary distribution of a Markov chain with states that are the k-colorings of a graph with maximum degree Δ. As opposed to approximate sampling algorithms based on rapid mixing, these algorithms have termination criteria that allow them to stop on some inputs much more quickly than in the worst case running time bound. For the first algorithm we show that when k > Δ(Δ + 2), the algorithm has an upper limit on the expected running time that is polynomial, For the second algorithm we show that for k > rΔ, where r is an integer that satisfies rr > n, the running time is polynomial. Previously, Jerrum showed that it was possible to approximately sample uniformly in polynomial time from the set of k-colorings when k &ge 2Δ, but our algorithm is the first polynomial time exact sampling algorithm for this problem. Using approximate sampling, Jerrum also showed how to approximately count the number of k-colorings, We give a new procedure for approximntcly counting the number of k-colorings that improves the running time of the procedure of Jerrum by a factor of (m/n)2 when k &ge 2Δ, where n is the number of nodes in the graph to be colored and m is the number of edges. In addition, we present an improved analysis of the chain of Luby and Vigoda for exact sampling from the independent sets of a graph. Finally, we present the first polynomial time method for exactly sampling from the sink free orientations of a gmph. Bubley and Dyer showed how to approximately sample from this state space in Θ(m3 ln(ε-1)) time, our algorithm takes O(m4) expected time.


This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.