Affiliations: Department of Applied Mathematics and Computer
Science, Ghent University, Krijgslaan 281 S9, B-9000 Gent, Belgium. E-mail:
Karel [email protected] | Department of Applied Mathematics, Biometrics and
Process Control, Ghent University, Coupure links 653, B-9000 Gent,
Belgium
Abstract: In this paper, we demonstrate how some simple graph counting
operations on the ideal lattice representation of a partially ordered set
(poset)P allow for the counting of the number of linear extensions of P, for
the random generation of a linear extension of P, for the calculation of the
rank probabilities for every x∈P, and, finally, for the calculation of the
mutual rank probabilities Prob(x>y) for every
(x,y)∈P^2. We show that all linear extensions can be counted and a first random
linear extension can be generated in O(∣I(P)∣·w(p)) time, while
every subsequent random linear extension can be obtained in
O(∣P∣·w(P)) time, where ∣I(P)∣
denotes the number of ideals of the poset P and w(P)
the width of the poset P. Furthermore, we show that all rank probability
distributions can be computed in O(∣I(P)∣·w(P))
time, while the computation of all mutual
rank probabilities requires O(∣I(P)∣·∣P∣·w(P))
time, to our knowledge the fastest exact
algorithms currently known. It is well known that each of the four problems
described above resides in the class of #P-complete counting problems, the
counterpart of the NP-complete class for decision problems. Since recent
research has indicated that the ideal lattice representation of a poset can be
obtained in constant amortized time, the stated time complexity expressions
also cover the time needed to construct the ideal lattice representation
itself, clearly favouring the use of our approach over the standard ap-proach
consisting of the exhaustive enumeration of all linear extensions.
Keywords: poset, ideal lattice, random linear extension, number of linear extensions, rank probability distribution, mutual rank probabilities
