On estimating the number of order ideals in partial orders, with some applications (Q1209661)

The generation and counting of order ideals and antichains in a given partially ordered set \(P\) of \(n\) elements is one of the basic, frequently occurring problems in combinatorial optimization and operations research. Counting the ideals of a general poset was shown to be \(\# P\)-complete by Provan and Ball in 1983 even in the case where \(P\) contains no chain with more than two elements. This paper presents a new polynomial time algorithm to count the number of ideals of any fixed cardinality in 2-dimensional ordered sets. It also gives some bounds for the number \(\text{NO}(P)\) of all ideals. These bounds depend only on the width \(w(P)\) of \(P\), the maximum size of an antichain in \(P\). These bounds are: \[ 2^{w(P)}+n-w(P)\leq \text{NO}(P)\leq [(n+w(P))/w(P)]^{w(P)}. \] Finally, the paper reports on a computational study that used 300 randomly generated posets of varying sizes and different values for the width and density of the posets. The study supports that a large part of the variation in \(\text{NO}(P)\) amd SMAX can be explained by simple regression equations using the width and density as independent variables.