Using TPA to count linear extensions

A linear extension of a poset P is a permutation of the elements of the set that respects the partial order. Let L(P) be the set of linear extensions. It is a #P complete problem to determine the size of L(P) exactly for an arbitrary poset, and so randomized approximation algorithms are used that employ samples that are uniformly drawn from the set of linear extensions. In this work, a new randomized approximation algorithm is proposed where the linear extensions are not uniformly drawn, but instead come from a distribution indexed by a continuous parameter beta. The introduction of beta allows for the use of a more efficient method for approximating #L(P) called TPA. Our primary result is that it is possible to sample from this continuous embedding in time that as fast or faster than the best known methods for sampling uniformly from linear extensions. For a poset containing n elements, this means we can approximate L(P) to within a factor of 1 + is an element of with probability at least 1 - delta using O(n(3)(lnn)(ln#L(P))(2) is an element of(-2 )ln delta(-1)) expected number of random uniforms and comparisons. (C) 2018 Published by Elsevier B.V.