Randomised algorithms for counting and generating combinatorial structures
Alistair Sinclair · ERA · 1988
The thesis studies the computational complexity of two natural classes of combinatorial problems: counting the elements of a finite set of structures and generating them uniformly at random.For each problem class, a notion of efficient randomised approximation algorithm is defined.The central theme is the classification of counting and generation problems for natural combinatorial structures with respect to these notions of tractability.For many structures, the two problems are of essentially equivalent complexity at this level of approximation.The emphasis is on positive results.In particular, the thesis makes a detailed study of a general technique for random generation based on simulating a finite Markov chain whose states are the structures of interest and which converges to some desired distribution over them.The efficiency of this method depends crucially on the rate of convergence of the chain.A major portion of the thesis is devoted to deriving a characterisation of rapid convergence for a broad class of Markov chains in terms of a structural property of the underlying graph.This enables useful bounds on the rate of convergence of non-trivial chains to be established for the first time.As a result, the following classes of structures may be generated almost uniformly in polynomial time: perfect matchings in dense graphs, and matchings of all sizes in arbitrary graphs.This approach also