# 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 *r*^{r} > 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 Θ(

*m*

^{3}ln(ε

^{-1})) time, our algorithm takes

*O*(

*m*

^{4}) 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.