Abstract
The permanent of an n x n matrix A with 0-1 entries aij is defined by per (A) = Σ/σ Π/n-1/i=ο aiσ(i), where the sum is over all permutations σ of [n] = {0, …, n - 1}. Evaluating per (A) is equivalent to counting perfect matchings (1-factors) in the bipartite graph G = (V1, V2, E), where V1 = V2 = [n] and (i,j) ∈ E iff aij = 1. The permanent function arises naturally in a number of fields, including algebra, combinatorial enumeration and the physical sciences, and has been an object of study by mathematicians for many years (see [14] for background). Despite considerable effort, and in contrast with the syntactically very similar determinant, no efficient procedure for computing this function is known.
Convincing evidence for the inherent intractability of the permanent was provided in the late 1970s by Valiant [19], who demonstrated that it is complete for the class #P of enumeration problems and thus as hard as counting any NP structures. Interest has therefore recently turned to finding computationally feasible approximation algorithms (see, e.g., [11], [17]). The notion of approximation we shall use in this paper is as follows: let ƒ be a function from input strings to natural numbers. A fully-polynomial randomised approximation scheme (fpras) for ƒ is a probabilistic algorithm which, when presented with a string x and a real number ε > 0, runs in time polynomial in |x| and 1/ε and outputs a number which with high probability estimates ƒ(x) to within a factor of (1 + ε).
A promising approach to finding a fpras for the permanent was recently proposed by Broder [7], and involves reducing the problem of counting perfect matchings in a graph to that of generating them randomly from an almost uniform distribution. The latter problem is then amenable to the following dynamic stochastic technique: construct a Markov chain whose states correspond to perfect and 'near-perfect' matchings, and which converges to a stationary distribution which is uniform over the states. Transitions in the chain correspond to simple local perturbations of the structures. Then, provided convergence is fast enough, we can generate matchings by simulating the chain for a small number of steps and outputting the structure corresponding to the final state.
When applying this technique, one is faced with the task of proving that a given Markov chain is rapidly mixing, i.e., that after a short period of evolution the distribution of the final state is essentially independent of the initial state. 'Short' here means bounded by a polynomial in the input size; since the state space itself may be exponentially large, the chain must typically be close to stationarity after visiting only a small fraction of the space.
Recent work on the rate of convergence of Markov chains has focussed on stochastic concepts such as coupling [1] and stopping times [3]. While these methods are intuitively appealing and yield tight bounds for simple chains, the analysis involved becomes extremely complicated for more interesting processes which lack a high degree of symmetry. Using a complex coupling argument, Broder [7] claims that the perfect matchings chain above is rapidly mixing provided the bipartite graph is dense, i.e., has minimum vertex degree at least n/2. This immediately yields a fpras for the dense permanent. However, the coupling proof is hard to penetrate; more seriously, as has been observed by Mihail [13], it contains a fundamental error which is not easily correctable.
In this paper, we propose an alternative technique for analysing the rate of convergence of Markov chains based on a structural property of the underlying weighted graph. Under fairly general conditions, a finite ergodic Markov chain is rapidly mixing iff the conductance of its underlying graph is not too small. This characterisation is related to recent work by Alon [4] and Alon and Milman [5] on eigenvalues and expander graphs.
While similar characterisations of rapid mixing have been noted before (see, e.g., [2]), independent estimates of the conductance have proved elusive for non-trivial chains. Using a novel method of analysis, we are able to derive a lower bound on the conductance of Broder's perfect matchings chain under the same density assumption, thus verifying that it is indeed rapidly mixing. The existence of a fpras for the dense permanent is therefore established.
Reductions from approximate counting to almost uniform generation similar to that mentioned above for perfect matchings also hold for the large class of combinatorial structures which are self-reducible [10]. Consequently, the Markov chain approach is potentially a powerful general tool for obtaining approximation algorithms for hard combinatorial enumeration problems. Moreover, our proof technique for rapid mixing also seems to generalise to other interesting chains. We substantiate this claim by considering an example from the field of statistical physics, namely the monomer-dimer problem (see, e.g., [8]). Here a physical system is modelled by a set of combinatorial structures, or configurations, each of which has an associated weight. Most interesting properties of the model can be computed from the partition function, which is just the sum of the weights of the configurations. By means of a reduction to the associated generation problem, in which configurations are selected with probabilities proportional to their weights, we are able to show the existence of a fpras for the monomer-dimer partition function under quite general conditions. Significantly, in such applications the generation problem is often of interest in its own right.
Our final result concerns notions of approximate counting and their robustness. We show that, for all self-reducible NP structures, randomised approximate counting to within a factor of (1 + nβ), where n is the input size, is possible in polynomial time either for all β ∈ R or for no β ∈ R. We are therefore justified in calling such a counting problem approximable iff there exists a polynomial time randomised procedure which with high probability estimates the number of structures within ratio (1 + nβ) for some arbitrary β ∈ R. The connection with the earlier part of the paper is our use of a Markov chain simulation to reduce almost uniform generation to approximate counting within any factor of the above form: once again, the proof that the chain is rapidly mixing follows from the conductance characterisation.
